4
$\begingroup$

On MSE I've asked a question about why did Godel assume the theory in question to be $\omega$ consistent [on top of effectiveness] for his proof [actually the second part of his proof] of first incompleteness to run, while he could have simply assumed the theory "not proving it's own inconsistency" (i.e. $T \not \vdash \neg \operatorname {Con}(T)$). Clearly the former is strictly stronger than the latter, since every $\omega$-consistent theory is a theory that doesn't prove its own inconsistency, but the converse is not true, since we can have sound $\omega$-inconsistent theories. The answer given was about historical context which answered the question.

Here, I want to ask about why afterwards the assumption of $\omega$-consistency remained in connection to Godel's proof? Why Godel himself after people became aware of the particulars of his proof whereby consistency statement of a theory can be expressed in the language of the theory using Godel's numbering, why he didn't change his assumption. Actually one gets the impression that $\omega$-consistency is necessary for his proof, while in fact it's not, actually it is in some sense restrictive! It won't apply to $\omega$-inconsistent theories that do not prove their own inconsistency. While his proof (without the assumption of $\omega$-consistency) actually does apply to those, there is no real need for $\omega$-consistency.

My guess is that Rosser's improvement lateron showed the incompleteness result applicable for every consistent effective theory. So, no one cared for increasing the applicability of Godel's original proof to more theories yet less than Rosser's applicability.

Now, apart from Rosser's improvement. Is there another reason to keep sticking to the assumption of $\omega$-consistency in connection to presenting Godel's original proof, even though it proves to be a strong assumption?

$\endgroup$
3
  • 2
    $\begingroup$ It is a standard view to adopt the Rosser variation of the theorem, for which omega-consistency is no longer relevant. I regard the omega- consistency hypothesis mainly only of historical interest, since it was used in the early original proof, but now we know from Rosser how to do it better without that assumption. There is little need nowadays to speak of omega-consistency when discussing the incompleteness theorem. $\endgroup$ Commented Sep 4, 2023 at 0:27
  • 1
    $\begingroup$ So sticking to saying that Godel's original proof demands $\omega$-consistency [which is too strong for it, it doesn't need all of that] is only for historical purposes. But, why not give a note that the proof itself doesn't really require that assumption, the assumption of $T \not \vdash \neg \operatorname{Con}(T)$ is what it requires (besides effectiviness...). So, your answer is that there is no other reason. It is just Rosser's improvements that dominated that matter, and so no one cared about fine tunning assumptions for the original proof. $\endgroup$ Commented Sep 4, 2023 at 0:37
  • $\begingroup$ @JoelDavidHamkins, I noticed that this subject had been addressed by Isaacson. See: link.springer.com/chapter/10.1007/978-94-007-0214-1_7 $\endgroup$ Commented Sep 4, 2023 at 12:16

1 Answer 1

13
$\begingroup$

To my way of thinking, the principal case of interest with regard to the first incompleteness theorem, the case carrying almost fully the philosophical interest and fascination of the theorem, is the case of true arithmetic theories. In this formulation, the theorem states that there is no computable axiomatization of a theory $T$ that proves all and only the true statements of arithmetic, that is, the statements that are true in the intended standard model $\langle\mathbb{N},+,\cdot,0,1,<\rangle$. In short, no computably axiomatized true theory of arithmetic is complete. We cannot provide a computable list of axioms for the true theory of arithmetic.

It is this formulation of the theorem that addresses the Hilbert program, for example, aimed at providing a complete theory of the arithmetic truths. Gödel's theorem shows that we shall be unable to provide such a theory by a computable list of axioms.

A similar formulation of the theorem is the statement that every consistent computably axiomatizable theory $T$ (and containing a sufficent weak fragment of arithmetic) will admit true but unprovable statements.

These versions of the theorem can be proved by introducing the Gödel sentence $\sigma$, which asserts its own nonprovability in $T$. This statement is both true and not provable in the system. If the theory $T$ is true, then of course we also know that $T$ does not prove $\neg\sigma$, and so the theory is incomplete.

