[FOM] A question concerning incompleteness

[Richard Heck]

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20140606/bddee67d/attachment.html>