MOPA

We investigate the end extendibility of models of arithmetic with restricted elementarity. By utilizing the restricted ultrapower construction in the second-order context, for each $n \in \mathbb{N}$ and any countable model of $\mathrm{B}\Sigma_{n+2}$, we construct a proper $\Sigma_{n+2}$-elementary end extension satisfying $\mathrm{B}\Sigma_{n+1}$, which answers a question by Clote positively. We also give a characterization of countable models of $\mathrm{I}\Sigma_{n+2}$ in terms of their end extendibility similar to the case of $\mathrm{B}\Sigma_{n+2}$. Along the proof, we will introduce a new type of regularity principles in arithmetic called the weak regularity principle, which serves as a bridge between the model's end extendibility and the amount of induction or collection it satisfies.
The talk is based on this paper from arxiv:2409.03527.

Slides

Video

A theory is tight if and only if every two extensions of it, in the language of that theory, are bi-interpretable iff they are equal. The property of being tight can be seen as a kind of local categoricity in a suitable category of theories and interpretations. Examples of tight theories include $\text{PA}$, $\text{Z}_{2}$, $\text{ZF}$, and $\text{KM}$. Neatness, semantic tightness, and solidity are strengthenings of tightness, with solidity being the strongest and the other two being intermediate. During the talk we will focus on relations between those properties in the context of arithmetic theories and theories of finite sets.

Partly based on a joint work with Leszek Kołodziejczyk and Mateusz Łełyk.

Video

A theory is tight if and only if every two extensions of it, in the language of that theory, are bi-interpretable iff they are equal. The property of being tight can be seen as a kind of local categoricity in a suitable category of theories and interpretations. Examples of tight theories include $\text{PA}$, $\text{Z}_{2}$, $\text{ZF}$, and $\text{KM}$. Neatness, semantic tightness, and solidity are strengthenings of tightness, with solidity being the strongest and the other two being intermediate. During the talk we will focus on relations between those properties in the context of arithmetic theories and theories of finite sets.

Partly based on a joint work with Leszek Kołodziejczyk and Mateusz Łełyk.

Video

Over the last years, a lot of progress has been achieved in understanding the arithmetical strength of axiomatic theories of compositional truth. It turned out that a theory $\mathsf{CT}^-$ of compositional truth for arithmetical sentences can become non-conservative over $\mathsf{PA}$ upon adding some seemingly benign principles.

One of the principles whose arithmetical strength is still unknown is the axiom of propositional soundness which says that for any arithmetical sentence $\phi$ which is a propositional tautology, $\phi$ is true in the sense of the truth predicate. It is an open problem whether this axiom together with $CT^-$ is conservative over $PA$.

In our talk, we will show that if $(M,T)$ is a model of $\mathsf{CT}^-$ satisfying the propositional soundness principle, then $(M,T)$ satisfies a certain amount of saturation: if $(\phi_i)_{i \lt c}$ is a sequence of sentences such that for any standard $i$, $\phi_i$ is true in the sense of the truth predicate, then there is a nonstandard $d$ such that for each $i \in [0,d]$, $\phi_i$ is true. This puts very strong limitations on any possible conservativeness proof. The result may be seen as a counterpart to the classical theorem of Lachlan which says that the arithmetical part of any model of $\mathsf{CT}^-$ is recursively saturated.

Video

Let $\mathsf{M}$ be the weak set theory (with powersets) axiomatised by: $\textsf{Extensionality}$, $\textsf{Pair}$, $\textsf{Union}$, $\textsf{Infinity}$, $\textsf{Powerset}$, transitive containment ($\textsf{TCo}$), $\Delta_0\textsf{-Separation}$ and $\textsf{Set-Foundation}$. In this talk I will discuss the relationship between two alternative versions of the set-theoretic collection scheme: Collection and Strong Collection. Both of these schemes yield $\mathsf{ZF}$ when added to $\mathsf{M}$, but when restricted the $\Pi_n$-formulae (denoted $\Pi_n\textsf{-Collection}$ and $\textsf{Strong } \Pi_n\textsf{-Collection}$) these alternative versions of set-theoretic collection differ. In particular, over the theory $\mathsf{M}$, $\textsf{Strong }\Pi_n\textsf{-Collection}$ is equivalent to $\Pi_n\textsf{-Collection}+\Sigma_{n+1}\textsf{-Separation}$. And, $\mathsf{M}+\textsf{Strong }\Pi_n\textsf{-Collection}$ proves the consistency of $\mathsf{M}+\Pi_n\textsf{-Collection}$. In this talk I will show that, despite this difference in consistency strength, every countable well-founded model of $\mathsf{M}+\Pi_n\textsf{-Collection}$ satisfies $\textsf{Strong } \Pi_n\textsf{-Collection}$. If time permits I will outline how this argument can be refined to show that $\mathsf{M}+\Pi_n\textsf{-Collection}+\Pi_{n+1}\textsf{-Foundation}$ proves $\Sigma_{n+1}\textsf{-Separation}$.

Video

In the talk we address the following problem: how many essentially different truth definitions (for the language of arithmetic) are there? Formally, a truth definition for us is just a sentence $\phi$ in some language $L$, which extends the elementary arithmetic (a.k.a. $I\Delta_0 + \exp$) and such that for some $L$-formula $\Theta(x)$, $$\phi\vdash \psi\equiv\Theta(\ulcorner\psi\urcorner),$$ for every sentence $\psi$ in the language of arithmetic. In other words $\phi$ is a sentence which can define a truth predicate for arithmetic (via a formula $\Theta(x)$). We investigate the structure of the definability relation between so defined truth definitions. To be more precise: we say that a truth definition $\phi$ (in a language $L$) defines a truth definition $\phi'$ (in a language $L'$) if and only if there are $L$-formulae $A_1,\ldots,A_n$ such that $\phi\vdash \phi'[A_1/R_1,\ldots,A_n/R_n]$, where $R_i$'s are all the non-arithmetical predicates from the language $L'$ and $\phi'[A_1/R_1,\ldots,A_n/R_n]$ denotes the result of translating $\phi'$ by substituting $A_i$ for each occurrence of $R_i$. We note that this translation does not relativize the quantifiers in $\phi'$ and keeps the arithmetical symbols unchanged. Our main result is that the structure consisting of truth definitions which are conservative over the basic arithmetical theory forms a countable universal distributive lattice. Additionally, we (slightly) generalize the result of Pakhomov and Visser showing that the set of (Gödel codes of) definitions of truth is not $\Sigma_2$-definable in the standard model of arithmetic.

This is joint work with Piotr Gruza which was published in here.

Video

The infinitary logic $L_{\omega_1, \omega}$ extends first-order logic by allowing countable disjunctions and conjunctions of formulas. Every countable structure can be described up to isomorphism (within the class of countable structures) by an $L_{\omega_1, \omega}$ sentence. This gives rise to a particular way of measuring the complexity of countable structures: there is a natural alternation hierarchy $(\Pi^{\text{in}}_\alpha: \alpha \lt \omega_1)$ of $L_{\omega_1, \omega}$ formulas, and the Scott rank of a structure $A$ is the smallest ordinal $\alpha$ such that $A$ can be described up to isomorphism by a $\Pi^{\text{in}}_{\alpha+1}$ sentence.

In recent years, beginning with a paper by Montalban and Rossegger, the Scott rank of models of arithmetic has attracted some attention. We now know, for instance, that every nonstandard pointwise definable model of ${\rm PA}$ has Scott rank at least omega, that all other nonstandard models of ${\rm PA}$ must have rank at least $\omega+1$, and that recursively saturated models of ${\rm PA}$ have rank exactly $\omega+1$. This naturally leads one to ask about possible Scott ranks of models of subtheories of ${\rm PA}$. In particular: what is the lowest possible Scott rank of a structure satisfying $I\Sigma_n + \lnot B\Sigma_{n+1}$? What about $B\Sigma_n + \lnot I\Sigma_n$?

We prove that every nonstandard model of $B\Sigma_n$ must have Scott rank at least $n+1$. Moreover, this lower bound is tight: it is realized both by the most familiar models of $I\Sigma_n + \lnot B\Sigma_{n+1}$, namely pointwise $\Sigma_{n+1}$-definable substructures of models of $I\Sigma_{n+1}$, and by the most familiar models of $B\Sigma_n + \lnot I\Sigma_n$, namely initial segments generated by the $\Sigma_n$-definables of models of $I\Sigma_n$. Time permitting, we also hope to mention a few other facts about Scott ranks of models of fragments of ${\rm PA}$.

This is joint work in progress with Mateusz Łełyk and Patryk Szlufik.

Video