MOPA

D'Aquino, Knight and Starchenko showed the real closure of a model of Peano Arithmetic is recursively saturated. Thus any two countable models of PA with the same standard system have isomorphic real closures. Charlie Steinhorn, Jim Schmerl and I showed that even for $\omega_1$-like model of PA the situation is very different. We construct $2^{\aleph_1}$ recursively saturated elementarily equivalent $\omega_1$-like models of PA with the same standard system and non-isomorphic real closures.

Video

In this talk we shall deal with fragments of first-order Peano Arithmetic obtained by restricting the conclusion of the induction or the collection axiom to elements in a prescribed subclass $D$ of the universe. Fix $n>0$. The schemes of $\Sigma_n$-induction up to $\Sigma_m$-definable elements and the schemes of $\Sigma_n$-collection up to $\Sigma_m$-definable elements form two families of subtheories of $I\Sigma_n$ and $B\Sigma_n$, respectively, obtained in this way.

The properties of $\Sigma_n$-induction up to $\Sigma_m$-definable elements for $n\geq m$ are reasonably well understood and interesting applications of these fragments are known. However, an analysis of the case $n<m$ was pending. In the first part of this talk, we address this problem and show that it is related to the following general question: 'Under which conditions on a model $M$ can we prove that every non-empty $\Sigma_m$-definable subset of $M$ contains some $\Sigma_m$-definable element?'

In the second part of the talk, we show that, for each $n\geq 1$, the scheme of $\Sigma_n$-collection up to $\Sigma_n$-definable elements provides us with an axiomatization of the $\Sigma_{n+1}$-consequences of $B\Sigma_n$. As an application, we obtain that $B\Sigma_n$ is $\Sigma_{n+1}$-conservative over parameter-free $\Delta_n$-minimization (plus $I\Sigma_{n-1}$), thus partially answering a question of R. Kaye.

This is joint work with F.Félix Lara-Martín (University of Seville).

Video

25 years ago I wrote a paper on four open problems concerning recursively saturated models of PA. The problems are still open. I will talk about two of them: (1) Let M be a countable recursively saturated model of PA. Can every automorphism of M be extended to some recursively saturated elementary end extension of M? (2) Is there a recursively saturated model of PA that has no recursively saturated elementary submodel of the same cardinality as the model? I will present some partial results involving partial inductive satisfaction classes.

Video

This talk will report on ongoing work that is being done in collaboration with Ali Enayat (University of Gothenburg).

For models of set theory $\mathcal{N}$ and $\mathcal{M}$, $\mathcal{N}$ is a powerset preserving end-extension of $\mathcal{M}$ if $\mathcal{N}$ is an end-extension of $\mathcal{M}$ and $\mathcal{N}$ contains no new subsets of sets in $\mathcal{M}$. A model of Kripke-Platek Set Theory, $\mathcal{N}$, is a rank-extension of a model of Kripke-Platek Set Theory, $\mathcal{M}$, if $\mathcal{N}$ is an end-extension of $\mathcal{M}$ and all of the new sets in $\mathcal{N}$ have rank that exceeds the rank of all of the sets in $\mathcal{M}$. A powerset preserving end-extension (rank-extension) $\mathcal{N}$ of $\mathcal{M}$ is topless if $\mathcal{M} \neq \mathcal{N}$ and there is no set in $\mathcal{N} \backslash \mathcal{M}$ containing only sets from $\mathcal{M}$. If $\mathcal{M}= \langle M, E^\mathcal{M} \rangle$ is a model of set theory, then the admissible cover of $\mathcal{M}$, $\mathbb{C}\mathrm{ov}_\mathcal{M}$, is defined to be the smallest admissible structure with $\mathcal{M}$ forming its urelements and whose language contains a unary function function symbol, $F$, that sends each $m \in M$ to the set $\{x \in M \mid x E^\mathcal{M} m\}$. Barwise has shown that if $\mathcal{M}$ is a model of Kripke-Platek Set Theory, then $\mathbb{C}\mathrm{ov}_{\mathcal{M}}$ exists and its minimality facilitates compactness arguments for infinitary languages coded in $\mathbb{C}\mathrm{ov}_\mathcal{M}$. We extend Barwise's analysis by showing that if $\mathcal{M}$ satisfies enough set theory then the expansion of $\mathbb{C}\mathrm{ov}_\mathcal{M}$ obtained by adding the powerset function remains admissible. This allows us to build powerset preserving end-extensions and rank-extensions of countable models of certain subsystems of $\mathrm{ZFC}$ satisfying any given recursive subtheory of the model being extended. In particular, we show that

1. Every countable model of $\mathrm{KP}^\mathcal{P}$ has a topless rank-extension that satisfies $\mathrm{KP}^\mathcal{P}$.
2. Every countable $\omega$-standard model of $\mathrm{MOST}+\Pi_1\textrm{-collection}$ has a topless powerset preserving end-extension that satisfies $\mathrm{MOST}+\Pi_1\textrm{-collection}$.

