[Math] Why does Cantor’s diagonal argument yield uncomputable numbers

real-analysisset-theory

As everyone knows, the set of real numbers is uncountable. The most ubiquitous proof of this fact uses Cantor's diagonal argument. However, I was surprised to learn about a gap in my perception of the real numbers:

A computable number is a real number that can be computed to within any desired precision by a finite, terminating algorithm.

Turns out that the set of computable numbers is countable. My mind is effectively blown at this point.

So I'm trying to reconcile this with Cantor's diagonal argument. Wikipedia has this to say: "…Cantor's diagonal argument cannot be used to produce uncountably many computable reals; at best, the reals formed from this method will be uncomputable."

So much for background information.

Say I have a list of real numbers $.a_{1n}a_{2n}a_{3n}\ldots$ for $n\geq 1$. Why do we get more than just computable numbers if we select digits different from the diagonal digits $a_{ii}$? I.e. if I make a number $.b_1b_2b_3\ldots$ where $b_i\neq a_{ii}$, why is this number not always computable?

The main issue I'm having is that it seems like I'm "computing" the digits $b_i$ in some sense. Is the problem that I have a choice for each digit? Or is there some other subtlety that I'm missing?

Best Answer

You are only computing the digits $b_i$ relative to the given enumeration $a_{i,n}$. So if the function $f(i,n) = a_{i,n}$ is computable then the $b$ you construct is also computable, and not equal any of the reals $a_i$. However, if you have no way to compute the digits $a_{i,n}$ then you can't compute $b$ either. It only seems like you are computing $b_i$ because you are assuming that you already have a way to compute the digits $a_{i,n}$.

However, there is no computable function $f(i,n)$ that satisfies these three requirements:

  • for any $i$ and $n$, $f(i,n)$ eventually returns some output. In other words, $f(i,n)$ is a total function
  • for every $i$, the function $n \mapsto f(i,n)$ gives a decimal expansion of a real number
  • for every computable real $a$ there is some $i$ with $a_n = f_{i,n}$ for all $n$

The diagonalization argument is actually the "standard" way to prove there is no $f(i,n)$ with those properties. If there was, then the $b$ you get from it would be another computable real, which is impossible.

Working in set theory, you can do the construction with a noncomputable function $f(i,n)$ which lists every computable real. Since this $f$ is not computable, $b$ need not be computable, and in fact it won't be if $f$ lists all the computable reals.

Related Question