|
|
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
|
|