Cantor's diagonal argument, is this what it says?

Question

I've been reading about Cantor's diagonal argument all day, it's pretty confusing, but I think I get it now and I want to make sure asking you guys to confirm it. So, this is my understanding:

Two sets, $A$ and $B$ have the same size if and only if there exists a one-to-one function that maps $A$ onto $B$.

A set $A$ is countably infinite if and only if there exists a one-to-one function that maps $A$ onto $ℕ$.

Now, if we want to show that the set $ℝ$ does not have the same cardinality as $ℕ$ and that "it's larger", from the above definition, we have to prove that there does not exists a one-to-one function that maps $ℕ$ onto $ℝ$ (or equivalently that $ℝ$ is not countably infinite).

We proceed by contradiction: We suppose there exists a one-to-one function that maps $ℕ$ onto $ℝ$.
All these are real numbers $f(1), f(2), f(3), …, f(n), …$
we arrange these numbers in this way: \begin{matrix} f(1)=\:.\pmb{a_{11}}a_{12}a_{13}a_{14}…\\ f(2)=\:.a_{21}\pmb{a_{22}}a_{23}a_{24}…\\ f(3)=\:.a_{31}a_{32}\pmb{a_{33}}a_{34}…\\ …\\ f(n)=\:.a_{n1}a_{n2}a_{n3}a_{n4}…\\ ... \end{matrix} where all the $a_{ij}$s represent random numbers from $0$ to $9$ (note the period at the beginning, it means that there should be another number there, like a normal decimal).

Now if we find a number that is not in that list it means 2 things (which is actually the same thing):

1 - The function is not bijective (since at the beginning we supposed that there exists a one-to-one function that maps $ℕ$ onto $ℝ$ every element of $ℝ$ should have an element of $ℕ$ mapped to it, and we found an element of $ℝ$ that doesn't have one, since it's not in the list).
2 - That the set $ℝ$ is not countable, both because we can't "list them" (that list should represent every real number, but we missed one) and because that function is not bijective.

To find this number that is not in the list we choose a number that should be in that list, let's say number $y$, which since it has to to be real number it has the form of a decimal: $y=\:.y_1y_2y_3y_4…$ where again all the $y_i$s are numbers between $0$ and $9$, now to make different from all the other numbers, the trick is:
Let the first digit $y_1$ be different from the first digit of the first number of that list, namely $a_{11}$, the second digit $y_2$ be different from the second digit of the second number of that list, namely $a_{22}$, $y_3$ different from $a_{33}$ and so on, so we will have a number that has at least 1 different digit from all those numbers and therefore it's none of those numbers, but at the same time since it's a decimal it should be in that list so we have a contradiction and we proved the 2 points, so in the end, even though $ℕ$ and $ℝ$ are both infinite they dont have the same number of elements, $ℝ$ has more since some elements "stay free" even after we paired every element of $ℕ$ with some element of $ℝ$.

Is this correct? I tried to explain it in the best way i can, i really hope it makes sense.. and please don't close the question, i know that there are a lot of questions about Cantor's diagonal argument but i can't be 100% sure i understand it if i don't write it down and someone confirms it. Thank you so much!

Answer 1

The argument works as follows:

• you tell me your would-be bijection by listing the numbers in the order induced by that bijection;

• I am able to exhibit a number which is not in your list: I take for the first decimal a digit different from the first decimal of the first number; then a digit different from the second decimal of the second number, and so on.

By the construction principle, that real differs from all reals the list by at least one decimal, hence your bijection is incomplete.

As this "works" with any bijection, no bijection can exist.

---

Illustration:

$$0.\color{green}584669954\cdots\to0.6$$ $$0.3\color{green}62587745\cdots\to0.67$$ $$0.88\color{green}7459552\cdots\to0.678$$ $$0.336\color{green}528454\cdots\to0.6786$$ $$0.9549\color{green}24584\cdots\to0.67863$$ $$\cdots$$

Answer 2

Many concepts we think we learned in kindergarten become hard to define with infinite sets. “Size” is one, as is a “one-to-one function” (an injection; note that this definition looks at only one direction) or a “one-to-one-to-one” function (a bijection.) The problem is that with finite sets, if there is an injection from A to B that isn’t a surjection, then no injection is a surjection. In kindergarten, that’s what you learned “larger” meant. This is not true with infinite sets, so the definition of “larger” can’t involve finding just one example.

So Cantor wanted to show that there was a set that had no sujection from N. Several things might surprise you about his proof. The set he used was deliberately not the reals; he used infinite-length binary strings. The same argument can work with reals, but it needs some extra details. He also did not assume he had either a surjection or an injection, nor did he use contradiction as you were taught.

All he tried to prove was that an surjection was impossible. Here’s a rough outline, which is a little different than yours. Call the set of all such strings T:

1. Assume a function f:N->T exists. (Examples are trivial to construct.)
2. Let S be the subset of T that is mapped by f(n).
3. Diagonalization constructs a new string t0 that is in T, but not in S.
4. Conclude that any function f:N->T is not a surjection.

Cantor did add a fifth step, which loosely translated was “It follows immediately that there cannot be an injection from N to T. Otherwise, we would have the contradiction, that t0 would be both an element of T, but also not an element of T.” This is really just an interpretation of my step 4, not a formal proof by contradiction.

A similar outline of your version of the proof would be:

1. Assume a bijection f:N->T exists.
2. Let S be the subset of T that is mapped by f(n). (By the assumption, it is an improper subset and S=T.)
3. Diagonalization constructs a new string t0 that is in T, but not in S.
4. Step 3 contradicts the assumption in step 1, so that assumption is proven false.

This is an invalid proof, but most people don’t seem to see what is wrong with it.

In order to disprove an assumption by contradiction, you have to actually use all parts of that assumption to derive the contradiction. Say you assume that the square root of 2 is rational AND that the moon is made of green cheese. You can use only the first part of this assumption to derive the contradiction that an odd number equals an even number. But you haven’t proven anything about what kind of cheese there is on the moon, even though you said you assumed it was green.

Step #3 in the second outline I gave uses only the assumption that there is a function from N to T. It does not use the assumption that it is a surjection, nor that it is an injection. But step #3 does prove, directly, that it is not a surection.