# How does Cantor's diagonal argument work?

I'm having trouble understanding Cantor's diagonal argument. Specifically, I do not understand how it proves that something is "uncountable". My understanding of the argument is that it takes the following form (modified slightly from the wikipedia article, assuming base 2, where the numbers must be from the set $\lbrace 0,1 \rbrace$):

\begin{align} s_1 &= (\mathbf{0},1,0,\dots)\\ s_2 &= (1,\mathbf{1},0,\dots)\\ s_3 &= (0,0,\mathbf{1},\dots)\\ \dots & (s_n \mathit{\ continues\dots}) \end{align}

In this case, the diagonal number is the bold diagonal numbers $(0, 1, 1)$, which when "flipped" is $(1,0,0)$, neither of which is $s_1$, $s_2$, or $s_3$.

My question, or misunderstanding, is: When there exists the possibility that more $s_n$ exist, as is the case in the example above, how does this "prove" anything? For example:

\begin{align} s_0 &= (1,0,0,\mathbf{0},\dots)\ \ \textrm{ (...the wikipedia flipped diagonal)}\\ s_1 &= (\mathbf{0},1,0,\dots)\\ s_2 &= (1,\mathbf{1},0,\dots)\\ s_3 &= (0,0,\mathbf{1},\dots)\\ s_4 &= (0,1,1,\mathbf{1},\dots)\\ s_4 &= (1,0,0,\mathbf{1},\dots)\ \ \textrm{ (...alternate, flipped } s_4\textrm{)}\\ s_5 &= (1,0,0,0,\dots)\\ s_6 &= (1,0,0,1,\dots)\\ \dots & (s_n \mathit{\ continues\dots}) \end{align}

… in other words, as long as there is a $\dots (continues\dots)$ at the end, the very next number could be the "impossible diagonal number"... with the caveat that it's not strictly identical to the "impossible diagonal number" as the wikipedia article defines it:

For each $m$ and $n$ let $s_{n,m}$ be the $m^{th}$ element of the $n^{th}$ sequence on the list; so for each $n$,

$s_n = (s_{n,1}, s_{n,2}, s_{n,3}, s_{n,4}, \dots)$.

...snip...

Otherwise, it would be possible by the above process to construct a sequence $s_0$ which would both be in $T$ (because it is a sequence of 0s and 1s which is by the definition of $T$ in $T$) and at the same time not in $T$ (because we can deliberately construct it not to be in the list). $T$, containing all such sequences, must contain $s_0$, which is just such a sequence. But since $s_0$ does not appear anywhere on the list, $T$ cannot contain $s_0$.

Therefore $T$ cannot be placed in one-to-one correspondence with the natural numbers. In other words, it is uncountable.

... but I'm not sure this definition is correct, because if we assume that $m = (1, \dots)$, then this definition says that "$s_n$ is equal to itself"- there is no "diagonalization" in this particular description of the argument, nor does it incorporate the "flipping" part of the argument, never mind the fact that we have very clearly constructed just such an impossible $T$ list above. An attempt to correct the "diagonalization" and "flipping" problem:

$s_n = (\lnot s_{m,m}, \lnot s_{m,m}, \dots)$ where $m$ is the element index and $$$\lnot s_{m,m} = \begin{cases}0 & \mathrm{if\ } s_{m,m} = 1\\1 & \mathrm{if\ } s_{m,m} = 0\end{cases}$$$

... but this definition doesn't quite work either, as we immediately run in to problems with just $s_1 = (0),$ which is impossible because by definition $s_1$ must be $= (1)$ if $s_1 = (0)$, which would also be impossible because... it's turtles all the way down!? Or more generally, with the revised definition there is a contradiction whenever $n = m$, which would seem to invalidate the revised formulation of the argument / proof.

Nothing about this argument / proof makes any sense to me, nor why it only applies to real numbers and makes them "uncountable". As near as I can tell it would seem to apply equal well to natural numbers, which are "countable".

What am I missing?

