[FOM] A question concerning incompleteness

[Arnon Avron]

Thanks again, Richard for your very helpful replies!

Thanks also to Panu Raatikainen and André Rognes for their replies.
However, their replies were based on a wrong interpretation
of what I had intended to ask. I did not mean the deletion of the
axiom that states that 0 has no prdecessor, but the one that states
that any other number does have a prdecessor. Accordingly, the systems
I had in mind obviously do not have finite models.

Arnon


On Fri, Jun 06, 2014 at 12:57:18PM -0400, Richard Heck wrote:
> On 06/05/2014 05:23 PM, Arnon Avron wrote:
> >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).
> 
> Yes, I should have remarked upon that.
> 
> >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.
> 
> The answer is known to be "No". This was first observed by Alan Cobham
> around 1960. The best reference for this:
> 
> @ARTICLE{JonesShep:VariantsOfR,
>  author = {James P. Jones and John C. Shepherdson},
>  title = {Variants of {R}obinson's Essentially Undecidable Theory {R}},
>  journal = {Archiv f\"ur mathematische {L}ogik und {G}rundlagenforschung},
>  year = {1983},
>  volume = {23},
>  pages = {61--4}
> }
> 
> which show how to interpret your RR^- in RR (=R) and which contains a bunch
> of other nice results. Cobham's paper:
> 
> @INCOLLECTION{Cobham:EfDecThs,
>  author = {Alan Cobham},
>  title = {Effectively Decidable Theories},
>  pages = {391--5},
>  address = {Princeton},
>  booktitle = {Summaries of Talk Presented at the Summer Institute
> for Symbolic Logic, Cornell University, 1957},
>  edition = {2d},
>  editor = {A. Tarski and others},
>  publisher = {Institute for Defense Analyses},
>  year = {1960}
> }
> 
> is hard to find. I have never seen it, in fact.
> 
> Richard
> 

> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom