Logic Colloquium 2024


Mateusz Łełyk

Faculty of Philosophy, University of Warsaw

Talks at this conference:

  Thursday, 17:30, J330

Simplest model properties for Peano Arithmetic: On a question of Montalban and Rossegger.

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.

  Wednesday, 14:25, J222

Internal categoricity for schemes

Authors: Mateusz Łełyk and Ali Enayat

The talk is devoted to the exposition and explanation of the recent results on the notion of internal categoricity and its various declinations. Within this line of research we aim at understanding how much of the second-order categoricity of various foundational theories (such as Peano Arithmetic, PA or Zermelo-Fraenkel set theory, ZF) can be recovered in the first-order setting? These considerations germinated in the introduction of the concept of internal categoricity of \(\text{PA}\) in full second order logic by Hellman and Parsons, which was followed by Väänänen’s introduction of the notion of internal categoricity of Peano Arithmetic and Zermelo-Fraenkel set theory in the context of Henkin models of second order logic in [6] and in joint work with Wong [5], and later in the context of first order logic, as in [8] and [7]. Internal categoricity has been substantially explored and debated in the philosophical literature, as witnessed by Button and Walsh’s monograph [1], the recent monograph of Maddy and Väänänen [4], and in the recent work of Fischer and Zicchetti [3].

In the talk we argue that the notion of internal categoricity is best seen as a property of schemes, i.e. first-order formulae with a second-order parameter which apply to (first-order) languages returning (first-order) theories. To wit, we prove that each sufficiently strong r.e. theory (in particular: each r.e. extension of PA or ZF) can be axiomatized by a scheme which is not internally categorical. Secondly, we introduce a short hierarchy of categoricity-like notions for schemes which refine internal categoricity and are based on Enayat’s notion of solidity ([2]). Using it we prove two general theorems on the preservation of the appropriate properties by adding the full comprehension and the minimality scheme. As a corollary we are able to derive in a uniform fashion the internal categoricity of the \(n\)-th order arithmetic and Burgess’ extension of the untyped Kripke-Feferman truth theory, KF\(\mu\).


  1. Button, Tim and Walsh, Sean, Philosophy and model theory, Oxford University Press, 2018.
  2. Enayat, Ali, Variations on a {V}isserian theme,A tribute to {A}lbert {V}isser, (J. van Eijk, R. Iemhoff, J. Joosten, editors), Coll. Publ., London, 2016, pp. 99- 110.
  3. , Fischer, Martin and Zicchetti, Matteo, Internal categoricity, truth and determinacy,Journal of Philosophical Logic, vol. 52 (2023), no. 5, pp. 1295- 1325.
  4. , Maddy, Penelope and Väänänen, Jouko, Philosophical Uses of Categoricity Arguments, Cambridge University Press, 2023.
  5. Väänänen, Jouko and Wang, Tong, Internal categoricity in arithmetic and set theory, Notre Dame Journal of Formal Logic vol. 56 (2015), np. 1, pp. 121- 134.
  6. Vä”{ a}nänen, Jouko Second order logic or set theory?, The Bulletin of Symbolic Logic, vol. 18 (2012), no. 1, pp. 91- 121.
  7. , Väänänen, Jouko, Tracing internal categoricity, Theoria. A Swedish Journal of Philosophy, vol. 87 (2021), no. 4, pp. 986- -1000.
  8. , Väänänen, Jouko, An extension of a theorem of {Z}ermelo, The Bulletin of Symbolic Logic, vol. 25 (2019), no. 2, pp. 208- 212.