-
Closely related: math.stackexchange.com/questions/35107/… One could make a point that this is a duplicate, but in view of the effort put into this post, I'm against voting to close. –  t.b. May 15 '11 at 20:51
Every natural number is finite so you cannot produce one by any infinite diagonalization process like that. –  quanta May 15 '11 at 21:08
Just for the record, I did see that question, but it has to do with why Cantor's diagonal argument is or isn't applicable to the natural numbers. My question, or misunderstanding, is that I don't get how Cantor's diagonal argument works fundamentally. The description given at wikipedia and @Arturo Magidin's answer have (at first approximation) slightly different pedantic semantics, and @Asaf Karagila's answer definitely has different pedantic semantics. In good faith, I do believe they are different, or at least they seem different to me (which may not mean much if I don't understand it). –  johne May 15 '11 at 23:34

First, let me give you a proof of the following:

Let $\mathbb{N}$ be the natural numbers, $\mathbb{N}=\{1,2,3,4,5,\ldots\}$, and let $2^{\mathbb{N}}$ be the set of all binary sequences (functions from $\mathbb{N}$ to $\{0,1\}$, which can be viewed as "infinite tuples" where each entry is either $0$ or $1$).

If $f\colon\mathbb{N}\to 2^{\mathbb{N}}$ is a function, then $f$ is not surjective. That is, there exists some binary sequence $s_f$, which depends on $f$, such that $f(n)\neq s_f$ for all natural numbers $n$.

What I denote $2^{\mathbb{N}}$ is what Wikipedia calls $T$.

I will represent elements of $2^{\mathbb{N}}$ as tuples, $$(a_1,a_2,a_3,\ldots,a_n,\ldots)$$ where each $a_i$ is either $0$ or $1$; these tuples are infinite; we think of the tuple as defining a function whose value at $n$ is $a_n$, so it really corresponds to a function $\mathbb{N}\to\{0,1\}$. Two tuples are equal if and only if they are identical: that is, $$(a_1,a_2,a_3,\ldots,a_n,\ldots) = (b_1,b_2,b_3,\ldots,b_n,\ldots)\text{ if and only if } a_k=b_k\text{ for all }k.$$

Now, suppose that $f\colon\mathbb{N}\to 2^{\mathbb{N}}$ is a given function. For each natural number $n$, $f(n)$ is a tuple. Denote this tuple by $$f(n) = (a_{1n}, a_{2n}, a_{3n},\ldots,a_{kn},\ldots).$$ That is, $a_{ij}$ is the $i$th entry in $f(j)$.

I want to show that this function is not surjective. To that end, I will construct an element of $2^{\mathbb{N}}$ that is not in the image of $f$. Call this tuple $s_f = (s_1,s_2,s_3,\ldots,s_n,\ldots)$. I will now say what $s_k$ is. Define $$s_k = \left\{\begin{array}{ll} 1 &\mbox{if a_{nn}=0;}\\ 0 &\mbox{if a_{nn}=1.} \end{array}\right.$$

This defines an element of $2^{\mathbb{N}}$, because it defines an infinite tuple of $0$s and $1$s; this element depends on the $f$ we start with: if we change the $f$, the resulting $s_f$ may change; that's fine. (This is the "diagonal element").

Now, the question is whether $s_f = f(n)$ for some $n$. The answer is "no." To see this, let $n\in\mathbb{N}$ be any natural number. Then $$f(n) = (a_{1n},a_{2n},a_{3n},\ldots,a_{nn},\ldots)$$ so the $n$th entry of $f(n)$ is $a_{nn}$. If the $n$th entry of $f(n)$ is $0$, then by construction the $n$th entry of $s_f$, $s_n$ is $1$, so $f(n)\neq s_f$. If the $n$th entry of $f(n)$ is $1$, then by construction the $n$th entry of $s_f$, $s_n$, is $0$. Then $f(n)\neq s_f$ again, because they don't agree on the $n$th entry.

This means that for every $n\in\mathbb{N}$, $s_f$ cannot equal $f(n)$, because they differ in the $n$th entry. So $s_f$ is not in the image of $f$.

What we have shown is that given a function $f\colon\mathbb{N}\to 2^{\mathbb{N}}$, there is some element of $2^{\mathbb{N}}$ that is not in the image of $f$. The element depends on what $f$ is, of course; different functions will have possibly different "witnesses" to the fact that they are not surjective.

Think of the function $f$ being hauled before a judged and accused of Being Surjective; to prove its innocence, $f$ produces a witness to verify its alibi that it's not surjective; this witness is $s_f$, who can swear to the fact that $f$ is not surjective because $s_f$ demonstrates that $f$ is not surjective: $s_f$ is not in $\mathrm{Im}(f)$; if the police hauls in some other function $g$ and accuse that function of being surjective, $g$ will also have to produce a witness to verify its alibi that it isn't surjective; but that witness does not have to be the same witness that $f$ produced. The "witness" we produce will depend on who the "accused" is.

The reason this is called the "diagonal argument" or the sequence $s_f$ the "diagonal element" is that just like one can represent a function $\mathbb{N}\to \{0,1\}$ as an infinite "tuple", so one can represent a function $\mathbb{N}\to 2^{\mathbb{N}}$ as an "infinite list", by listing the image of $1$, then the image of $2$, then the image of $3$, etc: \begin{align*} f(1) &= (a_{11}, a_{21}, a_{31}, \ldots, a_{k1},\ldots )\\ f(2) &= (a_{12}, a_{22}, a_{32}, \ldots, a_{k2},\ldots)\\ &\vdots\\ f(m) &= (a_{1m}, a_{2m}, a_{3m},\ldots, a_{km},\ldots) \end{align*} and if one imagines the function this way, then the way we construct $s_f$ is by "going down the main diagonal", looking at $a_{11}$, $a_{22}$, $a_{33}$, etc.

Now, remember the definition of "countable":

Definition. A set $X$ is said to be countable if and only if there exists a function $f\colon\mathbb{N}\to X$ that is surjective. If no such function exists, then $X$ is said to be uncountable.

That means that the theorem we proved above shows that:

Theorem. The set of all binary sequences, $2^{\mathbb{N}}$, is not countable.

Why? Because we showed that there are no surjective functions $\mathbb{N}\to 2^{\mathbb{N}}$, so it is not countable.

How does this relate to the real numbers? The real numbers are bijectable with the set $2^{\mathbb{N}}$. That is, there is a function $H\colon 2^{\mathbb{N}}$ to $\mathbb{R}$ that is both one-to-one and onto. If we had a surjection $\mathbb{N}\to\mathbb{R}$, then composing this surjection with $H$ we would get a surjection from $\mathbb{N}$ to $2^{\mathbb{N}}$, and no such surjection exists. So there can be no surjection from $\mathbb{N}$ to $\mathbb{R}$, so $\mathbb{R}$ is not countable (that is, it is uncountable).

Bijecting $\mathbb{R}$ with $2^{\mathbb{N}}$ is a bit tricky; you can first biject $\mathbb{R}$ with $[0,1]$; then you would want to use the binary representation (as in wikipedia's article), so that each sequence corresponds to a binary expansion, and each number in $[0,1]$ corresponds to a binary sequence (its digits when written in binary); the problem is that just like some numbers in decimal have two representations ($1$ and $0.999\ldots$ are equal), so do some numbers have two representations in binary (for example, $0.01$ and $0.0011111\ldots$ are equal). There is a way of fixing this problem, but it is a bit technical and may obscure the issue, so I would rather not get into it.

Instead, let me note that the set $2^{\mathbb{N}}$ can be mapped in a one-to-one way into $(0,1)$: simply take a binary sequence $$(a_1,a_2,a_3,\ldots,a_n,\ldots)$$ and map it to the decimal number that has a $5$ in the $k$th decimal position if $a_k=0$, and has a $6$ in the $k$th decimal position if $a_k=1$. Using $5$ and $6$ ensures that each number has only one decimal representation, so the map is one-to-one. Call this map $h$. Define $H\colon\mathbb{R}\to 2^{\mathbb{N}}$ as follows: given a real number $x$, if $x$ is in the image of $h$, then define $H(x)$ to be the unique sequence $s$ such that $h(s)=x$. If $x$ is not in the image of $h$, then define $H(x)$ to be the sequence $(0,0,0,\ldots,0,\ldots)$. Notice that $H$ is surjective, because $h$ is defined on all of $2^{\mathbb{N}}$.

This is enough to show that there can be no surjection from $\mathbb{N}$ to $\mathbb{R}$: suppose that $f\colon\mathbb{N}\to\mathbb{R}$ is any function. Then the function $H\circ f\colon \mathbb{N}\stackrel{f}{\to}\mathbb{R}\stackrel{H}{\to}2^{\mathbb{N}}$ is a function from $\mathbb{N}$ to $2^{\mathbb{N}}$. Since any function from $\mathbb{N}$ to $2^{\mathbb{N}}$ is not surjective, there is some $s\in 2^{\mathbb{N}}$ that is not in the image of $H\circ f$. Since $s$ is in the image of $H$, there exists some $x\in\mathbb{R}$ such that $H(x)=s$. That means that $f(n)\neq x$ for all $n$ (since $H\circ f(n)\neq s$).

Since there can be no surjection from $\mathbb{N}$ to $\mathbb{R}$, that means that $\mathbb{R}$ is uncountable.

So, as to your questions. First, you should understand that the diagonal argument is applied to a given list. You already have all of $s_1$, $s_2$, $s_3$, etc., in front of you. Nobody is allowed to change them. You construct the "diagonal number" (my $s_f$ above) on the basis of that list. Yes, if you change the list then you can put the diagonal number $s_f$ in the new list; but $s_f$ is only a witness to the fact that the original list was not a list of all sequences. If you change to a different list, then I will have to produce a different witness. The witnesses depend on the given list. You know that $s_4$ is not equal to $s_f$ because $s_f$ is constructed precisely so that it disagrees with $s_4$ in the $4$th position, and one disagreement is enough to guarantee inequality.

Wikipedia's presentation seems to argue by contradiction; I don't like to introduce that into these discussions because the argument is difficult enough to "grok" without the added complication. (The "Otherwise..." part is an argument by contradiction, arguing that if you could 'list' the elements of $T$, then you would apply the argument to show that this 'complete list' is not 'complete', etc). There's no need. Simply, there is no surjection from $\mathbb{N}$ to $T$, as discussed above.

Now, there is a common "first reaction" that this argument would apply "just as well" to the natural numbers: take a list of natural numbers listed in binary, and engineer an argument like the diagonal argument (say, by "reflecting them about the decimal point", so they go off with a tail of zeros to the right; or by writing them from left to right, with least significant digit first, instead of last) to produce a "number" not on the list. You can do that, but the problem is that natural numbers only corresponds to sequences that end with a tail of $0$s, and trying to do the diagonal argument will necessarily product a number that does not have a tail of $0$s, so that it cannot represent a natural number. The reason the diagonal argument works with binary sequences is that $s_f$ is certainly a binary sequence, as there are no restrictions on the binary sequences we are considering.

I hope this helps.

-
Sometimes I just wish you were my teacher for all the courses I ever took... :-) –  Asaf Karagila May 15 '11 at 21:45
@johne: Generally, I prefer to keep things here rather than in my private mailbox; if they refer to my answer here and are of such length as to make asking them through comments too hard, then go ahead (but if so, then you should wait until you are satisfied before accepting this answer!). If they are follow-ups or of something else, you might consider simply posting a new question, referencing this one. –  Arturo Magidin May 15 '11 at 22:50
And also, let me say how impressed I am that you are willing to take the time to give such a comprehensive answer to someone who is obviously a "newb". This is the type of community I liked at stackoverflow, and I've written my share of lengthy answers there. The community and moderators over at cstheory sucks and, IMHO, is the antithesis to the whole stackoverflow idea. –  johne May 15 '11 at 23:25
@johne: I don't know what "pedantically surjective" means (note that "pedantic" is often use pejoratively; you might want to use a different word...). A function is bijective if and only if it is both injective and surjective, so any bijective function is also surjective; indeed, "bijective" is a special case of "surjective", just like "even integer" is a special case of "integer." –  Arturo Magidin May 16 '11 at 0:40
@johne: Arturo always gives detailed answers. Just goes to show that if an artist really loves an art, he gets pleasure out of sharing the art form with others and by performing the act over and over again each time, the artist gets to appreciate the different subtleties of the art form when he performs each time. Just a thought I wanted to share though this has no relevance to the question or answer –  user17762 May 16 '11 at 17:41

The idea, in a nutshell, is to assume by contradiction that the reals are countable. Due to that you can write them as $a_i$ for $i\in\mathbb N$. This list contains all the real numbers.

By taking the number produced by the diagonal argument you ensure at the $n$-th step that you are not any of $a_1,\ldots,a_n$. When the induction "ends" you have produced a real number which is none of the $a_i,\ i\in\mathbb N$.

This could only mean one thing: the enumeration did not capture all the real numbers like you assumed it to.

Since the enumeration was not specific, but arbitrary, we deduce that any countable enumeration of the reals will not cover the entire real numbers. This, by definition, means that the real numbers are uncountable.

After reading more carefully most of this thread (on its comments, and so on) I think that I should add a few words about proof by contradiction - which is a very common method in mathematics.

"Mathematics is a science of deductions", said my linear algebra prof. on the first day of my B.Sc.

"We assume A,B,C and deduce D,E,F", he continued.

The important thing about the ability to deduce things, is to remain consistent. In simple words it means not to be able to prove both something and its negation. Why is this important? Because it is simple to prove anything from contradiction, in fact according to this xkcd it is even possible to derive phone numbers (although I never managed to do that myself).

Proof by contradiction exploits the assumption that we use a consistent axiomatic system. If we assumed one thing, and derived from it contradiction then our assumption was false.

Since something is either true or false, if it is false then its negation is true.

So what did I do in the proof above? I started by assuming mathematics as we know it is consistent, then added the assumption "The reals are countable". If they are countable, then by definition we can list them as above.

The diagonal argument shows that regardless to how you are going to list them, countably many indices is not enough, and for every list we can easily manufacture a real number not present on it. From this we deduce that there are no countable lists containing all the real numbers. This is to say that the reals are not countable, which contradicts our assumption that they are countable.

I should add that some of the proofs by contradiction do not actually require the contrapositive assumption. In this case, for example, I could have said "given an arbitrary countable list of real numbers we can procure a real number not on the list" and deduce from that that the real numbers are uncountable. Sometimes, however, contradiction is slightly more essential for the proof.

-
I don't quite follow how this argument ensures that "you have a sequence which is none of the $a_i, i \in \mathbb{N}$". You can certainly construct such sequences, but I do not see how it guarantees that "none of the $a_i, i \in \mathbb{N}$". In my question, the first (non-alternate) $s_4$ would appear to be just such a number. I think your description captures the essence of why I'm confused: I don't understand how the argument goes from "can be true (but might not be)" to "must be true under all circumstances". –  johne May 15 '11 at 23:03
@johne: Note that $(P\to \neg P)\to\neg P$ is a tautology. That means that if from an assumption $P$ you can conclude that $P$ is false, that means that $P$ is false. The argument takes that form: Assume the list contains all reals (P="the list contains all reals"). Using the diagonal argument, you construct a real not on the list ($\neg P$="there is a real not on the list). So $P\to\neg P$; hence the conclusion is that $\neg P$ is true (given a list of reals, there is a real not on that last). –  Arturo Magidin May 15 '11 at 23:47
@Arturo: $(P \to \lnot P) \to \lnot P$, or more specifically "$P \to \lnot P$ ", does not reflect what it is you are asserting or trying to prove. What you are trying to prove is $P \land \lnot P$ : $P$="the list contains all reals", $\lnot P$="there is a real not on the list". If $\lnot P$ is "a real not on the list", then $P \cup \lnot P \ne P$, but $P$ is "a list that contains all reals" if, and only if, $P \cup \lnot P = P$. Both must be true simultaneously- $P \land \lnot P$, not if / then $P \to \lnot P$. –  johne May 16 '11 at 2:07
@johne: If from $P$ you can prove $\neg P$, then this proves $\neg P$. This is a simple consequence of the fact that $(P\to\neg P)\to\neg P$ is a tautology; that proving $A\to B$ is equivalent to assuming $A$ is true and then using that to prove $B$; and modus ponens. While the "classic" argument by contradiction proceeds by showing that from $P$ you conclude $A\land\neg A$ *for some $A$*, if from $P$ you can conclude $\neg P$, then you have both $P$ and $\neg P$, which gives you the conjunction you want. –  Arturo Magidin May 16 '11 at 2:16
@johne: So that would mean that from $P$ we can conclude $P\land \neg P$, and using this as an argument by contradiction this shows $\neg P$. But this is all codified in the argument I noted: that if from $P$ you can prove $\neg P$, then this is equivalent to proving that $P\to\neg P$ holds (Deduction Theorem); and since $(P\to\neg P)\to\neg P$ is a tautology, this and $P\to\neg P$ together, by Modus Ponens, yield $\neg P$. –  Arturo Magidin May 16 '11 at 2:25

The diagonal argument is best understood by first examining finite instances. Suppose $\rm\:M_{\:\!i\:j}\:$ is a $\rm\ n \times n\$ matrix whose entries lie in a set $\rm\:T\:$ with at least two elements. Then one can construct a $\rm\ 1\times n\$ row $\rm\:R\:$ different from any row $\rm\:M_{\:\!i}\:$ of $\rm\:M\:$ by taking the diagonal $\rm\:M_{\:\!i\: i}\:$ and changing each of its entries, viz. $\rm\:R_{\:\!i} := \neg\: A_{\:\!i\: i},\:$ where $\:\neg\:$ is any "change" function on $\rm\:T,\:$ i.e. $\rm\: \neg\: t \ne t\:$ $\rm\:\forall\:t\in T.\:$ Note that $\rm\:R\:$ is not equal to any row $\rm\:M_{\:\!i}\:$ since its $\rm\:i$'th entry differs, i.e. $\rm\:R_{\:\!i} =\: \neg\: M_{\:\!i\:i}\ne M_{\:\!i\:i}\:.\:$

Viewing each row $\rm\:M_{\:\!i}\:$ as a function $\rm\:j\mapsto M_{\:\!i\: j}\:$ from $\rm\:n = \{0\ 1\:\cdots\: n-1\}\:$ to $\rm\:T,\:$ the proof shows that there are more than $\rm\:n\:$ such functions, i.e. $\rm\:|T^{\:\!n}| > n\:$ if $\rm\:|T|\ge 2\:.\:$ Obviously the proof generalizes from $\rm\:n\:$ to any set $\rm\:S,\:$ yielding that $\rm\:|T^S| > |S|\:.\:$ This illustrates the simple essence of diagonalization - which is due not to Cantor, but to du Bois-Reymond (who used it to diagonalize on growth rates of functions, i.e. "orders of infinity").

-

I am a maths student and wish to express my understanding on this subject. Cantor proved that the set of real numbers is not only infinite but also non-denumerable. Denumeration requires equivalence. Equivalence requires an unbreakable biunique correspondence. Lets assume that all the real numbers have actually been denumerated in a sequence. It means that we have established a biunique correspondence between our set of real numbers and set of positive integers. so both are equivalent. fair enough. Cantor found a trick - diagnoal argument - to destroy this biunique correspondence by creating a new number out of the set of real numbers in consideration. What it means that the biunique correspondence between any given set of real numbers and set of positive integers is very fragile and can be broken down easily by creating a new number.

-
What is "unbreakable biunique correspondence"? What is an unbreakable correspondence? –  Asaf Karagila Sep 25 '12 at 17:17

[This comment avoids formality. At the bottom, it draws a contrast with the @Arturo Magidin answer.]

A goal of this comment will be to help understand the following claim:

Among ALL the "decimal" numbers between 0 and 1 lies at least
one number that is not rational.


[You said]… in other words, as long as there is a …(continues…) at the end, the very next number could be the "impossible diagonal number"

So you think there is a number not yet specified but which matches the irrational we are building?

OK..

Do you agree that any set of rational numbers (even the set of all of them) can be mapped to the set of positive integers? [At least one such way is usually shown in text books.]

Do you agree that mapping to the set of positive integers is the same as making a "list" in some precise order? The sequence order would match the integer number.

Now, let's consider the set of ALL decimal numbers between 0 and 1. For the moment, we'll informally accept "decimal number" to mean what we all expect: a real number written out in base 10 using decimal point notation.

Do you agree that if this set composed of ALL decimals between 0 and 1 (hereafter "decimals") included only rational numbers, then we could list our set, each decimal number, in a list in some order (ie, in some mapping to positive integers)? We already agreed that any set of rational numbers can be mapped, so if the decimals form such a set....

Do you agree this now implies that if we can't find at least one way to list each decimal number in order, then the set of decimal numbers was not composed solely of rational numbers? [Any such decimal that might not be rational can be referred to as an "irrational".]

So we have to assume that at least one listing exists (one such mapping to the positive integers). We'll consider such a list and do the Cantor diagonalization process on it.

Below, I cover the Cantor process a little more, but for the moment let's believe the result, that we found a decimal number that is not on an alleged ordered listing of ALL decimals.

This is a contradiction. We can't have a list of ALL decimals but at the same time find a decimal that is not on that list.

This means one or more of our assumptions were incorrect.

What were our assumptions?

Primarily we stated we had a set consisting exactly of all decimals, and we assumed these were all rational numbers.

Unless you point out another specific "gotcha" or assumption, I'll assume this is it.

So we conclude that

we can't have a set of all decimals AND
have these all be rational numbers.


Having made the conclusion, let's backtrack to consider more carefully the Cantor diag process and a related issue of representation of a number.

For the table, we just list the digits after the decimal point (each decimal being in the range (0,1) ).

You claim that the number D we were constructing might match some other decimal s4 that is further down on the list.

Do you agree that s4 appears on that list at location n for some positive integer n? That n is taken to be the positive integer to which we mapped s4.

Do you agree, then, that, by construction, D differs from s4 at least in position n?

Question:

Can s4 and D be the same number even though
they differ in at least one digit?


[You said]... with the caveat that it's not strictly identical to the "impossible diagonal number"

Two decimal numbers, by a definition that forms a part of what we decided it means to be a decimal number (ie, a real number), satisfy exactly one of the following:

x=y
x<y
x>y


s4=D (?)


That is, you think that although s4 and D might be represented differently on the table, it's possible that (in the sense of equality under real numbers) s4 and D might be equal.

(to be continued)

... time passes...

I took a careful look at the answer provided by Arturo Magidin. Besides the obvious differences in degree of formality between this comment and that one (formality implies greater accuracy and correctness, perhaps at the cost of understandability to someone not comfortable with the material), there are a few other points of contrast I want to mention.

1 -- One point is that I considered mappings from "decimals" to the natural numbers (ie, to positive integers). Arturo's answer looks at mappings from natural numbers to the set in question (ie, flips the mapping's origin and destination). That flip is not a major issue as goes this comment (ie, for the particular focus of this comment), but keep it in mind if you read both replies. Surjective is the same as "onto", btw. It's perhaps easier and more natural to use that other mapping direction to be able to also label finite sets as "countable". Also, I have not checked, but that approach is very likely in agreement with accepted definitions (something always useful to consider if you want to entertain formality).

2 -- [From the other answer:] "...so do some numbers have two representations in binary (for example, 0.01 and 0.0011111… are equal). There is a way of fixing this problem, but it is a bit technical and may obscure the issue, so I would rather not get into it." So Arturo's more complete answer bypasses the "tricky" point I left off on right before taking a break (about multiple digit arrangements corresponding to values deemed to be =). However, although not via Cantor's argument directly on real numbers, that answer does ultimately go from making a statement on countability of certain sequences to extending that result to make a similar statement on the countability of the real numbers. This is covered in the last few paragraphs of the primary proof portion of that answer. Pay attention to the order of mappings and how surjective (as well as injective) are used.

3 -- This brings up distinction three. Arturo's answer focuses on binary sequences (similar to the concept of binary representations) before later extending to "decimals". I informally just looked at anything that looks like an ordinary base 10 decimal number we are all used to using when we deal with numbers and measurements. The distinction taken into account there is to (perhaps more easily) deal with formal issues (which were not a concern for this comment).

4 -- [From the other answer:] "argue by contradiction; I don't like to introduce that into these discussions because the argument is difficult enough to 'grok' without the added complication." In contrast, this comment argues by contradiction a fair amount. While it is easier to do this when you don't want to define precise definitions, you may have noted that I kept bringing up the issue of "assumptions". We can consider that open-endedness to be one type of "complication"; however, this open-endedness is an important concern. I was addressing, not a proof under an abstract system loaded with its formal definitions, but the fact that abstract models ultimately "have to" find a way to be useful to society and the real world. It is this feedback/reality-check that leads the abstract models to be refined over time. This idea that a model might be deficient or that we might have to go back and analyze our assumptions or our axioms more carefully in order to keep in sync with the real world is an issue that more easily steals a certain amount of focus when you are dealing with proofs by contradiction. [The recognition of physical models (based on sound mathematical foundation) as "guesses" of reality plays a big part in engineering disciplines and engineering mindset.] On the other hand, within an accepted/proven framework, there is certainly something very comforting about being able to do direct proofs rather than indirect proofs.

OK, the direct proof approach and greater degree of formality is perhaps an important reason Arturo's comment took the path it took and differed from this comment in the above respects.

With all of this out of the way, I have decided for the moment to refer you to Arturo's comment if you want a more satisfying (precise) argument, and I may not finish up this comment addressing this last question of multiple/unique representations. [I may come back and edit, but likely I won't.]

-
I couldn't quite follow the entire argument. Could you somehow clarify the structure of this answer? Perhaps use some LaTeX code (which "pops out" from the text) and explain what do you mean exactly by "decimal numbers"? –  Asaf Karagila May 16 '11 at 17:38
When you start a paragraph with blank spaces, it produces a box that may require a scroll bar. This makes it difficult to read. You may want to break such lines up. –  Arturo Magidin May 18 '11 at 3:28

Begin by supposing that there exists a countably infinite list containing all of the reals between 0 and 1. Now we list them as non-repeating non-terminating strings of 0's and 1's(the decimal representation of an irrational number) in no particular order:

s1 = 38763302...
s2 = 65388487...
.
.
.


You can put an imaginary decimal point in front of each string of digits if it helps.

We can construct a string Su with the following rule:

For every entry Sn in the list, take the nth digit and choose a digit different from the one at that position. So Su might become 46...(anything but 35...) in our example. In this way we are able to generate a string of digits, the decimal representation of a real number, that is guaranteed not to be in the purported list of all reals between 0 and 1. Su is guaranteed to be different from any number on the list because for any Sn in the list, Su has been constructed to have a different digit at the nth position no matter how large n gets.

This leaves us with a contradiction: (1) there exists a countably infinite list containing all of the reals between 0 and 1, and (2) there exists a real number between 0 and 1 that can't possibly be on that list.

So the original assumption that there exists a countably infinite list containing all of the real numbers between 0 and 1 was false and they are uncountable: we are unable to put them in 1 to 1 correspondence with the counting numbers.

-
Do you have any reference to the claim that the original argument was only about irrationals? (Note that it is false that the digits of an irrational number are random "by definition". Champernowne's constant $0.12345678910111213141516\ldots$ is transcendental, but its digits are very far from "random". And I have a hard time seeing how to guarantee that the number resulting from the diagonal process will necessarily be irrational. –  Arturo Magidin May 15 '11 at 22:26
Okay, at least the meaning of irrational is now correct; but there is still no warrant for the assertion that the resulting sequence will be "non-repeating, non-terminating". And I would still like to know some reference for the assertion that Cantor was considering a list of irrationals only (that is, you "understanding that Cantor restricted his argument to the irrationals"). Where does this understanding come from? –  Arturo Magidin May 15 '11 at 22:53