[FOM] A question concerning incompleteness
Panu Raatikainen
panu.raatikainen at helsinki.fi
Thu Jun 5 01:07:03 EDT 2014
aa at tau.ac.il:
> 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, or if we delete from N the axiom
> that states that the relation < on the natural numbers
> is linear?
>
> Thanks,
>
> Arnon Avron
If I get the setting right, the answer is no:
Such a theory is what Smullyan (1961, 1993) has called "a Gödel
Theory": it is incomplete and undecidable; however, it is not
"a Rosser Theory", and hence, in Tarski’s terminology, not
essentially undecidable; that is, its every consistent extension
is not undecidable. For one may add to it, for example, the
sentence (For all x, x = 0) – or, any sentence that determines
the model’s size to be some finite cardinality – and the resulting theory is
complete and decidable.
I played a little with one such theory in a funny old paper:
http://link.springer.com/article/10.1023%2FA%3A1026542526897#page-1
(or here: http://www.mv.helsinki.fi/home/praatika/finitetruth.pdf)
There are references to some other uses as well (note 5).
All the Best
Panu
--
Panu Raatikainen
Ph.D., Adjunct Professor in Theoretical Philosophy
Theoretical Philosophy
Department of Philosophy, History, Culture and Art Studies
P.O. Box 24 (Unioninkatu 38 A)
FIN-00014 University of Helsinki
Finland
E-mail: panu.raatikainen at helsinki.fi
http://www.mv.helsinki.fi/home/praatika/
More information about the FOM
mailing list