[FOM] A question concerning incompleteness

[Panu Raatikainen]

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/