Theories of arithmetics in finite models

Journal of Symbolic Logic 70 (1):1-28 (2005)
Abstract
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
Keywords Finite models   arithmetic   definability   spectrum   complexity
Categories (categorize this paper)
DOI 10.2178/jsl/1107298508
Options
 Save to my reading list
Follow the author(s)
Edit this record
My bibliography
Export citation
Find it on Scholar
Mark as duplicate
Request removal from index
Revision history
Download options
Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 30,169
Through your library
References found in this work BETA
Weak Second-Order Arithmetic and Finite Automata.J. Richard Büchi - 1960 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 6 (1-6):66-92.
Weak Second‐Order Arithmetic and Finite Automata.J. Richard Büchi - 1960 - Mathematical Logic Quarterly 6 (1‐6):66-92.
Arithmetical Definability Over Finite Structures.T. Lee - 2003 - Mathematical Logic Quarterly 49 (4):385.
Arithmetic of Divisibility in Finite Models.A. E. Wasilewska & M. Mostowski - 2004 - Mathematical Logic Quarterly 50 (2):169.
On Pascal Triangles Modulo a Prime Power.Alexis Bés - 1997 - Annals of Pure and Applied Logic 89 (1):17-35.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles
Stretchings.O. Finkel & J. P. Ressayre - 1996 - Journal of Symbolic Logic 61 (2):563-585.
Modal Logic Over Finite Structures.Eric Rosen - 1997 - Journal of Logic, Language and Information 6 (4):427-439.
Classical and Intuitionistic Models of Arithmetic.Kai F. Wehmeier - 1996 - Notre Dame Journal of Formal Logic 37 (3):452-461.
On the Complexity of Models of Arithmetic.Kenneth McAloon - 1982 - Journal of Symbolic Logic 47 (2):403-415.
Inconsistent Models of Arithmetic Part I: Finite Models. [REVIEW]Graham Priest - 1997 - Journal of Philosophical Logic 26 (2):223-235.
Added to PP index
2009-05-24

Total downloads
39 ( #136,049 of 2,191,922 )

Recent downloads (6 months)
1 ( #289,020 of 2,191,922 )

How can I increase my downloads?

Monthly downloads
My notes
Sign in to use this feature