# Why Cantor's diagonal argument is logically valid?

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.

• Is your qualm with the claim that "if is it countable, we can construct a sequence", or with some other part? I'm not quite sure from your question. Commented Sep 29, 2017 at 21:30
• Exactly that one. Why can we construct such a sequence? Commented Sep 29, 2017 at 21:36
• 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. Is your question why we can be construct $(s(d_1), s(d_2), ...)$?
– D_S
Commented Sep 29, 2017 at 21:41
• @HeMan Isn't the definition of a countable set $S$ that there exists a bijection between $S$ and $\mathbb{N}$? In that case, we can simply let $a_i$ be the element of $S$ paired with $i$ in our bijection. Commented Sep 29, 2017 at 21:44
• @D_S that was exactly the answer i was looking for. Commented Sep 29, 2017 at 21:45

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, ...)$.

• As written, you need a bit of an argument to ensure the sequence you built is not on the list. Here is a silly example: Say all numbers in your list are $0.0999\dots$; then the sequence you built is $0.1000\dots$, which again is on the list. Commented Sep 30, 2017 at 1:31

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.

 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.

• You can find a translation of Cantor's paper at logicmuseum.com/cantor/diagarg.htm, confirming all that I said. Commented Sep 30, 2017 at 1:32