Theories of arithmetics in finite models

Journal of Symbolic Logic 70 (1):1-28 (2005)
  Copy   BIBTEX


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



    Upload a copy of this work     Papers currently archived: 86,273

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Stretchings.O. Finkel & J. P. Ressayre - 1996 - Journal of Symbolic Logic 61 (2):563-585.
On the complexity of models of arithmetic.Kenneth McAloon - 1982 - Journal of Symbolic Logic 47 (2):403-415.
Classical and Intuitionistic Models of Arithmetic.Kai F. Wehmeier - 1996 - Notre Dame Journal of Formal Logic 37 (3):452-461.
Modal logic over finite structures.Eric Rosen - 1997 - Journal of Logic, Language and Information 6 (4):427-439.
Inconsistent models of arithmetic part I: Finite models. [REVIEW]Graham Priest - 1997 - Journal of Philosophical Logic 26 (2):223-235.


Added to PP

59 (#231,493)

6 months
3 (#338,162)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Pseudofinite difference fields and counting dimensions.Tingxiang Zou - 2021 - Journal of Mathematical Logic 21 (1):2050022.
Pseudofinite difference fields.Tingxiang Zou - 2019 - Journal of Mathematical Logic 19 (2):1950011.
Pseudofinite difference fields and counting dimensions.Tingxiang Zou - 2021 - Journal of Mathematical Logic 21 (1):2050022.

Add more citations

References found in this work

Weak Second‐Order Arithmetic and Finite Automata.J. Richard Büchi - 1960 - Mathematical Logic Quarterly 6 (1-6):66-92.
On representing concepts in finite models.Marcin Mostowski - 2001 - Mathematical Logic Quarterly 47 (4):513-523.
On Pascal triangles modulo a prime power.Alexis Bés - 1997 - Annals of Pure and Applied Logic 89 (1):17-35.
Arithmetic of divisibility in finite models.A. E. Wasilewska & M. Mostowski - 2004 - Mathematical Logic Quarterly 50 (2):169.
Arithmetical definability over finite structures.Troy Lee - 2003 - Mathematical Logic Quarterly 49 (4):385.

Add more references