[Math] Example of uncomputable but definable number

computabilityreal numbers

Every computable number is definable. However, the converse is not true.
What is an example of a real number that is definable but that is NOT computable? I guess if it is there, we can "define" (describe) it, can't we?

Best Answer

The point here is that definable real numbers are definable using the entire strength of might of the set theoretic universe; whereas computable real numbers are only allowed to access the natural numbers and their very very very rudimentary properties (since computable functions are only $\Sigma_1$ definable functions over $\Bbb N$).

Let $\varphi_n$ enumerate the sentences in the language of arithmetic. Now consider the real number whose $n$-th digit in the decimal expansion is $1$ if and only if $\Bbb N\models\varphi_n$, and $0$ otherwise. So it is a number in $[0,1]$.

This number is of course definable in the language of set theory, since the set of true sentences in $\Bbb N$ is definable; but it is not a computable real number since there is no computable function telling us what is true in $\Bbb N$ and what isn't (not even arithmetical, to be more accurate).


We can also take the following approach, as I suggest in the comments to the original question.

Note that every computable real lies in $L$, by absoluteness arguments (every computable functions lies there), and in $L$ there is a definable well-ordering of the reals (even with a $\Delta^1_3$ definition!), so there is a least real in the canonical well-ordering which is not definable.

Since the set "the real numbers which also lie in $L$" cannot change between models of $\sf ZF$ with the same ordinals, this set always has a canonical, definable well-ordering in any model of $\sf ZF$, and this indeed gives us a definition of a real number which is non-computable.


You can also argue that various generic reals are non-computable but definable, if you're willing to go this far as to consider different set theoretic universes (or at least one which can be seen as a nontrivial generic extension of some inner model).

For example Jensen reals are definable (they are the unique solution to a $\Pi^1_2$ predicate) but not computable.

Similarly, you can consider the iterated forcing that at the $n$-th step does the lottery sum between forcing $2^{\aleph_n}=\aleph_{n+1}$ and forcing $2^{\aleph_n}=\aleph_{n+2}$, at the limit step take a finite support limit, and consider the real number whose $n$-th decimal digit $1$ if and only if $2^{\aleph_n}=\aleph_{n+1}$, and $0$ otherwise.

This is a Cohen real which is definable, since it encodes the continuum below $\aleph_\omega$; but of course it is not computable by genericity arguments.

Note that this gives a very peculiar example of a real number, the one encoding the continuum function below $\aleph_\omega$. It is always definable, but in different models of $\sf ZFC$ it wil have different values, sometimes they will be computable (e.g. if $\sf GCH$ holds) and sometimes they could be non-computable (as above).

So this gives us a definition of a real number which is not provably computable and not provably uncomputable!

Related Question