[FOM] A question concerning incompleteness

[Arnon Avron]

Thanks, Richard, for a quick and helpful reply!

Your message  provides an answer for the case of Q. However, it leaves
the case of the system N of Shoenfield unanswered.
Unfortunately, this is the more interesting case (for me).
To explain why, let me refine my question. The minimal system
*I* know which is essentially undecidable
(and so no consistent axiomatic extension of it
can be complete) is sometime called RR.
It is in the language {=,<,0,S,+,x}, and has the
following as axioms:

1) All true atomic sentences of its language and 
   all true  negations of atomic sentences of its language.

2) For each natural number n, the axiom:
   \forall x<n. x=0\vee x=1 \vee ... \vee x=n-1

   (here for simplicity I identify a natural number k
    with the corresponding numeral of the form SS...S0)

3) For each natural number n, the axiom:
   \forall x. x<n \vee x=n \vee n<x

Let RR^- be the system whose axioms are only those
included in 1) and 2) above.
What I would *really* like to know is whether RR^-
has an axiomatic extension which is both consistent
and complete. My bet is that the answer is positive.
Needless to say, if the system N^- obtained from N
by deleting the linearity axiom has such extension
(as I believe) then so does RR^-. However, Q without
the axiom that every number different than 0
has a predecessor is too weak, I believe, for deriving the axioms
of RR^- concerning < (no matter how we define < in the
language of Q).

Arnon


On Thu, Jun 05, 2014 at 03:25:51PM -0400, Richard Heck wrote:
> 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 undecidable" (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 re-read the other proofs in detail, but they all seem to
> have the same
> structure. (The theory is defined in terms of the sentences true in
> some model.)
> So I think we can conclude, in the 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
>