Is Cantor's diagonal argument dependent on the base used?

Solution 1:

Cantor's diagonal argument proves (in any base, with some care) that any list of reals between $0$ and $1$ (or any other bounds, or no bounds at all) misses at least one real number. It does not mean that only one real is missing. In fact, any list of reals misses almost all reals. Cantor's argument is not meant to be a machine that produces reals not in your list. It's an argument by contradiction to show that the cardinality of the reals (or reals bounded between some two reals) is strictly larger than countable. It does so by exhibiting one real not in a purported list of all reals. The base does not matter. The number produced by cantor's argument depends on the order of the list, and the base chosen. In base $2$, you have no freedom in choosing the digits, so each ordering of the list produces in this way one real guaranteed not to be in the list. In other bases you have more freedom in choosing the digits, but this is irrelevant.

Solution 2:

The order of the binary numbers $s_n$ are arbitrary. For example, if we swapped the places of $s_2$ and $s_3$, a different number will be formed. Hence there are still an infinite number of irrational numbers that can be generated.

Solution 3:

The fundamental result proven by Cantor's diagonal argument (as applied to the real numbers) is that:

For any countable subset $S \subset \mathbb R$ of the real numbers, there is a real number $x \in \mathbb R$ such that $x \notin S$.

From this result, it then obviously follows that $\mathbb R$ itself cannot be countable, since otherwise we could choose $S = \mathbb R$ and derive a contradiction.

(Here, "$S$ is countable" means that there exists a surjection $f$ from the natural numbers $\mathbb N$ to $S$, and hence, that we can enumerate all members of $S$ as $S = \{f(1), f(2),f(3),\dotsc\}$.)

The diagonal argument proves the fundamental result quoted above directly and constructibly, by providing an "algorithm"¹ that, given an enumeration $f$ of a countable subset $S = f(\mathbb N) \subset \mathbb R$ of the reals, computes a real number $x \in (\mathbb R \setminus S)$.

As you correctly note, for any given countable subset $S \subset \mathbb R$, it's possible to produce several such numbers $x$ by varying the details of the diagonal algorithm, such as the base used to expand the reals into digit sequences, or the specific digits chosen for $x$, if the base is high enough to allow multiple choices.

This should not really be surprising, since, for any countable set of real numbers $S$, there are infinitely (and, in fact, uncountably) many real numbers that are not in $S$, and could therefore be chosen as $x$. Any given instance of the diagonal algorithm (with the digit choice rules fully specified) only picks out one such $x$ for each enumeration $f$, but that's enough for what it's supposed to do.

(Of course, you can always generate more $x$s by modifying the enumeration $f$ — for example, you can take a previously generated $x$, prepend it to the enumeration, and run the algorithm again to get a new real number $x_2 \ne x$ that is also not in $S$, and so on.)

Ps. As alluded to in the comments, when applying the diagonal argument to the real numbers, there are certain practical reasons to choose a base higher than 2 anyway. The problem is that, in any base $b$, certain real numbers (specifically, those of the form $n / b^k$, for some integers $n$ and $k$) have two possible base-$b$ expansions: one that ends in an infinite string of zeros, and one that ends in an infinite string of $(b-1)$-digits (e.g. 9s, for base 10).

One way to make sure that we don't accidentally generate such an alternate representation of a number that does occur in the given enumeration is to avoid ever choosing the digit $(b-1)$ when constructing the base-$b$ expansion of $x$. In base 2, however, we don't have that freedom: if the $i$-th base-$b$ digit of $f(i)$ is 0, the diagonal algorithm has to choose a non-zero $i$-th digit for $x$, but if $b = 2$, the only possible choice is $1 = (2-1)$. Thus, to make sure that the diagonal algorithm really does what it's supposed to, we really should use base 3 or higher.

That said, it's possible to modify the diagonal algorithm in other ways, to make it work in base 2. For example, we may choose all odd-numbered digits of $x$ to be 0, and choose the even-numbered digits such that digit $2i$ of $x$ is not equal to digit $2i$ of $f(i)$. As long as we also make sure that, for any $f(i)$ that has two base-2 expansions, we always choose the one that ends in all zeros, this is sufficient to guarantee that $x \ne f(i)$ for any $i \in \mathbb N$.

^{1) It's not actually an algorithm in the strict sense used by computer scientists, since it requires infinitely many steps to exactly compute $x$, but it's close enough.}

Solution 4:

one and only one irrational number can be generated that is not on the list.

That is not true. If you take the number that you generate and add it to the list (say at the top), and then run the same procedure again, you will generate another number that is not on the list. You can do this ad infinitum and still not have all the real numbers in $[0, 1)$ in the list.