The incompleteness theorems, Sigma-1-completeness, induction, all that

In the thread "Provable in T" the incompleteness theorem and their exact requirements - Sigma-1-completeness in particular - have been the subject of much discussion.

Tbe first incompleteness theorem is usually expressed something like the following

For any extension T of Robinson arithmetic we can effectively find a
sentence G_T, s.t. G_T is true and undecidable in T iff T is
(1-)consistent.

As everyone knows, Robinson arithmetic is Sigma-1-complete: every true Sigma-1 sentence is provable in Robinson arithmetic, proved essentially by showing by induction - not in Robinson arithmetic itself! - that every true Delta_0 sentence is provable in Robinson arithmetic and hence by existential generalization so is every Sigma-1 truth.

Now, in the proof of the first incompleteness theorem the sentence G_T is constructed specifically as a (true) fixed point of the unprovability predicate for T, which can be taken to be Pi-1. We need Sigma-1-completeness for two things: that enough facts about substitution of specific terms in formulas are provable - so that the diagonal lemma goes through -, and that if G_T is, in fact, provable in T then it is provable in T that G_T is provable in T.

To get the second theorem we need more than just Sigma-1-completeness, namely *provable Sigma-1-completeness* - this might or might not have been one of Greene's points - plus a few facts about provability itself. One of the original derivability conditions in the second incompleteness theorem given by Bernays was effectively a form of provable Sigma-1-completeness:

T |- f(x) = 0 --> Prov_T("f(x) = 0"), for f primitive recursive

If we have provable Sigma-1-completeness (together with a few facts about provability, i.e. that provability of P --> Q implies that the provability of P implies the provability of Q) we can, in T, see that if G_T were provable it would be provable in T that G_T is provable, contradicting the T-provable fact that G_T is a fixed point of the non-provability predicate, i.e. G_T <--> ~Prov_T("G_T"). The theory ISigma_1 - Q + induction for Sigma-1 formulae (which, by the way, is, in general, Pi_3) - suffices to prove the Sigma-1-completeness of (any extension of) Q, as well as the few facts about formal provability needed, but so does e.g. EA = Q + Delta_0(exp)-induction + the defining equations for exp where exp is a function symbol denoting exponentiation. We can easily show that there is no weakest theory to which the first incompleteness theorem applies, and similarly there is no weakest theory to which the second incompleteness theorem applies - in the sense that they could be proved incomplete by a proof substantially similar to that standardly given for the first incompleteness theorem, or that they do not prove their own consistency could be proved by a proof substantially similar to that standardly - though not very often! - given proof for the second incompleteness theorem.

--
Aatu Koskensilta (aatu.koskensilta@xxxxxxxxx)

"Wovon man nicht sprechen kann, daruber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
.

Relevant Pages

  • Re: Simple yet Profound Metatheorem
    ... P and Q are variables that range over wffs ... Unprovability of Consistency, or The Logic of Provability by Boolos. ... >> Computation theorem becomes an Incompleteness theorem in Logic, ... >> C-B ...
    (sci.logic)
  • Re: THIS STATEMENT HAS NO PROOF IN ANY SYSTEM = true or false?
    ... second incompleteness theorem (i.e., the first incompleteness theorem can be ... ISigma_1 is enough because you only need to prove things about provability, ... Suppose T is an axiomatizable theory extending Q and G is a Goedel-Rosser ... Then, the 1st incompleteness theorem says "If T is consistent, then G is ...
    (sci.math)
  • Re: THIS STATEMENT HAS NO PROOF IN ANY SYSTEM = true or false?
    ... second incompleteness theorem (i.e., the first incompleteness theorem can be ... ISigma_1 is enough because you only need to prove things about provability, ... Suppose T is an axiomatizable theory extending Q and G is a Goedel-Rosser ... Then, the 1st incompleteness theorem says "If T is consistent, then G is ...
    (sci.logic)
  • Re: THIS STATEMENT HAS NO PROOF IN ANY SYSTEM = true or false?
    ... second incompleteness theorem (i.e., the first incompleteness theorem can be ... ISigma_1 is enough because you only need to prove things about provability, ... Suppose T is an axiomatizable theory extending Q and G is a Goedel-Rosser ... Then, the 1st incompleteness theorem says "If T is consistent, then G is ...
    (comp.theory)
  • Re: The incompleteness theorems, Sigma-1-completeness, induction, all that
    ... But a sigma-1 truth of true arithmetic is going to ... Sigma-1-completeness for two things: that enough facts about ... been one of Greene's points - plus a few facts about provability itself. ...
    (sci.logic)