Theories of arithmetics in finite models

Krynicki, Michał ; Zdanowski, Konrad

J. Symbolic Logic, Tome 70 (2005) no. 1, p. 1-28 / Harvested from Project Euclid

Résumé

We investigate theories of initial segments of the standard models for arithmetics. It is easy to see that if the ordering relation is definable in the standard model then the decidability results can be transferred from the infinite model into the finite models. On the contrary we show that the Σ₂—theory of multiplication is undecidable in finite models. We show that this result is optimal by proving that the Σ₁—theory of multiplication and order is decidable in finite models as well as in the standard model. We show also that the exponentiation function is definable in finite models by a formula of arithmetic with multiplication and that one can define in finite models the arithmetic of addition and multiplication with the concatenation operation. ¶ We consider also the spectrum problem. We show that the spectrum of arithmetic with multiplication and arithmetic with exponentiation is strictly contained in the spectrum of arithmetic with addition and multiplication.

Détail

Publié le : 2005-03-14
Classification:  Finite models,  arithmetic,  definability,  spectrum,  complexity,  03C13,  03C68,  68Q17