History
Year:
-
Type:
Journal
Book
Article
Please fill in your query. A complete syntax description you will find on the General Help page.
Theories of arithmetics in finite models. (English)
J. Symb. Log. 70, No. 1, 1-28 (2005).
Let $A$ be a first-order structure whose universe is $ω$. For each $n<ω$, let $A_n$ denote the (naturally defined) restriction of $A$ to $\{0,\dots, n\}$. Let FM$(A)$ be the family of all $A_n$’s. Marcin Mostowski introduced the notion of satisfiability in sufficiently large finite models in FM$(A)$. This is the central notion of the paper. The focus is on decidability and other properties of the suitably defined theory Th(FM$(A))$, and the theory of sufficiently large models sl(FM$(A))$, where $A$ is one of the standard models of the form $(ω, +)$, $(ω, \times)$, $(ω, \times, \leq)$, or $(ω, \exp)$. It is a substantial paper, I only list some of the main results. In Section 4, the authors prove that the set of $Σ_2$ sentences of arithmetic of multiplication which are satisfiable in finite models is $Σ^0_1$-complete, and the set of those $Σ_2$ sentences which are true in all sufficiently large models is $Σ^0_1$-hard. Also, for $A$ being either $(ω, \times)$ or $(ω, \exp)$, Th(FM$(A))$ is $Π^0_1$-complete, and sl(FM$(A))$ is $Σ^0_2$-complete. The main result of Section 5 is that the theory of sufficiently large models in FM$(ω, \times,\leq)$ is decidable and so is the existential theory of the standard model of multiplication and order. In Section 6 the authors consider the arithmetic of concatenation and show that in finite models it has the same strength as the arithmetic of addition and multiplication. The FM$(A)$-spectrum of a sentence $φ$ is the set $\{n+1: A_n\models φ\}$. The spectrum of FM$(A)$ is the set of all FM$(A)$-spectra of all sentences of the language of FM$(A)$. Section 7 contains several interesting results concerning the spectra of FM$(A)$ for various $A$. In particular, it is shown that the spectrum of exponentiation is strictly contained in the spectrum of addition and multiplication.
Roman Kossak (New York)