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

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\).