Authors: Mateusz Łełyk and Patryk Szlufik

This is joint work with Patryk Szlufik from the University of Warsaw.

As famously shown by Scott, every countable structure can be characterized, up to isomorphism, by a sentence of infinitary language \(L_{\omega_1, \omega}\) which allows for conjunctions and disjunctions over arbitrary countable families of formulae (over finitely many variables). Formulae of this language can be naturally assigned ranks based on the number of alternations of existential connectives (disjunctions and existential quantifiers) with universal ones (conjunctions and universal quantifiers). This gives rise to a natural complexity measure for countable models: the Scott rank of a model \(\mathcal{M}\) is the least \(\alpha\) such that \(\mathcal{M}\) can be uniquely characterized by a sentence of rank \(\alpha+1\) (and starting from the universal quantifier). The developments of computable model theory witness that the Scott rank is a very robust notion integrating other well established tools from descriptive set theory. model theory and computability.

In “The Structural Complexity of Models of Arithmetic” Antonio Montalban and Dino Rossegger pioneered the Scott analysis of models of Peano Arithmetic. They characterized the Scott spectrum of completions PA , i.e. the set of ordinals which are Scott ranks of countable models of a given completion \(T\) of PA. A particulary intriguing outcome of their analysis is that PA has exacty one model of the least rank, the standard model, and the Scott rank of every other model is infinite. Additionally they studied the connections between Scott ranks and model-theoretical properties of models, such as recursive saturation and atomicity, rasising an open question: is there a non-atomic homogeneous model of PA of Scott rank \(\omega\)?

In the talk we answer the above question to the negative, showing that the nonstandard models of PA or rank \(\omega\) are exactly the nonstandard prime models. This witness another peculiar property of PA: not only it has the simplest model, but also every its completion has a unique model of the least Scott rank.

The notion of Rosser theories is introduced in [1]. Rosser theories play an important role in the study of the incompleteness phenomenon and mete-mathematics of arithmetic, and have important mete-mathematical properties. All definitions of Rosser theories in the literature are restricted to arithmetic languages which admit numerals for natural numbers. Results about Rosser theories in the literature are confined to 1-ary relations. A general theory of Rosser theories for \(n\)-ary relations for any \(n\geq 1\) and relationships among them is missing in the literature.

We first introduce the notion of \(n\)-Rosser theories, which generalizes the notion of Rosser theories for RE sets to \(n\)-ary RE relations in a general setting via the notion of interpretation. Then, we introduce notions of exact \(n\)-Rosser theories, effectively \(n\)-Rosser theories and effectively exact \(n\)-Rosser theories. Our definitions of these notions are not restricted to arithmetic languages admitting numerals for natural numbers. Then we systematically examine properties of these notions, and study relationships among these notions. Especially, we generalize some important theorems about Rosser theories for RE sets in the literature to \(n\)-Rosser theories for any \(n\geq 1\). One important tool we use is the fact that for a disjoint pair of \(n\)-ary RE relations, semi-\(\sf DU\) implies \(\sf DU\). We give three different proofs of this fact.

Let \(T\) be a consistent RE theory. We prove the following main theorems for any \(n\geq 1\):

• If \(T\) is \((n+1)\)-Rosser (exact \((n+1)\)-Rosser), then \(T\) is effectively \(n\)-Rosser (effectively exact \(n\)-Rosser).
• If \(T\) is \((n+1)\)-Rosser, then \(T\) is exact \(n\)-Rosser.
• \(T\) is effectively \(n\)-Rosser if and only if \(T\) is effectively exact \(n\)-Rosser.
• Suppose \(T\) is \(n\)-Rosser and any \(n\)-ary recursive functional on \(\mathbb{N}^n\) is admissible in \(T\), then \(T\) is exact \(n\)-Rosser.
• If the pairing function \(J_2(x,y)\) is strongly definable in \(T\), then for any \(n\geq 1\), the following are equivalent: \(n\)-Rosser, effectively \(n\)-Rosser, exact \(n\)-Rosser, effectively exact \(n\)-Rosser.

Bibliography

1. Raymond M. Smullyan. Recursion Theory for Meta-Mathematics (Oxford Logic Guides, 22). Oxford University Press, New York, 1993.

Authors: Mengzhou Sun, Tin Lok Wong and Yue Yang

A general question in the model theory of arithmetic is:

“for which theories \(S\), \(T\) and which \(n\in\mathbb N\) is it true that every countable sufficiently saturated model of a theory \(S\) has a proper \(\Pi_n\)-elementary end extension to a model of a theory \(T\)?”

Efforts over the past four decades have revealed answers to this question for all the well-known theories in arithmetic, i.e., the \(\Sigma_m\) induction schemes \(\mathrm I\Sigma_m\) and the \(\Sigma_m\) collection schemes \(\mathrm B\Sigma_m\), except the following instance.

Kaufmann [2] in the context of set theory; Clote [1]
“Is it true that, given any integer \(n\geqslant2\), every countable model of \(\mathrm B\Sigma_n\) has a proper \(\Pi_n\)-elementary end extension to a model of \(\mathrm B\Sigma_{n-1}\)?”

We present a positive answer to the Kaufmann–Clote question. The proof consists of a second-order ultrapower construction based on a low basis theorem. We will also include a survey on the answers related to the general question above.

Bibliography

1. P. Clote,Partition relations in arithmetic,Methods in Mathematical Logic(C. A. Di Prisco, editor),Springer-Verlag,Berlin,1985,pp. 32–68.
2. M. Kaufmann,On existence of \(Sigma_n\) end extensions,Logic Year 1979–80,(M. Lerman, J. H. Schmerl and R. I. Soare, editors),vol. 859,Springer,Berlin,1981,pp. 92–103.