Video

I will present an axiomatization of a class of residue rings of models of PA. This is obtained using valuation theory and results on models of PA. (Joint work with A. Macintyre)

Video

This is a continuation of the talk from Feb 16th. This time we shall study different theories of the form ${\rm CT}^-[\delta]$ which are conservative extensions of a ${\rm PA}$. In particular, we prove the following theorem.

Theorem 2 There exists a family $\{\delta_f\}_{f\in\omega^*}$ such that for all $f,g\in\omega^*$
1) ${\rm CT}^-[\delta_f]$ is conservative over ${\rm PA}$;
2) if $f\subsetneq g$, then ${\rm CT}^-[\delta_g]$ properly extends ${\rm CT}^-[\delta_f]$;
3) if $f\perp g$ then ${\rm CT}^-[\delta_g]\cup {\rm CT}^-[\delta_f]$ is nonconservative over ${\rm PA}$ (but consistent).

We will finish the proof of the theorem announced in the abstract of part II.

Video

​

This is a continuation of the talk from Feb 16th. This time we shall study different theories of the form ${\rm CT}^-[\delta]$ which are conservative extensions of a ${\rm PA}$. In particular, we prove the following theorem.

Theorem 2 There exists a family $\{\delta_f\}_{f\in\omega^*}$ such that for all $f,g\in\omega^*$
1) ${\rm CT}^-[\delta_f]$ is conservative over ${\rm PA}$;
2) if $f\subsetneq g$, then ${\rm CT}^-[\delta_g]$ properly extends ${\rm CT}^-[\delta_f]$;
3) if $f\perp g$ then ${\rm CT}^-[\delta_g]\cup {\rm CT}^-[\delta_f]$ is nonconservative over ${\rm PA}$ (but consistent).

Video

​

Hirschfeldt and Jockusch (2016) introduced a two-player game in which winning strategies for one or the other player precisely correspond to implications and non-implications between given $\Pi^1_2$ principles over $\omega$-models of ${\rm RCA}_0$. They also introduced a version of this game that similarly captures provability over (full) ${\rm RCA}_0$. We generalize this game for provability over arbitrary subsystems of second-order arithmetic, and establish a compactness argument that shows that certain winning strategies can always be chosen to win in a number of moves bounded by a number independent of the instance of the principles being considered. Our compactness result also generalizes an old proof-theoretic fact due to H. Wang, and has a number of other applications. This is joint work with Denis Hirschfeldt and Sarah Reitzes.

Video

​

This talk focuses on the theory PAI (I for Indiscernibles), a theory formulated in the language of PA augmented with a unary predicate I(x). Models of PAI are of the form (M,I) where (1) M is a model of PA, (2) I is a proper class of M, i.e., I is unbounded in M and (M,I) satisfies PA*, and (3) I forms a class of indiscernibles over M. The formalizability of the Infinite Ramsey Theorem in PA makes it clear that PAI is a conservative extension of PA. As we will see, nonstandard models of PA (of any cardinality) that have an expansion to a model of PAI are precisely those nonstandard models PA that can carry an inductive partial satisfaction class. The formulation and investigation of PAI was inspired by my work on the set theoretical sibling ZFI of PAI, whose behavior I will also compare and contrast with that of PAI.

Video

​

The purpose of this talk is to exposit a method for proving independence over PA of 'mathematical' statements (whatever that means). The method uses the concept of an $(\mathcal L, n)$-model: a finite sequence of finite $\mathcal L$-structures for some first order $\mathcal L$ extending the language of arithmetic. The idea is that this finite sequence is intended to represent increasing approximations of a potentially infinite structure and the machinery developed allows one to translate (meta-mathematical) compactness type statements, which are easily seen to be independent of PA, into statements about finite combinatorics, which have 'mathematical content'. $(\mathcal L, n)$-models were introduced by Shelah in the 70's in his alternative proof of the Paris-Harrington Theorem and also appears (implicitly) in his example of a true, unprovable $\Pi^0_1$ statement of some 'mathematical' content. A similar idea was discovered independently by Kripke (unpublished). In this talk we will flesh out the details of this method and extend the general theory. This will allow us to present, in a fairly systematic fashion, proofs of the Paris-Harrington Theorem and the independence over PA of several, similar, Ramsey Theoretic statements including some which are $\Pi^0_1$.

Slides

Video

​

