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

Question

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.

Answer 1

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.

Answer 2

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.