[FOM] A question concerning incompleteness
Richard Heck
richard_heck at brown.edu
Fri Jun 6 12:57:18 EDT 2014
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>
More information about the FOM
mailing list