5
$\begingroup$

I want to ask if it is possible to deduce Godel's first incompleteness theorem from Chaitin's incompleteness theorem. I am reading the following AMS-Notice article. The authors claim that:

The main conceptual difficulty in G¨odel’s original proof is the self-reference of the statement “this statement has no proof.” A conceptually simpler proof of the first incompleteness theorem, based on Berry’s paradox, was given by Chaitin.....

But the statement they proved is the Chaitin's incompleteness theorem, which appeared different from the Godel's first incompleteness theorem. They also contendeded that:

A different proof for G¨odel’s first incompleteness theorem, also based on Berry’s paradox, was given by Boolos [Boolos89] (see also [Vopenka66, Kikuchi94]). Other proofs for the first incompleteness theorem are also known (for a recent survey, see [Kotlarski04]).

Does this mean that Chaitin's incompleteness theorem implies Godel's first incompleteness theorem? I ask at here as I feel kind of confused with the logical relationship.

The authors also made a dubious claim that:

G¨odel considered the related statement “this statement has no proof.” He showed that this statement can be expressed in any theory that is capable of expressing elementary arithmetic. If the statement has a proof, then it is false; but since in a consistent theory any statement that has a proof must be true, we conclude that if the theory is consistent, the statement has no proof. Since the statement has no proof, it is true (over N). Thus, if the theory is consistent, we have an example for a true statement (over N) that has no proof. The main conceptual difficulty in G¨odel’s original proof is the self-reference of the statement “this statement has no proof.”

which is very similar to Wittegenstein's remark on Godel's proof:

I imagine someone asking my advice; he says: “I have constructed a proposition (I will use ‘P’ to designate it) in Russell’s symbolism, and by means of certain definitions and transformations it can be so interpreted that it says: ‘P is not provable in Russell’s system’. Must I not say that this proposition on the one hand is true, and on the other hand unprovable? For suppose it were false; then it is true that it is provable. And that surely cannot be! And if it is proved, then it is proved that it is not provable. Thus it can only be true, but unprovable.”[8]

and it has been refuted by Godel himself:

"It is clear from the passages you cite that Wittgenstein did "not" understand [the first incompleteness theorem] (or pretended not to understand it). He interpreted it as a kind of logical paradox, while in fact is just the opposite, namely a mathematical theorem within an absolutely uncontroversial part of mathematics (finitary number theory or combinatorics)." (Wang 1996:197)

I think I should for someone else's opinion as I am quite confused - what is right, what is wrong at here?

$\endgroup$
  • $\begingroup$ I'm not sure why none of the answers seem to explicitly address your question of what is right and wrong. That dubious claim is indeed wrong, specifically "in a consistent theory any statement that has a proof must be true" is false. Claiming that provability implies truth is a soundness claim, not a consistency claim. PA+¬Con(PA) is consistent but unsound because it proves the false sentence ¬Con(PA). Godel was correct that Wittgenstein did not understand the incompleteness theorem. Very few philosophers (even today) do. $\endgroup$ – user21820 Apr 18 at 17:24
8
$\begingroup$

Is it possible to deduce Godel's first incompleteness theorem from Chaitin's incompleteness theorem?

