David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Ezio Di Nucci
Jonathan Jenkins Ichikawa
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Symbolic Logic 70 (1):1-28 (2005)
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)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
J. Richard Büchi (1960). Weak Second‐Order Arithmetic and Finite Automata. Mathematical Logic Quarterly 6 (1‐6):66-92.
J. Richard Büchi (1960). Weak Second-Order Arithmetic and Finite Automata. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 6 (1-6):66-92.
T. Lee (2003). Arithmetical Definability Over Finite Structures. Mathematical Logic Quarterly 49 (4):385.
A. E. Wasilewska & M. Mostowski (2004). Arithmetic of Divisibility in Finite Models. Mathematical Logic Quarterly 50 (2):169.
Alexis Bés (1997). On Pascal Triangles Modulo a Prime Power. Annals of Pure and Applied Logic 89 (1):17-35.
Citations of this work BETA
No citations found.
Similar books and articles
O. Finkel & J. P. Ressayre (1996). Stretchings. Journal of Symbolic Logic 61 (2):563-585.
Maciej Farulewski (2005). On Finite Models of the Lambek Calculus. Studia Logica 80 (1):63 - 74.
James Loveys & Predrag Tanović (1996). Countable Models of Trivial Theories Which Admit Finite Coding. Journal of Symbolic Logic 61 (4):1279-1286.
Eric Rosen (1997). Modal Logic Over Finite Structures. Journal of Logic, Language and Information 6 (4):427-439.
Kai F. Wehmeier (1996). Classical and Intuitionistic Models of Arithmetic. Notre Dame Journal of Formal Logic 37 (3):452-461.
Kenneth McAloon (1982). On the Complexity of Models of Arithmetic. Journal of Symbolic Logic 47 (2):403-415.
David Fernández Duque (2011). On the Modal Definability of Simulability by Finite Transitive Models. Studia Logica 98 (3):347-373.
Marcel Guillaume (2000). Simplified Models Establishing Some of Né:Zondet's Results on Erdös–Woods Conjecture. Synthese 125 (1-2):133 - 146.
Graham Priest (1997). Inconsistent Models of Arithmetic Part I: Finite Models. [REVIEW] Journal of Philosophical Logic 26 (2):223-235.
Added to index2009-05-24
Total downloads37 ( #128,378 of 1,926,176 )
Recent downloads (6 months)3 ( #271,894 of 1,926,176 )
How can I increase my downloads?