Chaitin's famous incompleteness theorem states that for every r.e. theory $T\supseteq Q$ in the language of arithmetic, there is a constant $d_T$ such that for any $m\geq d_T$ and any $x$, $T$ can not prove the sentence $K(x)\geq m$ ($K$ is the kolmogorov complexity function). The constant $d_T$ is constructed in such a way:

Let $M_{i_0}$ to be the Turing machine that enumerates the theorems of $T$ and $| M_{i_0}|$ denote the length of this machine. Now if $T$ prove a sentence $K(x)\geq m$, then we can write an algorithm to search for such a $x$ and print the first one. The length of this algorithm is $| M_{i_0}|+\lceil log(m) \rceil+e$ where $e$ is a constant. For sufficiently large $m$'s we have $| M_{i_0}|+\lceil log(m) \rceil+e<m$ so $K(x)<m$, contradicting consistency of $T$. Hence we can choose $d_T$ as the least integer solution for the inequality $| M_{i_0}|+\lceil log(m) \rceil+e<m$.

The Chaitin constant of $T$ is defined as the least constant $c_T$ such that $T$ can not prove any sentence of the form $K(x)\geq c_T$ (see, e.g. this paper).

My question is about the relation between the two constant $c_T$ and $d_T$. Obviously $c_T\leq d_T$ but can they be equal or $c_T$ is always strictly smaller than $d_T$ ? (We know that Kolmogorov complexity has different definitions and so we can ask if the answer depend on the choice of definition).

  • $\begingroup$ This is a nice (and quite tough) question! An analogous question is: "is the Gödel sentence for $T$ the smallest sentence which is true but not provable in $T$?" This is obviously false for specific theories like $\mathrm{PA}$ where we have concrete examples of short undecidable statements, and likely to be false in general, but I suspect that you can carefully choose theories so that that is the shortest undecidable statement (say, by cleverly adding axioms that decide all shorter statements). $\endgroup$ – cody Mar 23 '16 at 20:29
  • $\begingroup$ @cody As you mentioned, in general, Godel sentence is not the smallest Pi_1 sentence which is unprovable in a theory and it can be proved as follows: $\endgroup$ – Payam Seraji Mar 26 '16 at 14:39
  • $\begingroup$ @cody We first note that "the smallest $\Pi_1$ sentence not provable in T" is not computable from description of T, because if it was so, by adding this sentence to T and iterating this work ω-times, we should have a r.e. and $\Pi_1$-complete theory which contradicts the incompleteness theorem. Godel sentence of T is obviously computable from description of T, so for infinitely many theory T, Godel sentence is not the smallest $\Pi_1$ undecidable sentence. $\endgroup$ – Payam Seraji Mar 26 '16 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.