# Cantor's Diagonal Argument - How Does It Establish Different Cardinalities of Infinite Sets?

I take it for granted Cantor's Diagonal Argument establishes there are sequences of infinitely generable digits not to be extracted from the set of functions that generate all natural numbers. We simply define a number where, for each of its decimal places, the value is unequal to that at the respective decimal place on a grid of rationals (I am here ignoring the "no 0's or 9's" failsafe).

What I cannot understand is how the argument forces the conclusion the set of reals has a greater cardinality than the naturals.

After all, infinite sequences of digits defined by diagonalization are parasitic on digit values on the grid of rationals. If we accept that one-to-one correspondence is the criterion of equal cardinality, can't we correlate any sequence generated by diagonalization with the respective decimal values on the grid used to produce all rational numbers' decimal expression?

I know one-to-one correspondence can be used to show equal cardinality between sequences of apparently (to non-specialists) different cardinalities: x, x+1, x+2... can be correlated with 9x, 9(x+1), 9(x+2)... But were we to choose a base 2 number system, wouldn't Cantor's diagonal be literally one-to-one with diagonal sequence on the list it is produced from? Like, if the grid read 1,0,1,1,0,1,0... then the Cantor diagonal would read 0,1,0,0,1,0,1...

The hypothesis I'm hoping to be corrected on is that diagonalization produces sequences in ways counting cannot. These sequences are uncountable, but not uncountably many, distinct from the natural numbers but not more numerous than them.

I looked around for other posts where the question in the title was answered but found none.

• Can you explain what you mean by "parasitic on digit values on the grid of rationals"? – qaphla Dec 31 '13 at 4:23
• I meant that the Cantor diagonal is dependent for its content on a sequence of digits found on a diagonal of the list of rationals. So all those values for decimal places on that list of rationals? Cantor defines a new sequence where all values are not equal to those respective decimal places in the original sequence – booboo Dec 31 '13 at 4:36

## 2 Answers

It works like this:

Theorem: Let $f$ be any function from the natural numbers to the real numbers. There exists a real number $a$ such that $a \neq f(n)$ for every natural number $n$.

Corollary: There does not exist a surjective function from the natural numbers to the real numbers.

• That expresses a conclusion. I'm looking for an explanation. – booboo Dec 31 '13 at 4:17
• @booboo The corollary is the definition of the real numbers having greater cardinality than the naturals. Do you not understand the proof of the theorem, or how the corollary follows from it? – Alex Becker Dec 31 '13 at 4:23
• I'm looking for an explanation that addresses the questions I asked. The theorem expresses what Cantor is supposed to have proven in a more or less formal way. It says that there are numbers that cannot be generated from the naturals, something my post took as its starting point. I could perhaps ask what causes the leap from the Theorem to the Corollary. I'm entertaining the idea that the function is in fact bijective. Any way that idea can be shown to be off course would be appreciated. – booboo Dec 31 '13 at 4:32
• @booboo: It doesn't say that there are numbers that cannot be generated from the naturals (whatever that might mean): it says that, for any function from the naturals to the reals, there is a real that is not in the image of that specific function. We also have the somewhat more trivial theorem For any real number a, there exists a function f from the natural numbers to the real numbers, along with a natural number n, such that f(n) = a. – user14972 Dec 31 '13 at 4:45
• @booboo: Dear booboo, The answer to your last question is "yes", but it is a vacuous answer; the natural numbers and reals are not in bijection. If you look at the statements of the theorem and corollary in Hurkyl's answer, they say there is no surjection from the naturals to the reals. (The corollary says this explicitly; the theorem says the same thing, but in a slightly more technical way, by unwrapping what surjection means.) A fortiori, they can't be put into 1-1 correspondence. However much you talk about it, there's no getting around that fact. Regards, – Matt E Dec 31 '13 at 5:32

I think a lot of confusion about Cantor's diagonalization argument arises from the fact that it is frequently conveyed in contexts wherein many of the readers are not familiar with the basic structure of a mathematical proof; I'll try to describe the reasoning steps and then present a proof. If we're only interested in showing there are distinct cardinal infinities, we can avoid the minor issue of uniqueness of representations of real numbers by considering functions from the set of natural numbers (which we denote by $\mathbb{N}$) to the set of binary sequences. Slightly informally, we may think of a binary sequence as an object of the form $(x_1, x_2, \ldots)$ wherein either $x_i = 0$ or $x_i = 1$ for each $i\in\mathbb{N}$. We say that two binary sequences $(y_1, y_2, \ldots)$ and $(z_1, z_2, \ldots)$ are equal if and only if $y_i = z_i$ for each $i\in\mathbb{N}$.

We want to show the following: every function from $\mathbb{N}$ to the set of binary sequences fails to map to at least one binary sequence (so that $f$ is not surjective by definition). We will prove this assertion in the next paragraph by fixing such a function $f$ and constructing a binary sequence to which $f$ fails to map. Since $f$ is arbitrary, we may conclude that our assertion holds for any such function. Note that although the procedure implied by the proof may generate different unmapped sequences for different functions, it guarantees the existence of some such sequence for any function from $\mathbb{N}$ to the set of binary sequences. Recall that by definition, two sets have the same cardinality if and only if a one-to-one correspondence exists between them; our argument implies that every function between the aforementioned sets fails to be a one-to-one correspondence.

With these preliminaries in mind, let's carry out a proof and see if it makes more sense. Let $f$ be an (arbitrary fixed) function from $\mathbb{N}$ to the set of binary sequences. For every natural number $i$, we may write $f(i)=(a_{i1}, a_{i2}, \ldots)$. Now define a binary sequence $(b_1, b_2, \ldots)$ for each $i\in\mathbb{N}$ by putting $b_i=0$ if $a_{ii}=1$ and $b_i=1$ if $a_{ii}=0$. Then if $i\in\mathbb{N}$, $b_i \neq a_{ii}$; hence, $f(i)=(a_{i1}, a_{i2}, \ldots)\neq(b_1, b_2, \ldots)$ (since these sequences differ at their $i$-th terms). Thus, $f$ does not map any natural number to $(b_1, b_2, \ldots)$.

The diagonal argument for the reals (which is not the only proof) is similar; we use the fact that the reals can be represented using sequences of digits.