If we aim at a stronger version of the theorem, however, without the assumption that $T$ is true — but one must admit that this is a strange case in which to be interested! — then this argument doesn't quite seem to establish that the theory $T$ is incomplete, since perhaps $T$ would prove $\neg\sigma$. To address this, Gödel had recognized however that if we know the theory is $\omega$-consistent, then we may deduce also that $T$ does not prove $\neg\sigma$, and so $T$ is incomplete. So this was a technical condition, a weakening of truth to $\omega$-consistency, which sufficed to prove his desired conclusion in a more general context.

Soon after, however, Rosser pointed out that in fact no additional assumption is needed for the conclusion in the general case — one needs rather only to consider a slightly revised sentence, while using essentially similar methods. The Rosser sentence $\rho$ asserts that for every proof of $\rho$, there is a smaller proof of $\neg\rho$, smaller in terms of the Gödel code. One can then show, assuming only that $T$ is consistent and computably axiomatizable (and containing a sufficient weak fragment of arithmetic), that $T$ proves neither $\rho$ nor $\neg\rho$.

Thus, the Rosser argument shows that we can simply drop the $\omega$-consistency assumption from the theorem. It is irrelevant.

To my way of thinking, therefore, we frankly have little need to consider or discuss $\omega$-consistency at all in connection with the incompleteness theorem (except as a historical matter). It was a technical hypothesis considered by Gödel as a weakening of truth, but quickly seen to be unnecessary in light of Rosser's argument, which shows that essentially similar ideas as Gödel's prove the theorem without that hypothesis.

When I prove the incompleteness theorem, I start with the easy case of true arithmetic theories, the main case, a case also where the proof is slightly easier. For a stronger result, we go directly to the Gödel-Rosser theorem, which can be proved by essentially similar methods. There is no need or reason at all to consider $\omega$-consistency, and I typically mention it in passing only, in order to give historical context to Rosser's innovation.

In fact, there are many different proofs of the incompleteness theorem, and when I teach this topic, as I shall next semester, I prefer to give as many as possible. I am currently writing a a book entitled Ten proofs of Gödel incompleteness.

$\endgroup$
11
  • $\begingroup$ I think you mean arithmetically sound theories (when you say $T$ is a true theory). Now I understand Boolos's assumption, he is also considering the case where $T$ is sound. Yet, his proof, (as is Godel's) is also not Rosserable and does run under mere estimation of $T \not \vdash \neg Con(T)$ which is the necessary assumption underlying Godel's as well (Isaacson). $\endgroup$ Commented Sep 4, 2023 at 13:51
  • $\begingroup$ Hopefully you can make them "Elven" proofs, by adding [my last proof ](arxiv.org/abs/2308.10904). (smile). However, in connection to this posting, I've realized lately that Godel's incompleteness (1st) can be proved as a corollary of the theorem stating that "no consistent effective theory can be both complete and prove its own consistency". To see this, one has to think in terms of $T \not \vdash \neg Con(T)$ instead of $\omega$-consistency in Godel's original proof. Note, that the above theorem only assumes consistency, because we internalized the last assumption in it's statement. $\endgroup$ Commented Sep 4, 2023 at 14:00
  • $\begingroup$ This reference also seem relevant to this subject and to various ways of proving Godel's first incompleteness. arxiv.org/abs/1612.02549 $\endgroup$ Commented Sep 4, 2023 at 14:16
  • 2
    $\begingroup$ But your statement is not as strong as what Rosser provides: there is no consistent effective complete theory of arithmetic at all (containing a sufficient weak fragment). And there is no need to consider T⊬¬Con(T). Why should we care about generalizing Gödel's ω-consistency proof a little bit, when Rosser already generalized further, almost a century ago, using essentially Gödelian methods? Why be preoccupied with a proof method that was recognized as suboptimal a century ago? $\endgroup$ Commented Sep 4, 2023 at 15:02
  • $\begingroup$ I'm not advocating doing that. And, of course, what I wrote in comments is not at Rosser's strength. I just wanted to say that Godel's original proof burns down to something much weaker than what it appears at first glance. But, with Rosser, this is another story. Again, of course Rosser's is what should be adopted or any proof equivalent to it (like what I think mine (linked) is). I'm not disputing that. There is only some need to consider T $\not \vdash \neg$ Con(T) in connection the original Godel proof (non-historical context), it shows the applicability of that proof. $\endgroup$ Commented Sep 4, 2023 at 18:49

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