How does Cantor's diagonal argument work?

Question

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)\\ \vdots &= (s_n \text{ continues}) \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)\\ \vdots &= (s_n \text{ continues}) \end{align}

In other words, as long as there is a $\dots \text{ continues}$ 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.

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"&mdadsh;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) \quad \text{where $m$ is the element index and} \quad\begin{equation}\lnot s_{m,m} = \begin{cases}0 & \mathrm{if\ } s_{m,m} = 1\\1 & \mathrm{if\ } s_{m,m} = 0\end{cases}\end{equation}$$

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?

Answer 1

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.

Answer 2

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.

Addendum:

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.

Answer 3

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").

Answer 4

To address the problem noted in the Wiki article of 0.1239999... being equal to 0.124 (i.e. the problem of more than one representation of a decimal fraction), you an define a set $T'$ as the set of all infinite strings of digits excluding those ending with 9's trailing off to infinity.

In any enumerated list of elements from $T'$, you can define the $k^{th}$ element of the anti-diagonal to be $1$ if the $k^{th}$ element of the diagonal is $0$; $1$ otherwise. This anti-diagonal will be not be on the list, but will still be an element of $T'$. Thus $T'$ can also be shown to be uncountable.

Note that this argument will only work for bases greater than 2.

Answer 5

[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

So the allegation you have made (your doubt) is that

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.]

Answer 6

Remember that a set A is countable if there is a one-to-one correspondence function $f$ that maps every member of the set $Z^+$ (natural number) to every member of $A$, or written formally: $f:Z^+ \rightarrow A$.

The difficulty in understanding this proof stems from our mental blockage, which assumes that all infinite sets have the same cardinality, or number of elements. However, the idea behind the proof is actually straightforward:

1. Show that we have successfully mapped ALL the members of the set $Z^+$ to certain members of $A$.

2. Then show that there exist members of $A$ that have not yet been mapped.

So, to prove that a set is not countable, is to show that $f$ cannot possibly be surjective, or there are members of $A$ that that is not in the image of $f$.

Let's define the set $A = \prod_{i=1}^\infty A_i$ where each set $A_i$ is the two elements set $\{0,1\}$.

(You could define each set $A_i$ as the ten elements set $\{0,1,2,...,9\}$, in which you will get a set $A$ similar to how we usually write real numbers.)

Now assume that the set $A$ is countable. So, the set $A = \{(a_1, a_2, a_3, ...):a_i \in \{0,1\}$ for each $i \in Z^+\}$. Here we have mapped all member of the set $Z^+$ to certain members of the set $A$.

For an element $a = (a_1, a_2, a_3, ...)$ of A, let's refer to $a_1$ as the first coordinate, $a_2$ as the second coordinate, and so on.

However, we could always have elements $x = (x_1, x_2, x_3, ...)$ whose coordinates are defined as follows:

For each any positive integer $i$, $x_i = 1$ if the $i$th coordinate of $f(i)$ is $0$ and $x_i = 0$ if the $i$th coordinate of $f(i)$ is $1$.

In other words, $x_i$ is chosen so that $x$ and $f(i)$ will differ in their $i$th coordinate. This means that $x$ and $f(i)$ cannot be equal for any $i \in Z^+$. Thus $f$ is not a surjective function, or there exist members of $A$ that are not in the image of $f$.

This contradiction shows that A is not a countable set.

Answer 7

Several things that are taught, or implied by the way it is taught, about Cantor's Diagonalization are not correct. And they lead to misunderstandings like this one.

1) "Cantor wanted to prove that the real numbers are countable." No. Cantor wanted to prove that if we accept the existence of infinite sets, then the come in different sizes that he called "cardinality."

2) "Diagonalization was his first proof." No. His first proof was published 17 years earlier.

3) "The proof is about real numbers." No. The real numbers were the example he used in the first proof, but some other mathematicians objected to assumptions he made about them. So diagonalization explicitly did not. It used what I call Cantor Strings: infinite length strings of the characters "m" and "w." A similar proof can be used on real numbers, but it requires more steps that are often left out.

4) "It is a formal proof." No. It was an informal explanation of a more formal version, about power sets.

5) "Diagonalization is a proof by coontradiction." No, no, no. No. It is a proof by contraposition, which is similar but not the same. By proving "If A, then B" you also prove "If not B, then not A."

What diagonalization proves, is "If S is an infinite set of Cantor Strings that can be put into a 1:1 correspondence with the positive integers, then there is a Cantor string that is not in S." The contrapositive of this is "If there are no Cantor Strings that are not in the infinite set S, then S cannot be put into a 1:1 correspondence with the positive integers."