Theories of initial segments of standard models of arithmetics and their complete extensions (Q549718)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Theories of initial segments of standard models of arithmetics and their complete extensions
scientific article

    Statements

    Theories of initial segments of standard models of arithmetics and their complete extensions (English)
    0 references
    0 references
    0 references
    0 references
    18 July 2011
    0 references
    Let \(\mathcal A\) be a first-order structure whose universe is the set of natural numbers \(\mathbb N\). For each \(n\), \({\mathcal A}_n\) is the structure defined by restricting all functions and relations of \({\mathcal A}\) to \(\{0,\dots, n\}\) and redefining the functions so that, in the case of an overflow, the value is defined to be \(n\). The signature of \({\mathcal A}_n\) is that of \({\mathcal A}\) with the additional constant symbol MAX, interpreted as \(n\). \(\text{FM}({\mathcal A})\) is the set \(\{{\mathcal A}_n: n\in {\mathbb N}\}\), and, for a formula \(\varphi(x_1,\dots, x_p)\) and \(b_1,\dots,b_p\in {\mathbb N}\), the satisfaction relation \(\text{FA}({\mathcal A})\models_{\text{sl}}\varphi(b_1,\dots, b_p)\) is defined to hold whenever there is a \(k\) such that, for all \(n\geq k\), \({\mathcal A}_n\models\varphi(b_1,\dots,b_p)\). Finally, \(\text{sl}({\mathcal A})\) is the set of sentences \(\varphi\) such that \(\text{FA}({\mathcal A})\models_{\text{sl}}\varphi\). The paper gives a comprehensive introduction to the model theory of the sl-semantics. Among others, examples are given of structures \({\mathcal A}\) and \({\mathcal B}\) such that \({\mathcal A}\not\equiv {\mathcal B}\) and \(\text{sl}({\mathcal A})=\text{sl}({\mathcal B})\), and structures \({\mathcal A}\) and \({\mathcal B}\) such that \({\mathcal A}\cong {\mathcal B}\) and \(\text{sl}({\mathcal A})\not=\text{sl}({\mathcal B})\). Then, in the main part of the paper, the authors prove a number of results on finite models of Presburger arithmetic and full arithmetic. An axiomatization {sl}PresbAr for \(\text{sl}(({\mathbb N},+))\) is given, followed by a theorem characterizing its completions. It is shown that {sl}PresbAr has continuum many completions and infinitely many decidable ones. Concerning the structure of full arithmetic \({\mathcal N}=({\mathbb N},+,\times)\), it is shown that there are continuum many completions of \(\text{sl}({\mathcal N})\) and that the complexity of each completion is at least \(\Delta_3\). The paper concludes with an example of a completion of \(\text{sl}({\mathcal N})\) that is \(\Delta_3\).
    0 references
    0 references
    finite models
    0 references
    arithmetic
    0 references
    finite arithmetic
    0 references
    Presburger arithmetic
    0 references
    decidability
    0 references

    Identifiers