Is Chaitin’s constant well-defined

computabilitydefinitionlogic

Chaitin's constant is this amazing example of a real number that we can define, however we can not compute. However, I have a doubt in the claim that the constant is well-defined.

If I understand correctly, however this might very well be the part where I'm wrong, the way Chaitin's constant is defined is by defining a sequence of programs, and then defining the $i$'th binary digit of our number to be $1$ if the $i$'th program halts, and $0$ otherwise. If this sequence enumerates every program, then, because the halting problem is provably undecidable, the constant is uncomputable.

My problem lies in the claim that every program either will halt or not. Take for example the algorithm that enumerates every even natural number greater than $2$ and tries to write it as the sum of two primes, until it finds a number that can not be written this way, at which point it will halt. This program will halt if, and only if, the Goldbach conjecture turns out to be wrong. However, we do not even know if the Goldbach conjecture might be independent of ZFC. If the Goldbach conjecture is independent of ZFC, then is the digit of Chaitin's constant corresponding to this program well-defined?

Even if the Goldbach conjecture turns out to be dependent of ZFC, I doubt that the halting problem is dependent of ZFC for every fixed program.

EDIT: So this apparently depends on the definition of a definable number. A number does not have to be dependent of your universe to be definable. However, then the following follow up question comes to my mind.

If we define a super-definable number to be a number both definable and dependent of ZFC, does there exist a super-definable uncomputable number? Is this known?

EDIT 2: I mean "dependent of ZFC" to say there is a string of symbols in ZFC that determines the value of each digit. But then we can write a program iterating through all strings of symbols until it finds such a string, so the number is computable.

Best Answer

Look at the number $x\in[0,1]$ whose $n$th digit is $0$ if and only if $2^{\aleph_n}=\aleph_{n+1}$ and $1$ otherwise. This is certainly a definable real number, I just defined it, but it is consistent to be $0$ and it is consistent to be $1$, and in fact, it is consistent to be any other number whose decimal expansion is only $0$ and $1$. Being definable means you are constant within a fixed universe of your theory. It means it is provably a fixed number. But what is the value? That might depend on your universe.

Or, you know, just take $x=\begin{cases}0 &\rm CH\\ 1 &\lnot\rm CH\end{cases}$ also works.

The key thing to understand is that being definable is Platonistically-constant, but not necessarily constant if you allow for a more multiversial approach (or even a more formalistic approach) to mathematics.


But this is very much like saying that $\pi_d$ is half of the length $\{x\in\Bbb R^2\mid \|x\|_d=1\}$, when $d$ is a metric on $\Bbb R^2$. It will invariably depend on the metric you choose.