Constructive vs computable real numbers

Question

I find it confusing that all of the following statements are true :

1. The computable real numbers are countable. $-\hspace{-3pt}-$ Alan Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem"
2. In constructive analysis, the real numbers are uncountable. $-\hspace{-3pt}-$ Errett Bishop, Foundations of Constructive Analysis
3. "every mathematical statement [in constructive analysis] ultimately expresses the fact that if we perform certain computations within the set of positive integers, we shall get certain results" $-\hspace{-3pt}-$ Ibid.

Perhaps I am misunderstanding something.

I suppose I really have two questions. In constructive analysis :

1. Why isn't every real number computable?
2. How is it possible to construct an uncountable set?

Answer 1

A real number $x$ is computable if there exists a program $P(n)$ that on input $n$ outputs the decimal expansion of $x$ up to the $n$th digit. For example, $\pi$ is one such computable number - you can approximate $\pi$ as close as you want with a computer.

From this we can deduce $1$. Each computer program can be specified by a unique integer (it's binary representation), and hence there are a countable number of such programs, and therefore at most a countable number of computable real numbers.

However as $2$ says, the real numbers are uncountable. You can find a classical diagonalization proof of this fact here.

So if the real numbers are uncountable but computable numbers are countable then there must exist uncountably many real numbers which are not computable. Examples of uncomputable real numbers are rather exotic - they do not usually appear in natural problems.

However that does not mean they are sparse - indeed since every interval of the real line contains uncountable many numbers it must contain uncountable many uncomputable numbers. One example of an uncomputable number is Chaitin's constant.

The third statement you cite is the most sophisticated. Essentially, uncomputable numbers are not operational - you cannot use them in ordinary calculations. So for all practical purposes you could just work with the set of computable real numbers - and that is what constructive analysts do. Computable real numbers are algebraically closed - every reasonable operation you do with them will result in another computable numbers. That is the essence of the statement.

Regarding your question on how to build uncountable sets - if a set $S$ is countably infinite, then the set of all subsets of $S$ is uncountable. This is Cantor's theorem.

Answer 2

1.Because there is at least one real number that is not computable.

2. Step 1 : 0.0 , 0.1

Step 2 : 0.00 , 0.01 , 0.10 , 0.11

Step 3 : 0.000 , 0.001 , 0.010 , 0.100 , 0.011 , 0.101 , 0.110 , 0.111

step n : 0.(all combinations 1,0 of length n)

continue above indefinitely in binary to get all values in the interval 0,1.

Answer 3

1. It is consistent with the constructive analysis that every real is computable. (In fact, it is consistent with intuitionistic ZF $\mathsf{IZF}$.) This follows from that the consistency of Church's thesis, which claims every total function from $\mathbb{N}$ to $\mathbb{N}$ is computable.

   However, it does not mean constructive analysis can prove every real is computable. We know that classical analysis is a superset of constructive analysis (as a theory), that is, every statement that is provable from the constructive analysis is also a theorem of the classical analysis. And classical mathematics proves not every real is computable. Hence it would be accurate to say whether every real is computable is independent of constructive analysis.

   To add some comment, I think it does not mean Bishop is simply wrong. Bishop's constructive analysis is minimal in the sense that it is contained in classical analysis, Brouwer's intuitionistic mathematics, and Recursive constructive analysis (also known as Russian constructivism.) The latter one reflects the behavior of recursive mathematics, so Bishop's claim would be true in that sense.

2. $\mathbb{R}$ is uncountable in the sense that there is no bijection between $\mathbb{N}$ and $\mathbb{R}$. The proof is available from Bishop's Constructive analysis. (Theorem 2.19 of Bishop and Bridges.) Here is a rough proof:

   Theorem. There is no bijection from $\mathbb{N}$ to an interval $[x_0,y_0]=\{z\in\mathbb{R}\mid x_0\le z\le y_0\}$. (Caution: $x\le y$ is not ($x< y$ or $x=y$.))

   Proof. The proof uses diagonalization argument. Assume that $f:\mathbb{N}\to\mathbb{R}$ is a function. We will find a Cauchy real $x\in [x_0,y_0]$ such that $f(n)\neq x$ for all $n$. We will construct sequences of natural numbers $(x_n)$ and $(y_n)$ recursively such that

   1. $x_0\le x_n\le x_m<y_m\le y_n\le y_0$ if $1\le n\le m$,
   2. $x_n>f(n)$ or $y_n<f(n)$, and
   3. $y_n-x_n<1/n$.

   Assume that $x_i$ and $y_i$ are given for all $i<n$. Then we have either $f(n)>x_{n-1}$ or $f(n)<y_{n-1}$. (This follows from the following constructively valid theorem: if $x<y$ are reals, then either $z<y$ or $x<z$.)

   Assume that we have $f(n)>x_{n-1}$. (The remaining case is analogous.) Choose a rational number $x_n$ and $y_n$ such that $x_{n-1}<x_n<\min(a_n,y_{n-1})$ and $x_n<y_n<\min(a_n,y_{n-1},x_n+1/n)$. Then the mentioned inequalities are satisfied.

   Hence $(x_n)$ forms a Cauchy sequence of rational numbers. Let $x$ be a limit of $(x_n)$, then $x$ satisfies the desired properties.

   Note that the above proof makes use of the countable choice that Bishop accepted. As far as I know, it is open whether $\mathbb{R}$ is countable or not without the countable choice. Also, note that $\mathbb{R}$ can be subcountable, i.e. $\mathbb{R}$ can be an image of a subset of $\mathbb{N}$. (Unfortunately, I forgot whether the subcountability of $\mathbb{R}$ is compatible with $\mathsf{IZF}$, although I believe it is true.)