MOPA

Tarski's undefinability of truth theorem has two versions, the first one deals with truth itself, takes some effort to prove, and is a descendant of the Epimenides (liar) paradox. The second one deals with the related concept of satisfaction, has a one-line proof, and is a descendent of Russell's paradox. This talk is about the first one, which appeared in the 1953 monograph 'Undecidable Theories' by Tarski, Mostowski, and Robinson; it was employed there to show the essential undecidability of consistent theories that can represent all recursive functions (a strong form of the Gödel-Rosser incompleteness theorem). I will present Tarski's original 1953 formulation (which differs from the common formulation in modern expositions) and will explain how it was used in my recent work with Albert Visser to show that no consistent completion of a sequential theory whose signature is finite is axiomatizable by a collection of sentences of bounded quantifier-alternation-depth. A variant of this result was proved independently by Emil Jeřábek, as I will explain. Our proof method has a pedagogical dividend since it allows one to replace the cryptic Gödel-Carnap fixed point lemma with the perspicuous undefinability of truth theorem in the proof of the Gödel-Rosser incompleteness theorem.

Slides

Video

Tarski's undefinability of truth theorem has two versions, the first one deals with truth itself, takes some effort to prove, and is a descendant of the Epimenides (liar) paradox. The second one deals with the related concept of satisfaction, has a one-line proof, and is a descendent of Russell's paradox. This talk is about the first one, which appeared in the 1953 monograph 'Undecidable Theories' by Tarski, Mostowski, and Robinson; it was employed there to show the essential undecidability of consistent theories that can represent all recursive functions (a strong form of the Gödel-Rosser incompleteness theorem). I will present Tarski's original 1953 formulation (which differs from the common formulation in modern expositions) and will explain how it was used in my recent work with Albert Visser to show that no consistent completion of a sequential theory whose signature is finite is axiomatizable by a collection of sentences of bounded quantifier-alternation-depth. A variant of this result was proved independently by Emil Jeřábek, as I will explain. Our proof method has a pedagogical dividend since it allows one to replace the cryptic Gödel-Carnap fixed point lemma with the perspicuous undefinability of truth theorem in the proof of the Gödel-Rosser incompleteness theorem.

Slides

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

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

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

​

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

​

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

​

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

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

​