Gödel's incompleteness theorem, in its modern form using Rosser's trick, only requires that (beyond being effective and sufficiently strong), the theory must be consistent. There is no requirement that the theory has to be $\omega$-consistent or meet any soundness assumption beyond simple consistency. You cannot apply Chaitin's theorem in its usual form to these theories, in general, because the usual form of Chaitin's theorem assumes more (e.g. many proofs of Chaitin's theorem assume as an extra soundness assumption that the theory only proves true statements.)

Many of the "alternate proofs" also require stronger assumptions than the standard proof of the incompleteness theorem. You have to be very careful when reading about this to check which assumptions are included in each theorem.

In the particular proof of Chaitin's theorem presented by Kritchman and Raz, however, they do not need to assume any particular soundness beyond just consistency. I am going to explain this in detail.

They do need to assume that $T$ is sufficiently strong. In particular, they assume that if $n$ and $L$ satisfy $K(n) < L$, then $T \vdash \hat K(\dot n) < \dot L$. Here $\dot n$ and $\dot L$ are terms of the form $1 + 1 + \cdots + 1$ corresponding to $n$ and $L$, and $\hat K$ is a formula of arithmetic defined directly from the definition of $K$. (Note that the set of pairs $(n,L)$ with $K(n) < L$ is recursively enumerable, so there is no real issue in assuming $T$ proves all true sentences of that form.)

Given the assumption on $T$, their proof goes as follows (rephrased in more precise terms):

Begin proof

Given $L$, we can make a program $e_L$ that does the following:

  1. Search for any $n$ such that $T \vdash \hat K (\dot n) > \dot L$. We do this by searching through all $T$-proofs in an exhaustive manner.

  2. Output the first such $n$ we find, if we ever find one.

Because we can code $L$ into the program as a fixed constant, using the standard coding methods, the length $|e_L|$ of $e_L$ no worse than $2\log(L) + C$ for some constant $C$. In particular, we can fix an $L$ with $|e_L| < L$. Assume such an $L$ is fixed.

For this $L$, suppose $e_L$ returns a value, $n$. Then $K(n) \leq |e_L| < L$. By our assumption that $T$ is sufficiently strong, this means $T$ proves $\hat K (\dot n) < \dot L$.

But if $e_L$ returns $n$ then $T$ also proves $\hat K(\dot n) > \dot L$. This means that if $e_L$ returns a value then $T$ is inconsistent. So, if we assume $T$ is consistent, then $e_L$ cannot return a value. This means that, for our fixed $L= L_T$, $T$ cannot prove $\hat K(\dot n) > \dot L$ for any $n$.

Thus, if we take $n = n_T$ to be such that $K(n) > L$, we have that $\hat K (\dot n) > \dot L$ is a true statement that is not provable in $T$.

End proof

This proof just given (in italics) proves:

If $T$ is a consistent, effective theory of arithmetic that proves every true formula of the form $\hat K(\dot n) < \dot L$, then there is a true statement of the form $\hat K(\dot n) > \dot L$ that is not provable in $T$.

This is almost the same as Gödel's incompleteness theorem. The only difference is that the usual proof of the incompleteness theorem gives us an explicit formula that it is true but not provable in $T$ (namely, the Rosser sentence of $T$). On the other hand, the proof in italics requires us to find $n_T$ in order to have an explicit example, and there is no algorithm to do this.

This is one motivation for what I think of as the "standard form" of Chaitin's theorem. In that form, we look instead for unprovable sentences of the form ($\dagger$): $(\exists x)[\hat K(x) > \dot L]$.

Because we can compute $L= L_T$, we can compute a specific sentence of that form for $T$. But, for the proof to work, we need to have an actual $n$ such that $T \vdash \hat K(\dot n) > \dot L$. So we have to add an additional soundness assumption to the theorem, namely that if $T$ proves a sentence of the form ($\dagger$) then there is an $n$ such that $T$ proves $\hat K(\dot n) > \dot L$.

Overall, in this version of Chaitin's theorem, we have an explicit sentence, but with a stronger soundness assumption. The proof of Gödel's incompleteness theorem using Rosser's method gives us an explicit sentence without any stronger soundness assumption.

$\endgroup$
  • $\begingroup$ Thanks! This is really helpful and cleared my confusion. $\endgroup$ – Bombyx mori Nov 2 '14 at 20:08
  • $\begingroup$ Carl, you may want to add "(as opposed to $\omega$-consistent or the like)" or words to that effect right after "only requires that the theory must be consistent", to avoid confusion (since the theory should also be r.e., etc.) $\endgroup$ – Andrés E. Caicedo Nov 4 '14 at 15:53
  • 1
    $\begingroup$ I see how that could be confusing. Thanks for the suggestion, @Andres Caicedo $\endgroup$ – Carl Mummert Nov 4 '14 at 16:00
4
$\begingroup$

As far as I can judge, a very good introductory book about Gödel Theorems is Torkel Franzén, Gödel's theorem : An incomplete guide to its use and abuse (2005).

It is plain but void of the "usual" logical and philosophical misconceptions.

In it you can see Ch.8 : Incompleteness, Complexity, and Infinity, with a discussion about Chaitin's theorem [page 139] :

Suppose $T$ is a consistent formal system incorporating the usual "certain amount of arithmetic." Chaitin's incompleteness theorem states that there is then a number $c$ depending on $T$ such that $T$ does not prove any statement of the form "the complexity of the string $s$ is greater than $c$."

Since there are true such statements, it follows that unless $T$ proves false statements about complexity, there are statements of the form "the complexity of the string $s$ is greater than $c$" that are undecidable in $T$.

Thus, it is a "variant" of Gödel's Incompleteness Theorem.

The gist of Gödel's first incompleteness theorem is not the fact that it build a self-referential sentence: we know it already since ancient Greeks (see Liar Paradox).

The key-result of the first incompleteness theorem is that it establish :

that in any consistent formal system $F$ within which a certain amount of arithmetic can be carried out, there are statements of the language of $F$ which can neither be proved nor disproved in $F$.

Assume $F$ is a formalized system which contains Robinson arithmetic $\mathsf Q$. Then a sentence $G_F$ of the language of $F$ can be mechanically constructed from $F$ such that:

If $F$ is consistent, then $F ⊬ G_F$.

If $F$ is $1$-consistent, then $F ⊬ ¬G_F$.

Such an independent, or “undecidable” (that is, neither provable nor refutable in $F$) statement $G_F$ in $F$ is often called “the Gödel sentence” of $F$.

In fact, in favourable circumstances, it can be shown that $G_F$ is true, provided that $F$ is indeed consistent. [...] For this reason, the Gödel sentence is often called “true but unprovable”.


Can be useful to quote Gödel's closing statements in the introduction to :

The analogy of this argument with the Richard antinomy leaps to the eye. It is closely related to the" Liar" too ; for the undecidable proposition [...] states that [it] is not provable. We therefore have before us a proposition that says about itself that it is not provable [in PM]$^{15}$.

[$footnote^{15}$ : Contrary to appearances, such a proposition involves no faulty circularity, for initially it onlyl asserts that a certain well-defined formula [...] is unprovable. Only subsequently (and so to speak by chance) does it turn out that this formula is precisely the one by which the proposition itself was expressed.]

The method of proof just explained can clearly be applied to any formal system that, first, when interpreted as representing a system of notions and propositions, has at its disposal sufficient means of expression to define the notions occurring in the argument above (in particular, the notion "provable formula") and in which, second, every provable formula is true in the interpretation considered.

The purpose of carrying out the above proof with full precision in what follows is, among other things, to replace the second of the assumptions just mentioned [i.e. "every provable formula is true in the interpretation considered"] by a purely formal and much weaker one [emphasis added].



Regarding Wittgenstein's argument, it seems a little bit too "simplified" :

  • it seems that Wittgenstein "equate" true with provable; Gödel's result says exactly the opposite: in general, we cannot do it.

  • Wittgenstein's formation about logic was with Frege and W&R's Principia Mathematica, i.e. with logicism and it seems to me that at the time of the comment he still the conception of a single, "universal" logico-mathematical system; Gödel's result is relative to a formalized theory $F$ with certain properties (basically, containing arithmetic).

  • Wittgenstein omits the essential "initial condition" that the theory $F$ must be consistent.

But about Wittgenstein and his "misunderstanding" of Gödel's theorem, you can see a much deeper analysis in Juliet Floyd, On Saying What You Really Want to Say: Wittgenstein, Gödel, and the Trisection of the Angle, in Jaakko Hintikka (editor), From Dedekind to Gödel : Essays on the Development of the Foundations of Mathematics, (1995), pp. 373-425.


Notes : you can find here a review of Franzén's book.

You can see also : Panu Raatikainen, On the Philosophical Relevance of Gödel’s Incompleteness Theorems.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.