# Misconceptions about Cantor's diagonal argument?

I started to make a demonstration of Cantor's diagonal argument on Mathematica, by reading here, I've noticed that I'd need to do a list of tuples with binary digits, and I tried to do it on Mathematica with the following command:

TableForm[Tuples[{0, 1}, 4]]


Which yields:

$$\begin{array}{cccc} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ \end{array}\tag{1}$$

And then I tried to apply the diagonal argument:

\begin{array}{cccc} & \color{red}{0} & 0 & 0 & 0 \\ & 0 & \color{red}{0} & 0 & 1 \\ & 0 & 0 & \color{red}{1} & 0 \\ \rightarrow& 0 & 0 & 1 & \color{red}{1} \end{array}

And found a number that is already on the list, that number is already in the fourth row of the list. I looked at the wikipedia page again and noticed that the list of sequences of binary digits have a pattern that is completely different of the pattern I constructed:

$$\begin{array}{ccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ \end{array}\tag{2}$$

And that in this pattern, the afirmation about the diagonal sequence not being in the set of sequences is true. I got curious about the following:

• What is this pattern? I mean, what is the formula to make it? I've read one book that had the following construction:

$$\begin{array}{ccccccc} \mathbb{N} & 1 & 2 & 3 & 4 & 5 & \cdots \\ \text{Is prime} & 0 & 1 & 1 & 0 & 1 & \cdots \\ \text{Is odd} & 1 & 0 & 1 & 0 & 1 & \cdots \\ \text{Is even} & 0 & 1 & 0 & 1 & 0 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{array}\tag{3}$$

And the diagonal proposition works here too, but I noticed that this new pattern is different from the previous one - But I can notice that they have something in common because the the diagonal argument works in both of them.

• What property do the lists $(2)$ and $(3)$ share that enables them to have the diagonal argument applied on them succesfully?

• Why choose the set of sequences that have this property instead of the one I proveded in $(1)$? - The question may be silly, but in the book I read about (and even in the wikipedia link I provided), it says:

$$\text{"In his 1891 article, Cantor considered the set T of all infinite sequences of binary digits"}$$

And I guess the sequence I provided is also a list of all infinite sequences of binary digits, I'd just need to change the $4$ in TableForm[Tuples[{0, 1}, 4]].

-
The pattern used is just by way of example. The point is that no list can contain all real numbers in $(0,1)$; that example list is employed just to illustrate the method. Any list can do this job. –  egreg Jan 17 '14 at 23:18
For sequences of length $n$, the diagonalization works only for at most $n$-many sequences as in example (2) you posted. To understand why, just think about the proof. –  hot_queen Jan 17 '14 at 23:42

The essence of Cantor's diagonal argument is quite simple, namely:

• Given any square matrix $F,\,$ one may construct a row-vector different from all rows of $F$ by simply taking the diagonal of $F$ and changing each element.

In detail: suppose matrix $F(i,j)$ has entries from a set $B$ with two or more elements (so there exists a "change" map $\,\lnot\,$ on $B$ such that $\,\lnot b \neq b).$ Let $\,\lnot F(i,i)$ be the "changed diagonal" of $F,$ i.e. the row-vector obtained by applying $\lnot$ to each element of the diagonal $F(i,i)$ of $F.$ The changed diagonal of $F$ differs from each row-vector of $F$ because it differs on all diagonal elements, viz. the $i$'th row-vector $f_i$ of F has $i$'th entry $= F(i,i) \neq \lnot F(i,i) = i$'th entry of changed diagonal:

$$\left[ \begin{array}{ccc} \color{#c00}{f_1(1)} & f_1(2) & f_1(3) & \cdots\ \\ f_2(1) & \color{#c00} {f_2(2)} & f_2(3) & \cdots \\ f_3(1) & f_3(2) & \color{#c00}{f_3(3)} & \cdots \\ \\ & \vdots & & \color{#c00}\ddots \end{array}\right]\ \ \mapsto\ \ {\bf [}\,\lnot \color{#c00}{f_1(1)},\lnot \color{#c00}{f_2(2)},\lnot\color{#c00}{ f_3(3)},\,\ldots{\bf ]}$$

Notice that the above proof required no hypotheses on the index set of the rows and columns of $F.$ Although classically one thinks of a square matrix as indexed by a finite ordered set $\,\{1, 2, \ldots, n\},$ in fact the above proof holds for any abstract index set $A;$ then the rows are simply functions $\,f_j$ from $A$ to $B,$ and the matrix $F$ is just a set of such row-functions $\{f_i(j)\},$ indexed by $i \in A.$ This suggestve matrix viewpoint is adopted in the proof given below that nontrivial set exponentiation $B^A$ increases the cardinality $|A|$ of $A.$

Theorem $\$ Let $A, B$ be sets, and $B^A =$ set of functions from $A$ to $B.$
If $|B| > 1$ then $|B^A| > |A|,\,$ i.e. $B^A$ has more than $|A|$ functions.

Proof $\$ Given $|A|$ functions $f_i\, :\, A \to B,$ construct the $|A| \times |A|\,$ "matrix" $F(i,j) = f_i(j).\,$ The proof above shows that the changed diagonal function $\lnot F(i,i)$ differs from the given $|A|$ functions (= row-vectors of $F$); hence $|B^A| > |A|$ when $|B| > 1\ \$ QED

In particular, for $B = 2 = \{0, 1\}$ the theorem implies $|2^A| > |A|,$ i.e. the cardinality of the powerset of $A$ exceeds that of $A,\,$ once one recalls that the powerset of $A$ is the same as $2^A$ (subsets $S$ of $A$ are in $1$-$1$ correspondence with functions $f\, :\, A \to 2\,$ via: $\,i \in S \iff f(i) = 1;\,$ in other words consider $f$ as the characteristic function (bit-vector) for the subset $S$ of $A).\,$ A close examination of the classical proof will show that it is essentially identical to the above "matrix-theoretic" proof.

By the way, it is a historical mistake that the diagonalization is attributed to Cantor. In fact it dates to at least 1871 when du Bois-Reymond diagonalized on the growth rates of functions in his pioneering studies on "orders of infinity"

-
Yes. I've read this historical remark on Stillwell's Roads to Infinity. He mentioned that the original Cantor's proof from 1874 is based on a least upper bound of a certain sequence increasing of numbers. In 1875, Du Bois-Reymond presented his work and then in 1891, Cantor presented the diagonal argument. I've started to read this book and I was thinking it wouldn't be good because it's a pop-math book: I'm happy that it's a good book and it's also historically precise! Some books ignore this nuance. –  Voyska Jan 18 '14 at 5:16

You applied the diagonal argument wrong. The diagonal argument doesn't say "take the elements of the diagonal", but "take the diagonal, and flip the bits".

So the first use, should have given you the binary string $1100$ which is not on the list that you have used.

Note that the diagonal argument, in its general form, says that if $A$ is a set, and $S$ is a set of functions from $A$ into $\{0,1\}$, such that $|A|=|S|$ then there is a function from $A$ into $\{0,1\}$ which is not in $S$.

The list on $(1)$ includes all the binary sequences of length four, whereas the diagonal argument merely ensures that given four binary sequences of length four, there is one which is different than all of them.

Because four is so small, and $\Bbb N$ is infinite, it's easy to list ALL the binary sequences of length four. Clearly if you produce a binary sequence of four digits, it will appear on that list, but its not a list of $4$ elements.

-
Yes, yes, yes. I was scratching my head wondering if somehow my education was lacking and that there is an alternative "diagonalization argument", but I know of no other method than to alter the digit found on the diagonal. That's the point. –  nayrb Jan 17 '14 at 23:17
@egreg: I don't have to cope with anything. The claim is not that it is asymptotically distinct or something. We simply ensured that the result of the diagonal argument is distinct from all those sequences which appear on our list. –  Asaf Karagila Jan 17 '14 at 23:18
@egreg The diagonal argument strictly shows that the set of infinite sequences is uncountable. If you want to directly map this to a set of real numbers, you'll have an easier time using a base higher than 2, so you can always choose a different number that isn't the highest digit. –  MartianInvader Jan 17 '14 at 23:19
@egreg: If one wants to apply it directly to the real numbers, one can easily choose decimal basis, rather than a binary one, then it's easy to ensure the resulting number is distinct. –  Asaf Karagila Jan 17 '14 at 23:21
@nayrb: You're doing it wrong. You don't need to assume that the real numbers are countable. The proof is positive, given a countable set of real numbers, there is a real number which is not in that set. –  Asaf Karagila Jan 17 '14 at 23:29

If you apply the method to a list of finite tuples, then obviously you get an already existing tuple. But, as you see, going through the diagonal stops at the fourth element. For being able to “do” it fully, you need infinite sequences.

The list used in the Wikipedia article is just an example of what the beginning of a list could be, but the point is that no list can contain all sequences. You don't want to show that a particular list doesn't contain all sequences, but rather that no list can contain all sequences.

Moreover, the diagonal method consists of taking a different digit.

So, if the $n$th item of the $n$th sequence is $0$ you choose $1$ and conversely. The built sequence cannot be in the list, because it differs from the first sequence in the first item, from the second sequence in the second item, and so on.

However, I don't think the Wikipedia article is accurate in saying that Cantor considered binary expansions of the real numbers. The article derives the uncountability of the real numbers from the fact about sequences in a correct way, but that isn't the original pattern, where decimal expansions were used. At Cantor's time binary representation of numbers wasn't used.

-