[FOM] A question concerning incompleteness
Arnon Avron
aa at tau.ac.il
Sat Jun 7 02:23:58 EDT 2014
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
More information about the FOM
mailing list