[FOM] A question concerning incompleteness
Richard Heck
richard_heck at brown.edu
Thu Jun 5 15:29:16 EDT 2014
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
More information about the FOM
mailing list