# Applying cantor diagonal argument recursively: How to show the resulting construction is incomplete?

Recall that cantor diagonal argument basically asked to list out the table of all countable binary strings, and showing how regardless of what list you start with, there's always a diagonal element that is not enumerated in the list, thus proving the reals have larger cardinality.

\begin{matrix} 00001...\\ 10101...\\ 11001...\\ 11000...\\ 11010...\\ \vdots \\ \text{pick}: 00000\\ \end{matrix}

But suppose we iterate this process as follows:

2. Use the diagonal argument to pick out the diagonal element that is not in the list of binaries
3. Place the new element at the beginning of the list of binaries
4. Repeat until no new diagonal can be picked out.

Since this is expected to iterate indefinitely, can a proof by transfinite induction allow us to deduce whether such procedure can enumerate all countable binary strings. what is the step required to set up this proof?

Alternately, since any algorithm in a computer can only run for finite number of steps, what is the approach used to find a counterexample of this conjecture?

• This procedure can't give an enumeration of all binary strings (i.e. a bijection between these strings and $\mathbb{N}$) since Cantor's argument is valid. I suspect that the difficult issue here is that there is no obvious way to "repeat" your steps transfinitely, in particular at countable limit ordinals. After you repeat it $\omega$ many times, it would be natural to interleave the initial list with the new strings obtained from diagonalization, just as joriki says. Then you could continue diagonalizing. But what do you do at stage $\omega_2$? $\omega_\omega$? Commented Jun 22, 2018 at 4:03
• In general you would need a procedure for taking an arbitrary countable limit ordinal $\alpha$ and outputting a bijection between $\alpha$ and $\mathbb{N}$. This brings up some profound issues. I think Tarski had a proof that no such procedure could be "computable" in some sense (my memory is vague here though). Commented Jun 22, 2018 at 4:15