Why Cantor's diagonal argument is logically valid?

Question

Cantor's diagonal argument goes like this: We suppose that the real numbers are countable. Then we can put it in sequence. Then we can form a new sequence which goes like this: take the first element of the first sequence, and take another number so this new number is going to be the first number of your new sequence, etcetera.

My question is, why can we construct such a sequence? What is the logical argument? Some people say that is a construction, I'm aware of that, but I'm asking why that sequence can be constructed.

Answer 1

Let $(d_1,d_2, ...)$ be the sequence obtained by taking the first digit of the first number, the second digit of the first number, etc. Define

$$s: \{0, 1, ... , 9\} \rightarrow \{0, 1, ... , 9\}$$

by $s(x) = x+ 1$ if $x \neq 9$, and $s(9) = 0$. Then your new sequence is

$$(s(d_1), s(d_2), ... )$$

which cannot be on the original countable list.

To me, it's obvious that you can "construct" the above sequence and work with it. If you're not convinced, we can do things more formally as follows. Let $P = \{0, 1, ... , 9\}$. We have the function $s: P \rightarrow P$ I mentioned. Consider the cartesian product

$$\mathbf P = \prod\limits_{i=1}^{\infty} P$$

together with the projections $\pi_i: \mathbf P \rightarrow P, i = 1, 2, ...$. Then every decimal sequence $\mathbf e = (e_1, e_2, ...)$ is an element of $\mathbf P$, and $\pi_i$ is just the map which sends such a sequence to $e_i$. The universal property of the cartesian product guarantees the existence of a unique function

$$\mathbf s: \mathbf P \rightarrow \mathbf P$$

with the property that $\pi_i \circ \mathbf s = s \circ \pi_i$ for every $i$. Then

$$(s(d_1), s(d_2), ... )$$

is nothing more than the function $\mathbf s$ applied to $(d_1, d_2, ...)$.

Answer 2

What gets taught as Cantor's argument, is not what Cantor argued. And in my experience, most issues people have with it stem from the misrepresentations.

Cantor started with the set of of what I call Cantor Strings, not the set of all real numbers. They are infinite length binary strings. In fact, his express purpose was to prove that there are uncountable sets without using irrational numbers.

Then, he assumed that it is possible to count some subset of his set, not the entire thing. This is easy to demonstrate, with {'100000...', '010000..., '001000...', ...}.

Finally, what diagonalization proves, is that if a subset is countable, then it is not the entire set. By contraposition, not contradiction, this proves that if a set is the entire set, then it is not countable.

[Edit] Now, to better address your question. "To construct" doesn't have to mean that you produce a sequence of steps that terminates. In set theory, it is enough to define a function that produces the object. So, for example, the function "For every n, CS(m) = '1' if n=m, and CS(m)='0' is n!=1" constructs the mth Cantor String in my example above.

When Cantor assumes that there is a subset of Cantor Strings that can be counted, what he really means is that there is a function S(n) that returns a unique Cantor String for every natural number n. We don't care what that function is, but we assume it exists. But if it does, there must be a related function, the diagonalization function, that constructs a Cantor String that S(n) cannot.