# How to interpret “computable real numbers are not countable, and are complete”?

On page 12 of this (controversial) polemic

http://web.maths.unsw.edu.au/~norman/papers/SetTheory.pdf

Wildberger claims that

Even the "computable real numbers" are quite misunderstood. Most mathematicians reading this paper suffer from the impression that the "computable real numbers" are countable, and that they are not complete. As I mention in my recent book, this is quite wrong. Think clearly about the subject for a few days, and you will see that the computable real numbers are not countable, and are complete. Think for a few more days, and you will be able to see how to make these statements without any reference to "infinite sets"...

These claims are false, as far as I can tell, with the usual definitions. Is there a reasonable way to interpret them---more specifically, do they become true after replacing "countable" by "computably enumerable" and doing something similar with "complete", requiring only sequences that are "computably Cauchy" (feel free to modify my provisional definition below if convenient) to converge? I know nothing about computable real numbers, so I will appreciate it if you are gentle!

Provisional definition: A sequence $a_n$ is computably Cauchy if there is a computable function $f: \mathbb{Z}_{> 0} \rightarrow \mathbb{Z}_{> 0}$ such that $|a_k-a_m|<1/n$ if $k,m \geq f(n)$.

• But computable numbers are countable... en.wikipedia.org/wiki/Computable_number – Dave Jun 12 '13 at 0:26
• @Steve, sorry, I meant the question the author poses. He kind of advocates a "set theory" in which axioms are implicit, naively thought to be "obvious", and where an infinite set has no role, just like an "all-seeing leprechaun". – Ferdinand.kraft Jun 12 '13 at 0:58
• Well, it seems to me like most of the paper makes sense if you define "mathematics" as something like "the study of the behavior of computer programs"—*real* computer programs, running on actual computers, not on Turing machines. Adjusting other terms appropriately, the computable real numbers are "uncountable" in a sense (you can't write a computer program that lists each one exactly once), and "complete" in a sense (since all we're talking about is computer programs, we're denying the existence of uncountable real numbers). I have no idea if this is what Wildberger actually had in mind. – Tanner Swett Jun 12 '13 at 0:59
• All, don't take this the wrong way: I understand that Wildberger rubs people the wrong way. I would really appreciate it if you would not take it out on me. I asked a precise mathematical question. If you feel it requires more clarification, I will be happy to clarify it. – Stephen Jun 12 '13 at 1:03
• To try to (roughly) justify the statement, perhaps he means that the computable reals are not 'countable' in the sense that there's no computable bijection between integers and computable reals? As long as you're working within the world of computability (and not looking from the 'outside view') then it makes sense to take a computable definition of countability too, and 'has a computable bijection with the integers' seems a legitimate definition of countability that would make the initial statement make sense. – Steven Stadnicki Jun 12 '13 at 1:05

Here we have two assertions. Uncountability and completeness.

In the usual set theoretic tradition computable real numbers are countable since there are only a countable quantity of Turing Machines. Funnily, you can show using Cantor's diagonal argument -the same that it is used to show that real numbers are not countable- that this bijection from the natural numbers to the real computable numbers is non-computable. If you have such a computable bijection, you can compute a real number that is not in the range of this computable function by diagonalization.

Thus real computable number are countable, but not effectively countable, i.e. you cannot give a computable bijection from the natural numbers onto the real computable numbers.

About completeness, Specker sequence using the fact that there are recursively enumerable sets that are not recursive/decidable. Take one of those sets $A\subset \mathbb{N}_1$, and consider an enumeration of it given by $$a:\mathbb{N}\rightarrow A$$ And so consider the number $$S_A=\sum_{n\in \mathbb{N}}\frac{1}{2^{a(n)}}$$ Then this number is the supremum of the family of computable numbers $\{S_{A,n}\}_{n\in\mathbb{N}}$, where $S_{A,n}$ is given by $$S_{A,n}=\sum_{i\leq n}\frac{1}{2^{a(i)}}\text{,}$$ but $S_A$ is not computable. (If it were computable, then $A$ would be recursive.) Thus we don't have completeness natural sequences of computable numbers.

However, in the previous example we cannot say that everything is done. If we define a computable Cauchy sequence of computable real numbers as a computable sequence of computable real numbers $\{q_n\}_{n\in\mathbb{N}}$ such that there is a computable function $$r:\mathbb{N}_1\rightarrow \mathbb{N}$$ such that for every $n\in\mathbb{N}_1$, for all $i,j>r(n)$, $$|q_i-q_j|<1/n$$ Then the resulting limit can be shown to be a computable real number, and thus having a sort of computable completeness.

The previous two things are the facts, thus we have some sort of uncountability, if we add the requirement of computability to the bijection, and a sort of completeness, strengthening the requirements of the definition-. This has to be said that are results very similar to those of Bishop's constructive analysis.

The article you linked seems to me one of those people angry with the infinity and that thinks that mathematics have to be limited to what they think is philosophically valid. However, mathematics is free product of our mind (paraphrasing Dedekind) and thus we have to learn to enjoy it in all its forms since all of them gives us a broader view of the subject.

EDIT: For the affirmation that the computable Cauchy sequence $\{q_n\}_{n\in\mathbb{N}}$ converges to a computable real number $q$ we only have to give an algorithm (Turing machine) that calculates the binary expansion of this number.

Remember that a number $x$ is computable if there is a computable function $$f_x:\mathbb{N}_1\rightarrow \mathbb{Q}$$ such that for all $n\in\mathbb{N}_1$, $$|f_x(n)-x|<1/n$$

Now, given our computable sequence, this fact is translated that we have a computable function $$f:\mathbb{N}\times\mathbb{N}_1\rightarrow \mathbb{Q}$$ such that for all $n\in\mathbb{N}$ and $i\in\mathbb{N}_1$, $$|q_n-f(n,i)|<1/i$$

Now, since this sequence is Cauchy computable, we have that there is a computable function $$r:\mathbb{N}_1\rightarrow \mathbb{N}$$ such that for every $n\in\mathbb{N}_1$, for all $i,j>r(n)$, $$|q_i-q_j|<1/n$$

This fact will be essential for showing that the limit is computable in the considered case. Now, using classical analysis to show that for the limit $q$ we have that for every $n\in\mathbb{N}_1$, for all $i>r(n)$, $$|q_i-q|<2/n$$

In this way, the desired computable function for approximating $q$ is given by $$h(n)=f(r(4n)+1,2n)$$

• Thanks +1; do you have a reference for the fact about computably Cauchy sequences converging to computable numbers? (Or better, can you give a quick proof?) – Stephen Jun 12 '13 at 1:13
• @Steve There is the proof. – Josué Tonelli-Cueto Jun 12 '13 at 2:55