1
$\begingroup$

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:

  1. Start with a list of binaries
  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?

$\endgroup$
2
  • $\begingroup$ 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$? $\endgroup$
    – Doug McLellan
    Commented Jun 22, 2018 at 4:03
  • $\begingroup$ 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). $\endgroup$
    – Doug McLellan
    Commented Jun 22, 2018 at 4:15

1 Answer 1

Reset to default
0
$\begingroup$

You're not gaining anything new by this method. If it terminates, you just end up with a standard list, and you already know how to prove that that can't be complete. If it doesn't terminate, it produces a "two-sided list", infinite in both directions, which you can easily map to a standard list by cutting it at some point and interleaving the two resulting lists. So again you already know how to prove that this can't be complete.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .