MOPA

The Borel hierarchy gives a robust way to stratify the complexity of sets of countable structures and is intimately tied with definability in infinitary logic via the Lopez-Escobar theorem. However, what happens with sets axiomatizable in finitary first-order logic, such as the set of structures satisfying a given finitary first-order theory T? Is the complexity of the set of T's models in any way related to the quantifier complexity of the sentences axiomatizing it? In particular, if a theory T is not axiomatizable by a set of sentences of bounded quantifier complexity, can the set of models of T still be at a finite level of the Borel hierarchy?

In this talk, we will present results concerning these questions:

In joint work with Andrews, Gonzalez, Lempp, and Zhu we show that the set of models of a theory T is $\Pi^0_\omega$-complete if and only if T does not have an axiomatization by sentences of bounded quantifier complexity, answering the last question in the negative. We also characterize the Borel complexity of the set of models of complete theories in terms of their finitary axiomatizations. Our results suggest that infinitary logic does not provide any efficacy when defining first-order properties, a phenomenon already observed by Wadge and Keisler and, recently, rediscovered by Harrison-Trainor and Kretschmer using different techniques.

Combining our results with recent results by Enayat and Visser, we obtain that a large class of theories studied in the foundations of mathematics, sequential theories, have a maximal complicated set of models.

Video

​

It is well-known under ZFC that there is a nonstandard model of PA which has a full standard system, i.e. every subset of this model's standard cut is the intersection of the standard cut with some subset of the model which is definable from parameters. We show that the use of Choice here cannot be avoided. More precisely, we prove that it is consistent relative to ZF that no model of PA has full standard system, and it is provable in ZF (or just a fragment of second-order arithmetic) that no Borel model has full standard system. The proof is measure-theoretic in nature, and as a simpler first argument, we will prove from Projective Determinacy the stronger claim that no projective model has full standard system.

Since the power set of the naturals is trivially a Scott set, an immediate corollary of this result is that Scott's problem is independent of ZF.

Slides

Video

It was shown by Visser that Peano Arithmetic has the property that no two distinct extensions of it (in its language) are bi-interpretable. Enayat proposed to refer to this property of a theory as tightness and to carry out a more systematic study of tightness and its stronger variants, which he called neatness and solidity.

Enayat proved that not only $\text{PA}$, but also $\text{ZF}$, $\text{Z}_{2}$, and $\text{KM}$ are solid; and on the other hand, that finitely axiomatisable fragments of them are not even tight. Later work by a number of authors showed that many natural proper fragments of these theories are also not tight.

Enayat asked whether there are proper solid subtheories (containing some basic axioms that depend on the theory) of the theories listed above. We answer this question in the case of $\text{PA}$ by proving that for every $n$ there exists a solid theory strictly between $\text{I}\Sigma_{n}$ and $\text{PA}$. Furthermore, we can require that the theory does not interpret $\text{PA}$, and that if any true arithmetic sentence is added to it, the theory still does not prove $\text{PA}$.

Joint work with Leszek Kołodziejczyk and Mateusz Łełyk.

Video

​

This talk reports on research in collaboration with Ali Enayat and Mateusz Łełyk.

Steffen Lempp and Dino Rossegger asked: is there a consistent completion of ${\sf PA}^-$ that is axiomatised by sentences of bounded quantifier-alternation complexity? We show that there is no such restricted completion. We also show that, if one changes the measure of complexity to being $\Sigma_n$, there is a restricted completion. Specifically, we show that the true theory of the non-negative part of $\mathbb Z[X]$ can be axiomatised by a single sentence plus a set of $\Sigma^0_1$-sentences.

In our talk we will sketch these two answers. One of our aims is to make clear is that the negative answer for the case of quantifier-alternation complexity simply follows from Rosser's Theorem viewed from a sufficiently abstract standpoint.

Video

​

The lattice problem for models of PA is to determine which lattices can be represented either as lattices of elementary substructures of a model of PA or, more generally, which can be represented as lattices of elementary substructures of a model N that contain a given elementary substructure M of N. I will talk about the history of the problem, from the seminal paper of Haim Gaifman from 1976 and other early results to some recent work of Jim Schmerl. There is much to talk about.

Video

​

The lattice problem for models of PA is to determine which lattices can be represented either as lattices of elementary substructures of a model of PA or, more generally, which can be represented as lattices of elementary substructures of a model N that contain a given elementary substructure M of N. I will talk about the history of the problem, from the seminal paper of Haim Gaifman from 1976 and other early results to some recent work of Jim Schmerl. There is much to talk about.

Video

​

Following up on the series of talks on the history of the problem, in this talk we will discuss the main technique for realizing finite lattices as interstructure lattices, due to Schmerl in 1986. We will motivate this technique by studying an example: the Boolean algebra $\mathsf{B}_2$. We will see how we can modify the technique to produce elementary extensions realizing specific ranked lattices to ensure that such extensions are end, cofinal, or mixed extensions.

Video

Following up on the series of talks on the history of the problem, in this talk we will discuss the main technique for realizing finite lattices as interstructure lattices, due to Schmerl in 1986. We will motivate this technique by studying an example: the Boolean algebra $\mathsf{B}_2$. We will see how we can modify the technique to produce elementary extensions realizing specific ranked lattices to ensure that such extensions are end, cofinal, or mixed extensions.

Video

(This is a joint work with Keita Yokoyama) Some recent studies in reverse mathematics focus on theorems that are stronger than $\mathsf{ATR}_0$ and weaker than $\Pi^1_1$-$\mathsf{CA}_0$. Especially, theorems represented by a $\Pi^1_2$ sentence and provable from $\Pi^1_1$-$\mathsf{CA}_0$ are investigated. In this talk, we will introduce a hierarchy slicing the set $\{\sigma \in \Pi^1_2: \Pi^1_1\text{-}\mathsf{CA}_0\}$. Then, we show that Ramsey's theorem for $\Sigma^0_2,\Sigma^0_3,\Sigma^0_4,\ldots$ sets are separated in a sense although all of them are equivalent to $\Pi^1_1$-$\mathsf{CA}_0$ by comparing this hierarchy and a suitable weaker variant of those theorems. We also show that a similar result holds for $(\Sigma^0_1)_n$ determinacy.

Slides

Video