We study a family of axioms expressing $$`\text{All axioms of PA are true.' (*)}$$ where PA denotes Peano Arithmetic. More precisely, each such axiom states that all axioms from a chosen axiomatization of PA are true. We start with a very natural theory of truth ${\rm CT}^-({\rm PA})$ which is a finite extension of PA in the language of arithmetic augmented with a fresh predicate T to serve as a truth predicate for the language of arithmetic. Additional axioms of this theory are straightforward translations of inductive Tarski truth conditions. To study various possible ways of expressing (*), we investigate extensions of ${\rm CT}^-({\rm PA})$ with axioms of the form $$\forall x \bigl(\delta(x)\rightarrow T(x)\bigr).$$ In the above (and throughout the whole abstract) $\delta(x)$ is an elementary formula which is proof-theoretically equivalent to the standard axiomatization of PA with the induction scheme, i.e. the equivalence $$\forall x \bigl(\text{Prov}_{\delta}(x)\equiv \text{Prov}_{\rm PA}(x)\bigr).$$ is provable in $I\Sigma_1$. For every such $\delta$, the extension of ${\rm CT}^-({\rm PA})$ with the above axiom will be denoted ${\rm CT}^-[\delta]$.

In particular we shall focus on the arithmetical strength of theories ${\rm CT}^-[\delta]$. The 'line' demarcating extensions of ${\rm CT}^-({\rm PA})$ which are conservative over PA from the nonconservative ones is known in the literature as the Tarski Boundary. For some time, there seemed to be the least (in terms of deductive strength) *natural* extension of ${\rm CT}^-({\rm PA})$ on the nonconservative side of the boundary, whose one axiomatization is given by ${\rm CT}^-({\rm PA})$ and $\Delta_0$ induction for the extended language (the theory is called ${\rm CT}_0$). This theory can equivalently be axiomatized by adding to ${\rm CT}^-({\rm PA})$ the natural formal representation of the statement 'All theorems of ${\rm PA}$ are true.'. We show that the situation between the Tarski Boundary and ${\rm CT}_0$ is much more interesting:

Theorem 1: For every r.e. theory Th in the language of arithmetic the following are equivalent:
1) ${\rm CT}_0\vdash$ Th
2) there exists $\delta$ such that ${\rm CT}^-[\delta]$ and Th have the same arithmetical consequences.

Theorem 1 can be seen as a representation theorem for r.e. theories below ${\rm REF}^{\omega}({\rm PA})$ (all finite iterations of uniform reflection over ${\rm PA}$, which is the set of arithmetical consequences of ${\rm CT}_0$): each such theory can be finitely axiomatized by a theory of the form ${\rm CT}^-[\delta]$, where $\delta$ is proof-theoretically reducible to ${\rm PA}$.

Secondly, we use theories ${\rm CT}^-[\delta]$ to investigate the situation below the Tarski Boundary. We shall prove the following result

Theorem 2: There exists a family $\{\delta_f\}_{f\in\omega^{<\omega}}$ such that for all $f,g\in\omega^{<\omega}$
1) ${\rm CT}^-[\delta_f]$ is conservative over ${\rm PA}$;
2) if $f\subsetneq g$, then ${\rm CT}^-[\delta_g]$ properly extends ${\rm CT}^-[\delta_f]$;
3) if $f\perp g$ then ${\rm CT}^-[\delta_g]\cup CT^-[\delta_f]$ is nonconservative over ${\rm PA}$ (but consistent).

Video

​

We prove that any two countable models of the theory ${\rm WKL}^*_0$ sharing the same first-order universe and containing the same counterexample to $\Sigma^0_1$ induction are isomorphic.

This theorem implies that over ${\rm WKL}^*_0 + \neg I\Sigma^0_1$, the analytic hierarchy collapses to the arithmetic hierarchy. It also implies that ${\rm WKL}^*_0$ is the strongest $\Pi^1_2$ statement that is $\Pi^1_1$-conservative over ${\rm RCA}^*_0 + \neg I\Sigma^0_1$. Together with the (slightly subtle) generalizations of the theorem to higher levels of the arithmetic hierarchy, this gives an 'almost negative' answer to a question of Towsner, who asked whether $\Pi^1_1$-conservativity of $\Pi^1_2$ sentences over collection principles is a $\Pi^0_2$-complete computational problem. Our results also have some implications for the reverse mathematics of combinatorial principles: for instance, we get a specific $\Pi^1_1$ sentence that is provable in ${\rm RCA}_0 + B\Sigma^0_2$ exactly if the $\Pi^1_1$ consequences of ${\rm RCA}_0 + {\rm RT}^2_2$ coincide with $B\Sigma^0_2$.

On the side, we also give a positive answer to Towsner's question as originally stated.

Joint work with Marta Fiori Carones, Tin Lok Wong, and Keita Yokoyama.

Video

​

Two types of principles are commonly called “reflection principles” in reverse mathematics. According to syntactic reflection principles for T, every theorem of T (from some complexity class) is true. According to semantic reflection principles, every set belongs to some (sufficiently correct) model of T. We will present a connection between syntactic reflection and semantic reflection in second-order arithmetic: for any Pi^1_2 axiomatized theory T, every set is contained in an omega model of T if and only if every iteration of Pi^1_1 reflection for T along a well-ordering is Pi^1_1 sound. There is a thorough proof-theoretic understanding of the latter in terms of ordinal analysis. Accordingly, these reductions yield proof-theoretic analyses of omega-model reflection principles. This is joint work with Fedor Pakhomov.

Video

​