[FOM] A question concerning incompleteness

[Richard Heck]

On 06/03/2014 12:40 PM, Arnon Avron wrote:
> Dear Fomers,
>
> I have a question:
>
> It is well-known that no consistent axiomatic extension
> of Robinson's system Q or Shoenfield's system N
> (from his great book "Mathematical Logic") can be complete.
>
> Does this theorem remain true if we delete from Q
> the axiom that states that every number different than 0
> has a predecessor....?

No. This falls out of the proof that Tarski, Mostowski, and Robinson 
give in _Undecidable Theories_ of Theorem II.11: "No axiomatic subtheory 
of Q obtained by removing any one of the seven axioms from the axiom 
system is essentially undeciable" (p. 62).

They give the following example for this case: Let T3 be the set of all 
formulas in the language <0,S,+,x> that are true in the model where the 
domain is the set of non-negative reals and the rest are interpreted as 
usual. Then all axioms of Q other than the one you mention are theorems 
of T3. Let T-bar be the set of all formulas in the language <P,0,S,+,x> 
that are true in the model with domain the reals, P true of the 
non-negative ones, and the rest interpreted normally. Then T-bar is 
decidable, by other results of Tarski's, and relativizing T-bar to P 
shows that T3 is also decidable, so T3 is an axiomatic theory. But T3 is 
also complete, since it is the set of all formulas true in some model.

I did not read all the other proofs in detail, but they all seem to have 
the same structure. So I think we can conclude, in teh spirit of II.11: 
No axiomatic subtheory of Q obtained by removing any one of the seven 
axioms from the axiom system is essentially incomplete.

Richard