MOPA

In a paper published in 1990, Kossak showed that all countable models of $\Sigma_n$ collection where $\Sigma_n$ induction fails have continuum-many automorphisms. We extract from his proof a(nother) quantifier-elimination result. This gives new information about pigeonhole principles and expansions to second-order models. The work is joint with David Belanger, CT Chong, Wei Li, and Yue Yang at the National University of Singapore.

Video

​

Advances in understanding the incompleteness of PA in the 1970s and 80s built on the work of an earlier generation in the 1930s and 40s. This talk will offer historical and personal reflections on what was known, and what was not known, by both generations of logicians.

Video

​

Athena sprang forth full grown from the head of Zeus. Newton/Leibniz created Calculus. Galois created Galois Theory. Cantor created Set Theory. Boole created Boolean Algebra.

But Models of Peano Arithmetic doesn’t have a dramatic origin myth like that and took some 100 years to emerge as a discipline in itself - from Dedekind’s Second Order Axioms for Arithmetic (1863), through Frege’s Begriffsschrift (1879) and First Order Logic, through Godel’s Completeness and Incompleteness Theorems, through Skolem’s elegant construction of a non-standard model, through the War and après-guerre and on into the 1970s where the subject at last emerges as a discipline in itself. We’ll discuss the convergence of people and ideas from diverse fields like Model Theory, Set Theory, Recursion Theory, Proof Theory, Complexity Theory, … that led to the field we know and love today.

Video

Slides

​

As the history goes, and was confirmed recently [vP20], Gödel first proved his first incompleteness theorem [G31] for sound theories (that extend Principia Mathematica). Later he weakened the soundness condition to “ℵ₀-consistency”, which later evolved to “ω-consistency”. This condition was needed for irrefutability of (what is now called) Gödelian sentences; the simple consistency of a theory suffices for the unprovability of such sentences. Gödel already notes in [G31] that a necessary and sufficient condition for the independence of Gödelian sentences of T is just a bit more than the simple consistency of T: the consistency of T with Con_T, the consistency statement of T.
In this talk, we ask the following questions and attempt at answering them, at least partially.

1. Why on earth Gödel [G31] had to introduce this rather strange notion?
2. Does it have any applications in other areas of logic, arithmetical theories, or mathematics?
3. What was Gödel’s reason that ω-consistency is “much weaker” than soundness? He does prove in [G31] that consistency is weaker (if not much weaker) than ω-consistency; but never mentions a proof or even a hint as to why soundness is (much) stronger than ω-consistency!
4. Other than those historical and philosophical questions, is this a useful notion worthy of further study?

We will also review some properties of ω-consistency in the talk.
References:

• [G31]   Kurt Gödel (1931); “On formally undecidable propositions of Principia Mathematica and related systems I”, in: S. Feferman, et al. (eds.), Kurt Gödel: Collected Works, Vol. I: Publications 1929–1936, Oxford University Press, 1986, pp. 135–152.
• [vP20]   Jan von Plato (2020); Can Mathematics Be Proved Consistent? Gödel’s Shorthand Notes & Lectures on Incompleteness, Springer.
  Reviewed in the zbMATH Open at https://zbmath.org/1466.03001

Video

​

The Scott rank of a countable structure is the least ordinal $\alpha$ such that all automorphism orbits of the structure are definable by infinitary $\Sigma_{\alpha}$ formulas. Montalbán showed that the Scott rank of a structure is a robust measure of the structural and computational complexity of a structure by showing that various different measures are equivalent. For example, a structure has Scott rank $\alpha$ if and only if it has a $\Pi_{\alpha+1}$ Scott sentence if and only if it is uniformly $\pmb \Delta_\alpha^0$ categorical if and only if all its automorphism orbits are $\Sigma_\alpha$ infinitary definable.

In this talk we present results on the Scott rank of non-standard models of Peano arithmetic. We show that non-standard models of PA have Scott rank at least $\omega$, but, other than that, there are no limits to their complexity. Given a completion $T$ of $PA$ we give a reduction via bi-interpretability of the class of linear orders to the models of $T$. This allows us to exhibit models of $T$ of Scott rank $\alpha$ for every $\omega\leq \alpha\leq \omega_1$. In particular, every completion of $T$ has models of high Scott rank.

This is joint work with Antonio Montalbán.

Video

​

When properly arithmetized, Yablo's paradox results in a set of formulas which (with local disquotation in the background) turns out to be consistent, but $\omega$-inconsistent. Adding either uniform disquotation or the $\omega$-rule results in inconsistency. Since the paradox involves an infinite sequence of sentences, one might think that it doesn't arise in finitary contexts. We study whether it does. It turns out that the issue depends on how the finitistic approach is formalized. On one of them, proposed by Marcin Mostowski, all the paradoxical sentences simply fail to hold. This happens at a price: the underlying finitistic arithmetic itself is $\omega$-inconsistent. Finally, when studied in the context of a finitistic approach which preserves the truth of standard arithmetic, the paradox strikes back - it does so with double force, for now the inconsistency can be obtained without the use of uniform disquotation or the $\omega$-rule. This is joint work with Rafał Urbaniak from the University of Gdańsk.

Video

​

I will survey some well-known and some more recent undefinability results about models of Peano Arithmetic. I want to contrast first-order undefinability in the standard model with a much stronger notion of undefinability which is suitable for resplendent models, and use the results to motivate some more general questions about the nature of undefinability.

Video

​

In their technical report “Alien Intruders in Relevant Arithmetic,” Robert Meyer and Chris Mortensen explored models of relevant arithmetic including nonstandard numbers and proved an “Alien Intruder Theorem” that there are models of relevant arithmetic R# in which all rationals exist and act as natural numbers. They observed some “magical” phenomena about these models, like the fact that induction holds of these rational numbers, but did little to explain them. In this talk, I will show how techniques from ultraproduct constructions reveal some of the reasons for these “magical” features, which help demystify some of Meyer and Mortensen’s observations. This is joint work with Elisangela Ramirez at UNAM.

Video

​

In this talk we discuss important results concerning the automorphism groups of countable recursively saturated models of PA and automorphism groups of the countable boundedly recursively saturated models of PA which are short (aka short recursively saturated models). We compare and contrast and also list some open questions.

Video

​

In this talk we investigate generic automorphisms of countable models. Hodges-Hodkinson-Lascar- Shelah 93 introduces the notion of SI (small index) generic automorphisms which are used to show the small index property. Truss 92 defines the notion of Truss generic automorphisms. We study the relationship between these two types of generic automorphisms.

Video

​

In the 1970s, the logician and philosopher Robert Meyer proposed a novel response to Goedel's Incompleteness Theorems, suggesting that perhaps the results' impact could be blunted by analyzing Peano arithmetic with a weaker deductive system. Initial successes of the program of relevant arithmetic were positive. E.g., R# (the theory of Peano arithmetic under the relevant logic R) can be shown consistent in the sense of not proving 0=1 and this can be shown through arguably finitistic methods. In this talk I will discuss the rise and fall of Meyer's program, detailing the philosophical foundations, its positive development, and the context of Harvey Friedman's negative result in 1992. I'll also suggest why the program, although not necessarily successful, is nevertheless an interesting object of study.

Also note that a great deal of context—including Meyer's two long-unpublished monographs on the topic—have recently appeared in a special issue of the Australasian Journal of Logic I co-edited with Graham Priest, which can be found at https://ojs.victoria.ac.nz/ajl/issue/view/751.

Video

​

The use of nonstandard models *N of the natural numbers has recently found several applications in arithmetic Ramsey theory. The basic observation is that every infinite number in *N corresponds to an ultrafilter on N, and the algebra of ultrafilters is a really powerful tool in this field. Note that this notion also makes sense in any model of PA, where one can consider the 1-type of any infinite number.

Furthermore, nonstandard natural numbers are endowed with a natural compact topology, and one can apply the methods of topological dynamics considering the shift operator $x \mapsto x+1$ . This very peculiar dynamic has interesting characteristics.

In this talk I will also present a new result in the style of Hindman’s Theorem about the existence of infinite monochromatic configurations in any finite coloring of the natural numbers. A typical example is the following monochromatic pattern:
a, b, c, $\ldots$ , a+b+ab, a+c+ac, b+c+bc, $\ldots$ , a+b+c+ab+ac+bc+abc.

Video

​

Harvey Friedman shows that, over Peano Arithmetic as base theory, the consistency statement for a finitely axiomatised theory can be characterised as the weakest statement that, in combination with the base, interprets the given theory. Thus, we have a coordinate-free characterisation of these consistency statements modulo base-theory-provable equivalence.

Let us call a base theory that, in analogy to Peano Arithmetic, has such weakest extensions: Friedman-reflexive. We call such a weakest statement the interpreter of the finite theory. Interpreters are not always consistency statements, but they are still 'consistoids'.

Which theories are Friedman-reflexive and what more can we say about their consistoids and the associated provability-like notion? We will sketch some preliminary insights. (E.g., all complete theories are Friedman-reflexive.)

We discuss Friedman-reflexive sequential base theories. We introduce an example of an attractive very weak base theory that shares many properties with Peano Arithmetic, to wit Peano Corto. We have a look at what Friedman-reflexive sequential theories look like in general. It turns out that they may look somewhat different from Peano Arithmetic and its little brother Peano Corto.

Given an interpretation $K$ of a Friedman-reflexive base $U$ in a finitely axiomatised theory $A$, we can define an analogue of provability logic: the interpreter logic of $A$ over $U$, relative to $K$. All interpreter logics satisfy K4, aka the Löb Conditions. Two theories are irreconcilable iff they do not have finite extensions that are mutually interpretable. If $A$ and $U$ are irreconcilable, then their interpreter logic relative to $K$ contains at least Löb’s Logic. If one of $A$ or $U$ is sequential, then $A$ and $U$ are irreconcilable.

Video

​

The disjunctive correctness principle (DC) states that a disjunction of arbitrary (possibly nonstandard) length is true if and only if one of its disjuncts is true. On first sight, the principle seems an innocent and natural generalization of the familiar compositional truth axiom for disjunction. However, Ali Enayat and Fedor Pakhomov demonstrated that (DC) has the same strength as Delta_0 induction, hence it produces a non-conservative extension of the background arithmetical theory.

In the presentation the proof of a stronger result will be presented. Let (DC-Elim) be just one direction of (DC), namely, the implication 'if a disjunction is true, then one of it disjuncts is true'. We will show that already (DC-Elim) carries the full strength of Delta_0 induction; moreover, the proof of this fact will be significantly simpler than the original argument of Enayat and Pakhomov.

Video

​

This is joint work (still in progress) with Mateusz Łełyk (who gave the first part of the talk). By an axiomatic theory of truth (for the language of arithmetic, $L$) we mean a theory in L enriched with a fresh unary predicate $T(x)$ which (extends the elementary arithmetic EA and) proves all sentences of the form ($\phi$ being a sentence in L) $T(\phi)\equiv \phi.$

The collection of all sentence of the above form is normally called $TB^-$. It is well known that axiomatic theories of truth have a number of interesting model-theoretic consequences. For example, already relatively weak theories of truth impose recursive saturation, in the sense that the L-reduct of any model of such theory is recursively saturated. To give another example, already $TB^-$ imposes elementary equivalence of models, in the sense that whenever $(M,T)\models TB^-$, $(M',T')\models TB^-$, and $(M,T)\subset (M', T)$ (the first model is a submodel of the second one), then actually $M$ and $M'$ are elementarily equivalent. During (both parts) of the talk we investigate which of these properties actually characterize the respective truth theory up to definability. In particular, in the first part of the talk, we prove the following results (we restrict ourselves to theories in a finite language and extending EA):

1. Every theory which imposes elementary equivalence defines $TB^-$.
2. Every theory which imposes full elementarity defines $UTB^-$.

Additionally, we take a look at the definability relations between axiomatic truth theories and axiomatic theories of definability or skolem functions.

Video

​

This is joint work (still in progress) with Bartosz Wcisło (who will give the second part of the talk). By an axiomatic theory of truth (for the language of arithmetic, $L$) we mean a theory in L enriched with a fresh unary predicate $T(x)$ which (extends the elementary arithmetic EA and) proves all sentences of the form ($\phi$ being a sentence in L) $T(\phi)\equiv \phi.$

The collection of all sentence of the above form is normally called $TB^-$. It is well known that axiomatic theories of truth have a number of interesting model-theoretic consequences. For example, already relatively weak theories of truth impose recursive saturation, in the sense that the L-reduct of any model of such theory is recursively saturated. To give another example, already $TB^-$ imposes elementary equivalence of models, in the sense that whenever $(M,T)\models TB^-$, $(M',T')\models TB^-$, and $(M,T)\subset (M', T)$ (the first model is a submodel of the second one), then actually $M$ and $M'$ are elementarily equivalent. During (both parts) of the talk we investigate which of these properties actually characterize the respective truth theory up to definability. In particular, in the first part of the talk, we prove the following results (we restrict ourselves to theories in a finite language and extending EA):

1. Every theory which imposes elementary equivalence defines $TB^-$.
2. Every theory which imposes full elementarity defines $UTB^-$.

Additionally, we take a look at the definability relations between axiomatic truth theories and axiomatic theories of definability or skolem functions.

Slides

Video

​

The use of nonstandard models *N of the natural numbers has recently found several applications in arithmetic Ramsey theory. The basic observation is that every infinite number in *N corresponds to an ultrafilter on N, and the algebra of ultrafilters is a really powerful tool in this field. Note that this notion also makes sense in any model of PA, where one can consider the 1-type of any infinite number.

Furthermore, nonstandard natural numbers are endowed with a natural compact topology, and one can apply the methods of topological dynamics considering the shift operator $x \mapsto x+1$ . This very peculiar dynamic has interesting characteristics.

In this talk I will also present a new result in the style of Hindman’s Theorem about the existence of infinite monochromatic configurations in any finite coloring of the natural numbers. A typical example is the following monochromatic pattern:
a, b, c, $\ldots$ , a+b+ab, a+c+ac, b+c+bc, $\ldots$ , a+b+c+ab+ac+bc+abc.

Video

​

In this talk, I will present generalisations of some incompleteness results along two axes: r.e. theories are replaced by $\Sigma_{n+1}$-definable ones, and the base theory is pushed down as far as it will go below PA. Such results are often easy to prove from suitably formulated generalisations of facts used in the original proofs. I will present a handful of such facts, including versions of the arithmetised completeness theorem and the Orey–Hájek characterisation, to show what additional assumptions our theories must satisfy for the results to generalise. Two salient classes of theories emerge in this context: (a) $\Sigma_n$-sound extensions of I$\Sigma_n$ + exp, and (b) $\Pi_n$-complete, consistent extensions of I$\Sigma_{n+1}$. Finally, I will discuss some results that fail to generalise to $\Sigma_{n+1}$-definable theories, as well as an open problem related to Woodin's theorem on the universal algorithm.

The presentation is based on the following paper: https://doi.org/10.1017/S1755020321000307

Video

​

This is a joint work with Albert Visser. We prove that no consistent finitely axiomatized theory one-dimensionally interprets its own extension with predicative comprehension. This constitutes a result with the flavor of the Second Incompleteness Theorem whose formulation is completely arithmetic-free. Probably the most important novel feature that distinguishes our result from the previous results of this kind is that it is applicable to arbitrary weak theories, rather than to extensions of some base theory. The methods used in the proof of the main result yield a new perspective on the notion of sequential theory, in the setting of forcing-interpretations. https://arxiv.org/abs/2109.02548

Video

​

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

​

We consider a bounded arithmetic in Buss's language enriched with a predicate Tr which is assumed to be a truth definition for bounded sentences. Among other things we assume polynomial induction for $\Sigma^b_1(\text{Tr})$ formulas. We show that such an arithmetic captures PSPACE. We prove a witnessing theorem for such an arithmetic by an interpretation of free-cuts free proofs of strict $\Sigma^{1,b}_1$ in $U^{1,*}_2$, a canonical second order arithmetic capturing PSPACE. It follows that the problem of the existence of a truth definition for $\Delta_0$ sentences without the totality of $\exp$ might be more about separating subexponential time alternation hierarchies from PSPACE.

The presentation is based on the following article: Konrad Zdanowski, Truth definition for $\Delta_0$ formulas and PSPACE computations, Fundamenta Mathematicae 252(2021) , 1-38.

Video

​

Ali Enayat had asked whether there is a model of Peano arithmetic (PA) that can be represented as $\langle\mathbb Q,\oplus,\otimes\rangle$, where $\oplus$ and $\otimes$ are continuous functions on the rationals $\mathbb Q$. We prove, affirmatively, that indeed every countable model of PA has such a continuous presentation on the rationals. More generally, we investigate the topological spaces that arise as such topological models of arithmetic. The reals $\mathbb{R}$, the reals in any finite dimension $\mathbb{R}^n$, the long line and the Cantor space do not, and neither does any Suslin line; many other spaces do; the status of the Baire space is open.

This is joint work with Ali Enayat, myself and Bartosz Wcisło.

Video

​

One of the strongest second-order arithmetic systems is full second-order arithmetic ${\rm Z}_2$ which asserts that every second-order formula (with any number of set quantifiers) defines a set. We can augment ${\rm Z}_2$ with choice principles such as the choice scheme and the dependent choice scheme. The $\Sigma^1_n$-choice scheme asserts for every $\Sigma^1_n$-formula $\varphi(n,X)$ that if for every $n$, there is a set $X$ witnessing $\varphi(n,X)$, then there is a single set $Z$ whose $n$-th slice $Z_n$ is a witness for $\varphi(n,X)$. The $\Sigma^1_n$-dependent choice scheme asserts that every $\Sigma^1_n$-relation $\varphi(X,Y)$ without terminal nodes has an infinite branch: there is a set $Z$ such that $\varphi(Z_n,Z_{n+1})$ holds for all $n$. The system ${\rm Z}_2$ proves the $\Sigma^1_2$-choice scheme and the $\Sigma^1_2$-dependent choice scheme. The independence of $\Pi^1_2$-choice scheme from ${\rm Z}_2$ follows by taking a model of ${\rm Z}_2$ whose sets are the reals of the Feferman-Levy model of ${\rm ZF}$ in which every $\aleph_n^L$ is countable and $\aleph_\omega^L$ is the first uncountable cardinal.

We construct a model of ${\rm ZF}+{\rm AC}_\omega$ whose reals give a model of ${\rm Z}_2$ together with the full choice scheme in which $\Pi^1_2$-dependent choice fails. This result was first proved by Kanovei in 1979 and published in Russian. It was rediscovered by Sy Friedman and myself with a slightly simplified proof.

Video

​

One of the strongest second-order arithmetic systems is full second-order arithmetic ${\rm Z}_2$ which asserts that every second-order formula (with any number of set quantifiers) defines a set. We can augment ${\rm Z}_2$ with choice principles such as the choice scheme and the dependent choice scheme. The $\Sigma^1_n$-choice scheme asserts for every $\Sigma^1_n$-formula $\varphi(n,X)$ that if for every $n$, there is a set $X$ witnessing $\varphi(n,X)$, then there is a single set $Z$ whose $n$-th slice $Z_n$ is a witness for $\varphi(n,X)$. The $\Sigma^1_n$-dependent choice scheme asserts that every $\Sigma^1_n$-relation $\varphi(X,Y)$ without terminal nodes has an infinite branch: there is a set $Z$ such that $\varphi(Z_n,Z_{n+1})$ holds for all $n$. The system ${\rm Z}_2$ proves the $\Sigma^1_2$-choice scheme and the $\Sigma^1_2$-dependent choice scheme. The independence of $\Pi^1_2$-choice scheme from ${\rm Z}_2$ follows by taking a model of ${\rm Z}_2$ whose sets are the reals of the Feferman-Levy model of ${\rm ZF}$ in which every $\aleph_n^L$ is countable and $\aleph_\omega^L$ is the first uncountable cardinal.

We construct a model of ${\rm ZF}+{\rm AC}_\omega$ whose reals give a model of ${\rm Z}_2$ together with the full choice scheme in which $\Pi^1_2$-dependent choice fails. This result was first proved by Kanovei in 1979 and published in Russian. It was rediscovered by Sy Friedman and myself with a slightly simplified proof.

Video

​

The talk will be a survey of results on first-order theories of pairs (N,M), where M is a model of PA and N is its elementary extension, under various assumptions on the models and on the type of extension. In particular, I will discuss in detail the results on countable recursively saturated models and their cofinal submodels from a joint paper with Jim Schmerl.

Video

​

The talk will be a survey of results on first-order theories of pairs (N,M), where M is a model of PA and N is its elementary extension, under various assumptions on the models and on the type of extension. In particular, I will discuss in detail the results on countable recursively saturated models and their cofinal submodels from a joint paper with Jim Schmerl.

Video

​

The talk will be a survey of results on first-order theories of pairs (N,M), where M is a model of PA and N is its elementary extension, under various assumptions on the models and on the type of extension. In particular, I will discuss in detail the results on countable recursively saturated models and their cofinal submodels from a joint paper with Jim Schmerl.

Video

​

The usual base theory used in reverse mathematics, $\mathrm{RCA}_0$, is the fragment of second-order arithmetic axiomatized by $\Delta^0_1$ comprehension and $\Sigma^0_1$ induction. The weaker base theory $\mathrm{RCA}^*_0$ is obtained by replacing $\Sigma^0_1$ induction with $\Delta^0_1$ induction (and adding the well-known axiom $\exp$ in order to ensure totality of the exponential function). In first-order terms, $\mathrm{RCA}_0$ is conservative over $\mathrm{I}\Sigma_1$ and $\mathrm{RCA}^*_0$ is conservative over $\mathrm{B}\Sigma_1 + \exp$.

Some of the most interesting open problems in reverse mathematics concern the first-order strength of statements from Ramsey Theory, in particular Ramsey's Theorem for pairs and two colours. In this talk, I will discuss joint work with Kasia Kowalik, Tin Lok Wong, and Keita Yokoyama concerning the strength of Ramsey's Theorem over $\mathrm{RCA}^*_0$.

Given standard natural numbers $n,k \ge 2$, let $\mathrm{RT}^n_k$ stand for Ramsey's Theorem for $k$-colourings of $n$-tuples. We first show that assuming the failure of $\Sigma^0_1$ induction, $\mathrm{RT}^n_k$ is equivalent to its own relativization to an arbitrary $\Sigma^0_1$-definable cut. Using this, we give a complete axiomatization of the first-order consequences of $\mathrm{RCA}^*_0 + \mathrm{RT}^n_k$ for $n \ge 3$ (this turns out to be a rather peculiar fragment of PA) and obtain some nontrivial information about the first-order consequences of $\mathrm{RT}^2_k$. Time permitting, we will also discuss the question whether our results have any relevance for the well-known open problem of characterizing the first-order consequences of $\mathrm{RT}^2_2$ over the traditional base theory $\mathrm{RCA}_0$.

In the first part of the talk, we concentrated on Ramsey's Theorem for $n$-tuples where $n \ge 3$. In this second part, the focus will be on $\mathrm{RT}^2_2$.

Video

​

In 2009 Roman Kossak and I showed that the classification of countable models of PA is Borel complete, which means it is as complex as possible. The proof is a straightforward application of Gaifman’s canonical I-models. In 2017 Sam Dworetzky, John Clemens, and I showed that the argument may also be used to show the classification of countable models of ZFC is Borel complete too. In this talk I'll outline the original argument for models of PA, the adaptation for models of ZFC, and briefly consider several subclasses of countable models of ZFC.

Video

​

In 1973, Harvey Friedman proved his striking result on initial self-embeddings of countable nonstandard models of set theory and Peano arithmetic. In this talk, I will discuss my joint work with Ali Enayat focused on the fixed point set of initial self-embeddings of countable nonstandard models of arithmetic. Especially, I will survey the proof of some generalizations of well-known results on the fixed point set of automorphisms of countable recursively saturated models of $ \mathrm{PA} $, to results about the fixed point set of initial self-embeddings of countable nonstandard models of $ \mathrm{I}\Sigma_{1} $.

Video

​

In the theory of nonstandard methods (traditionally known as nonstandard analysis), each mathematical object (a set) $x$ has a uniquely determined so called nonstandard extension ${}^*x$. In general, ${}^*x \supsetneq \{{}^*y; y\in x\}$ - that is, besides the original 'standard' elements ${}^*y$ for $y\in x$, the set ${}^*x$ contains some new 'nonstandard' elements.

For instance, some of the nonstandard elements of ${}^*\mathbb{R}$ can be interpreted as infinitesimals (there is $\varepsilon\in {}^*\mathbb{R}$ such that $0<\varepsilon<1/n$ for all $n\in\mathbb{N}$) allowing for nonstandard analysis to be developed in ${}^*\mathbb{R}$, while ${}^*\mathbb{N}$ turns out to be an (at least $\aleph_1$-saturated) nonstandard elementary extension of $\mathbb{N}$ (in the language of arithmetic).

While the whole nonstandard real analysis is most naturally developed in ${}^*\mathbb{R}$ (with just a few advanced topics where using the second extension ${}^{**}\mathbb{R}$ is convenient, though far from necessary), recent successful applications of nonstandard methods in combinatorics on $\mathbb{N}$ have utilized also higher order extensions ${}^{(n)*}\mathbb{N} = {}^{***\cdots *}\mathbb{N}$ with the chain $***\cdots *$ of length $n>2$.

In this talk we are going to study the structure of the $\omega$-iterated nonstandard extension ${}^{\cdot}\mathbb{N} = \bigcup_{n\in\omega} {}^{(n)*}\mathbb{N}$ of $\mathbb{N}$ and show how the obtained results shed new light on the complexities of Ramsey combinatorics on $\mathbb{N}$ and allow us to drastically simplify proofs of many advanced Ramsey type theorems such as Hindmann's or Milliken's and Taylor's.

Slides

Video

​

In bounded arithmetic, we study weak fragments of arithmetic that often correspond in a certain sense to computational complexity classes (e.g., polynomial time). Questions about provability in such theories can be thought of as a form of feasible reasoning: considering a natural object of interest from a complexity class $C$, can we prove its fundamental properties using only concepts from $C$?

Our objects of interest in this talk will be the elementary integer arithmetic operations $+,-,\times,/$, whose complexity class is (uniform) $\mathrm{TC}^0$, a small subclass of $\mathrm{P}$. The corresponding arithmetical theory is $\mathit{VTC}^0$. Since we do not know yet if the theory can prove the totality of division and iterated multiplication $\prod_{i<n}X_i$ which are in $\mathrm{TC}^0$ by an intricate result of Hesse, Allender, and Barrington, we will also consider an extension of the theory $\mathit{VTC}^0+\mathit{IMUL}$.

Our main question is what can $\mathit{VTC}^0\pm\mathit{IMUL}$ prove about the elementary arithmetic operations. The answer is that more than one might expect: $\mathit{VTC}^0+\mathit{IMUL}$ proves induction for quantifier-free formulas in the basic language of arithmetic ($\mathit{IOpen}$), and even induction and minimization for $\Sigma^b_0$ (sharply bounded) formulas in Buss’s language. This result is connected to the existence of $\mathrm{TC}^0$ constant-degree root-finding algorithms; the proof relies on a formalization of a form of the Lagrange inversion formula in $\mathit{VTC}^0+\mathit{IMUL}$, and on model-theoretic abstract nonsense involving valued fields.

The remaining problem is if $\mathit{VTC}^0$ proves $\mathit{IMUL}$. We will discuss issues with formalization of the Hesse–Allender–Barrington construction in $\mathit{VTC}^0$, and some partial results (this is a work in progress).

Video

​

The usual base theory used in reverse mathematics, $\mathrm{RCA}_0$, is the fragment of second-order arithmetic axiomatized by $\Delta^0_1$ comprehension and $\Sigma^0_1$ induction. The weaker base theory $\mathrm{RCA}^*_0$ is obtained by replacing $\Sigma^0_1$ induction with $\Delta^0_1$ induction (and adding the well-known axiom $\exp$ in order to ensure totality of the exponential function). In first-order terms, $\mathrm{RCA}_0$ is conservative over $\mathrm{I}\Sigma_1$ and $\mathrm{RCA}^*_0$ is conservative over $\mathrm{B}\Sigma_1 + \exp$.

Some of the most interesting open problems in reverse mathematics concern the first-order strength of statements from Ramsey Theory, in particular Ramsey's Theorem for pairs and two colours. In this talk, I will discuss joint work with Kasia Kowalik, Tin Lok Wong, and Keita Yokoyama concerning the strength of Ramsey's Theorem over $\mathrm{RCA}^*_0$.

Given standard natural numbers $n,k \ge 2$, let $\mathrm{RT}^n_k$ stand for Ramsey's Theorem for $k$-colourings of $n$-tuples. We first show that assuming the failure of $\Sigma^0_1$ induction, $\mathrm{RT}^n_k$ is equivalent to its own relativization to an arbitrary $\Sigma^0_1$-definable cut. Using this, we give a complete axiomatization of the first-order consequences of $\mathrm{RCA}^*_0 + \mathrm{RT}^n_k$ for $n \ge 3$ (this turns out to be a rather peculiar fragment of PA) and obtain some nontrivial information about the first-order consequences of $\mathrm{RT}^2_k$. Time permitting, we will also discuss the question whether our results have any relevance for the well-known open problem of characterizing the first-order consequences of $\mathrm{RT}^2_2$ over the traditional base theory $\mathrm{RCA}_0$.

Video

​

In a paper with Kossak in 2018, we studied the notion of neutrality: a subset X of a model M of PA is called neutral if the definable closure relation in (M, X) coincides with that in M. This notion was suggested by Dolich. motivated by work by Chatzidakis-Pillay on generic expansions of theories. In this talk, we will look at a more direct translation of the Chatzidakis-Pillay notion of genericity, which we call 'CP-genericity', and discuss its relation to neutrality. The main result shows that for recursively saturated models, CP-generics are always neutral; previously we had known that not all neutral sets are CP-generic.

Video

​

Recall that if $M \subseteq N$ are models of set theory then $N$ end-extends $M$ if $N$ does not have new elements for sets in $M$. In this talk I will discuss a $\Sigma_1$-definable finite sequence which is universal for end extensions in the following sense. Consider a computably axiomatizable extension $\overline{\mathsf{ZF}}$ of $\mathsf{ZF}$. There is a $\Sigma_1$-definable finite sequence $$a_0, a_1, \ldots, a_n$$ with the following properties.

* $\mathsf{ZF}$ proves that the sequence is finite.
* In any transitive model of $\overline{\mathsf{ZF}}$ the sequence is empty.
* If $M$ is a countable model of $\overline{\mathsf{ZF}}$ in which the sequence is $s$ and $t \in M$ is a finite sequence extending $s$ then there is an end-extension $N \models \overline{\mathsf{ZF}}$ of $M$ in which the sequence is exactly $t$.
* Indeed, for the previous statements it suffices that $M \models \mathsf{ZF}$ and end-extends a submodel $W \models \overline{\mathsf{ZF}}$ of height at least $(\omega_1^{\mathrm{L}})^M$.

This universal finite sequence can be used to determine the modal validities of end-extensional set-theoretic potentialism, namely to be exactly the modal theory $\mathsf{S4}$. The sequence can also be used to show that every countable model of set theory extends to a model satisfying the end-extensional maximality principle, asserting that any possibly necessary sentence is already true.

This talk is about joint work with Joel David Hamkins. The $\Sigma_1$ universal finite sequence is a sister to the $\Sigma_2$ universal finite sequence for rank-extensions of Hamkins and Woodin, and both are cousins of Woodin's universal algorithm for arithmetic.

Video

​

Cofinal extensions generally preserve many more properties of a model of arithmetic than their sisters, end extensions. Exactly how much must or can they preserve? The answer is intimately related to how much arithmetic the model can do. I will survey what is known and what is not known about this question, and report on some recent work on this line.

Slides

Video

In the context of arithmetic, a reflection principle for a theory Th is a formal way of expressing that all theorems of Th are true. In the presence of a truth predicate for the language of Th this principle can be expressed as a single sentence (called the Global Reflection principle over Th) but most often is met in the form of a scheme consisting of all sentences of the form

$\forall x \bigl( \text{Prov}_{\text{Th}}(\phi(\dot{x}))\rightarrow \phi(x)\bigr).$ Obviously such a scheme is not provable in a consistent theory Th. Nevertheless, such soundness assertions are said to provide a natural and justified way of extending ones initial theory.

This perspective is nowadays very fruitfully exploited in the context of formal theories of truth. One of the most basic observations is that strong axioms for the notions of truth follow from formally weak types of axiomatizations modulo reflection principles. In such a way compositional axioms are consequences of the uniform disquotational scheme for for the truth predicate, which is

$\forall x\, \, T(\phi(\dot{x}))\equiv \phi(x).$

The above observation is also used in the recent approach to ordinal analysis of theories of predicative strength by Lev Beklemishev and Fedor Pakhomov. The assignment of ordinal notations to theories proceeds via partial reflection principles (for formulae of a fixed $\Sigma_n$ complexity) over (iterated) disquotational scheme. It becomes important to relate theories of this form to fragments of standard theories of truth, in particular the ones based on induction for restricted classes of formulae such as $\text{CT}_0$ (the theory of compositional truth with $\Delta_0$-induction for the extended language. The theory was discussed at length in Bartek Wcisło's talk). Beklemishev and Pakhomov leave the following open question:

Is $\Sigma_1$-reflection principle over the uniform disquotational scheme provable in $\text{CT}_0$?

The main goal of our talk is to present the proof of the affirmative answer to this question. The result significantly improves the known fact on the provability of Global Reflection over PA in $\text{CT}_0$. During the talk, we explain the theoretical context described above including the information on how the result fits into Beklemishev-Pakhomov project. In the meantime we give a different proof of their characterisation of $\Delta_0$-reflection over the disquotational scheme.

Despite the proof-theoretical flavour of these results, our proofs rests on essentially model-theoretical techniques. The important ingredient is the Arithmetized Completeness Theorem.

Slides

Video

​

A Kaufmann model is an $\omega_1$-like, recursively saturated, rather classless model of PA. Such models were constructed by Kaufmann under the $\diamondsuit$ assumption and then shown to exist in ZFC by Shelah using an absoluteness argument involving the logic $L_{\omega_1, \omega}(Q)$ where $Q$ is the quantifier 'there exists uncountably many…'. It remains an intriguing, if vague, open problem whether one can construct a Kaufmann model in ZFC 'by hand' i.e. without appealing to some form of absoluteness or other very non-constructive methods. In this talk I consider the related problem of axiomatizing Kaufmann models in $L_{\omega_1, \omega}(Q)$ and show that this is independent of ZFC. Along the way we'll see that it is also independent of ZFC whether there is an $\omega_1$-preserving forcing notion adding a truth predicate to a Kaufmann model.

Video

In the 1973 paper 'Countable models of set theory', H. Friedman's investigation of embeddings between countable models of subsystems of ZF yields the following two striking results:

1. Every countable nonstandard model of PA is isomorphic to a proper initial segment of itself.
2. Every countable nonstandard model of a sufficiently strong subsystem of ZF is isomorphic to a proper initial segment that is a union of ranks of the original model.

Note that, in contrast to PA, in the context of set theory there are three alternative notions of 'initial segment': transitive subclass, transitive subclass that is closed under subsets and rank-initial segment. Paul Gorbow, in his Ph.D. thesis, systematically studies versions of H. Friedman's self-embedding that yield isomorphisms between a countable nonstandard model of set theory and a rank-initial segment of itself. In these two talks I will discuss recent joint work with Ali Enayat that investigates models of set theory that are isomorphic to a transitive subclass of itself. We call the maps witnessing these isomorphisms 'initial self-embeddings'. I will outline a proof of a refinement of H. Friedman's Theorem that guarantees the existence of initial self-embeddings for certain subsystems of ZF without the powerset axiom. I will then discuss several examples including a nonstandard model of ZFC minus the powerset axiom that admits no initial self-embedding, and models that separate the three different notions of self-embedding for models of set theory. Finally, I will discuss two interesting applications of our version of H. Freidman's Theorem. The first of these is a refinement of a result due to Quinsey that guarantees the existence of partially elementary proper transitive subclasses of non-standard models of ZF minus the powerset axiom. The second result shows that every countable model of ZF with a nonstandard natural number is isomorphic to a transitive subclass of the hereditarily countable sets of its own constructible universe.​

Slides

Video

Truth theories investigate the notion of truth using axiomatic methods. To a fixed base theory (typically Peano Arithmetic ${\rm PA}$) we add a unary predicate $T(x)$ with the intended interpretation '$x$ is a (code of a) true sentence.' Then we analyse how adding various possible sets of axioms for that predicate affects its behaviour.

One of the aspects which we are trying to understand is which truth-theoretic principles make the added truth predicate 'strong' in that the resulting theory is not conservative over the base theory. Ali Enayat proposed to call this demarcating line between conservative and non-conservative truth theories 'the Tarski boundary.'

Research on Tarski boundary revealed that natural truth theoretic principles extending compositional axioms tend to be either conservative over ${\rm PA}$ or exactly equivalent to the principle of global reflection over $
A$. It says that sentences provable in ${\rm PA}$ are true in the sense of the predicate $T$. This in turn is equivalent to $\Delta_0$ induction for the compositional truth predicate which turns out to be a surprisingly robust theory.

The equivalences between nonconservative truth theories are typically proved by relatively direct ad hoc arguments. However, certain patterns seem common to these proofs. The first one is construction of various arithmetical partial truth predicates which provably in a given theory have better properties than the original truth predicate. The second one is deriving induction for these truth predicates from internal induction, a principle which says that for any arithmetical formula, the set of those elements for which that formula is satisfied under the truth predicate satisfies the usual induction axioms.

As an example of this phenomenon, we will present two proofs. First, we will show that global reflection principle is equivalent to local induction. Global reflection expresses that any sentence provable in ${\rm PA}$ is true. Local induction says that any predicate obtained by restricting truth predicate to sentences of a fixed syntactic complexity $c$ satisfies full induction. This is an observation due to Mateusz Łełyk and the author of this presentation.

The second example is a result by Ali Enayat who showed that ${\rm CT}_0$, a theory compositional truth with $\Delta_0$ induction, is arithmetically equivalent to the theory of compositional truth together with internal induction and disjunctive correctness.

This talk is intended as a continuation of 'Tarski boundary II' presentation at the same seminar. However, we will try to avoid excessive assumptions on familiarity with the previous part.

Video

In the context of arithmetic, a reflection principle for a theory Th is a formal way of expressing that all theorems of Th are true. In the presence of a truth predicate for the language of Th this principle can be expressed as a single sentence (called the Global Reflection principle over Th) but most often is met in the form of a scheme consisting of all sentences of the form

$\forall x \bigl( \text{Prov}_{\text{Th}}(\phi(\dot{x}))\rightarrow \phi(x)\bigr).$ Obviously such a scheme is not provable in a consistent theory Th. Nevertheless, such soundness assertions are said to provide a natural and justified way of extending ones initial theory.

This perspective is nowadays very fruitfully exploited in the context of formal theories of truth. One of the most basic observations is that strong axioms for the notions of truth follow from formally weak types of axiomatizations modulo reflection principles. In such a way compositional axioms are consequences of the uniform disquotational scheme for for the truth predicate, which is

$\forall x\, \, T(\phi(\dot{x}))\equiv \phi(x).$

The above observation is also used in the recent approach to ordinal analysis of theories of predicative strength by Lev Beklemishev and Fedor Pakhomov. The assignment of ordinal notations to theories proceeds via partial reflection principles (for formulae of a fixed $\Sigma_n$ complexity) over (iterated) disquotational scheme. It becomes important to relate theories of this form to fragments of standard theories of truth, in particular the ones based on induction for restricted classes of formulae such as $\text{CT}_0$ (the theory of compositional truth with $\Delta_0$-induction for the extended language. The theory was discussed at length in Bartek Wcisło's talk). Beklemishev and Pakhomov leave the following open question:

Is $\Sigma_1$-reflection principle over the uniform disquotational scheme provable in $\text{CT}_0$?

The main goal of our talk is to present the proof of the affirmative answer to this question. The result significantly improves the known fact on the provability of Global Reflection over PA in $\text{CT}_0$. During the talk, we explain the theoretical context described above including the information on how the result fits into Beklemishev-Pakhomov project. In the meantime we give a different proof of their characterisation of $\Delta_0$-reflection over the disquotational scheme.

Despite the proof-theoretical flavour of these results, our proofs rests on essentially model-theoretical techniques. The important ingredient is the Arithmetized Completeness Theorem.

Slides

Video

​

In the 1973 paper 'Countable models of set theory', H. Friedman's investigation of embeddings between countable models of subsystems of ZF yields the following two striking results:

1. Every countable nonstandard model of PA is isomorphic to a proper initial segment of itself.
2. Every countable nonstandard model of a sufficiently strong subsystem of ZF is isomorphic to a proper initial segment that is a union of ranks of the original model.

Note that, in contrast to PA, in the context of set theory there are three alternative notions of 'initial segment': transitive subclass, transitive subclass that is closed under subsets and rank-initial segment. Paul Gorbow, in his Ph.D. thesis, systematically studies versions of H. Friedman's self-embedding that yield isomorphisms between a countable nonstandard model of set theory and a rank-initial segment of itself. In these two talks I will discuss recent joint work with Ali Enayat that investigates models of set theory that are isomorphic to a transitive subclass of itself. We call the maps witnessing these isomorphisms 'initial self-embeddings'. I will outline a proof of a refinement of H. Friedman's Theorem that guarantees the existence of initial self-embeddings for certain subsystems of ZF without the powerset axiom. I will then discuss several examples including a nonstandard model of ZFC minus the powerset axiom that admits no initial self-embedding, and models that separate the three different notions of self-embedding for models of set theory. Finally, I will discuss two interesting applications of our version of H. Freidman's Theorem. The first of these is a refinement of a result due to Quinsey that guarantees the existence of partially elementary proper transitive subclasses of non-standard models of ZF minus the powerset axiom. The second result shows that every countable model of ZF with a nonstandard natural number is isomorphic to a transitive subclass of the hereditarily countable sets of its own constructible universe.​

Truth theories investigate the notion of truth with axiomatic methods. To a fixed base theory (typically Peano Arithmetic ${\rm PA}$) we add a unary predicate $T(x)$ with the intended interpretation '$x$ is a (code of a) true sentence.' Then we analyse how adding various possible sets of axioms for that predicate affects its behaviour.

One of the aspects we are trying to understand is which truth-theoretic principles make the added truth predicate 'strong' in that the resulting theory is not conservative over the base theory. Ali Enayat proposed to call this 'demarcating line' between conservative and non-conservative truth theories 'the Tarski boundary.'

Research on Tarski boundary revealed that natural truth theoretic principles extending compositional axioms tend to be either conservative over ${\rm PA}$ or exactly equivalent to the principle of global reflection over ${\rm PA}$. It says that sentences provable in ${\rm PA}$ are true in the sense of the predicate $T$. This in turn is equivalent to $\Delta_0$ induction for the compositional truth predicate which turns out to be a surprisingly robust theory.

In our talk, we will try to sketch proofs representative of research on Tarski boundary. We will present the proof by Enayat and Visser showing that the compositional truth predicate is conservative over ${\rm PA}$. We will also try to discuss how this proof forms a robust basis for further conservativeness results.

On the non-conservative side of Tarski boundary, the picture seems less organised, since more arguments are based on ad hoc constructions. However, we will try to show some themes which occur rather repeatedly in these proofs: iterated truth predicates and the interplay between properties of good truth-theoretic behaviour and induction. To this end, we will present the argument that disjunctive correctness together with the internal induction principle for a compositional truth predicate yields the same consequences as $\Delta_0$-induction for the compositional truth predicate (as proved by Ali Enayat) and that it shares arithmetical consequences with global reflection. The presented results are currently known to be suboptimal.

This talk is intended as a continuation of 'Tarski boundary' presentation. However, we will try to avoid excessive assumptions on familiarity with the previous part.

There is a well-known close logical connection between PA and finite set theory. Is there a set theory that corresponds in an analogous way to bounded arithmetic $I\Delta_0$? I propose a candidate for such a theory, called $I\Delta_0S$, and consider the questions: what set-theoretic axioms can it prove? And given a model M of $I\Delta_0$ is there a model of $I\Delta_0S$ whose ordinals are isomorphic to M? The answer is yes if M is a model of Exp; to obtain the answer we use a new way of coding sets by numbers.

Slides

The subject of this two-part talk is a 1975 Barwise-Schlipf landmark paper, whose main theorem asserts that a nonstandard model M of PA is recursively saturated iff M has an expansion to a model of the subsystem $\Delta^{1}_{1}-CA_0$ of second order arithmetic. The impression one gets from reading the Barwise-Schlipf paper is that the left-to-right direction of the theorem is deep since it relies on sophisticated techniques from admissible set theory, and that the other direction is fairly routine.

As it turns out, the exact opposite is the case: the left-to-right direction of the Barwise-Schlipf theorem lends itself to a proof from first principles (as observed independently by Jonathan Stavi and Sol Feferman not long after the appearance of the Barwise-Schmerl paper); and moreover, as recently shown in my joint work with Jim Schmerl, there is a crucial error in the Barwise-Schlipf proof of the right-to-left direction of the theorem, an error that can be circumvented by a rather nontrivial argument. As I will explain, certain results from the joint work of Matt Kaufmann and Jim Schmerl in the mid-1980s on 'lofty' models of arithmetic come in handy for the analysis of the error, and for circumventing it.

In part I, after going over some history, and preliminaries, I will discuss (1) the gap in the Barwise-Schlipf paper, and (2) the aforementioned Feferman-Stavi proof. In part II, I will focus on how the gap can be circumvented with a proof strategy very different from that Barwise and Schlipf.​

Slides

​

The subject of this two-part talk is a 1975 Barwise-Schlipf landmark paper, whose main theorem asserts that a nonstandard model M of PA is recursively saturated iff M has an expansion to a model of the subsystem $\Delta^{1}_{1}-CA_0$ of second order arithmetic. The impression one gets from reading the Barwise-Schlipf paper is that the left-to-right direction of the theorem is deep since it relies on sophisticated techniques from admissible set theory, and that the other direction is fairly routine.

As it turns out, the exact opposite is the case: the left-to-right direction of the Barwise-Schlipf theorem lends itself to a proof from first principles (as observed independently by Jonathan Stavi and Sol Feferman not long after the appearance of the Barwise-Schmerl paper); and moreover, as recently shown in my joint work with Jim Schmerl, there is a crucial error in the Barwise-Schlipf proof of the right-to-left direction of the theorem, an error that can be circumvented by a rather nontrivial argument. As I will explain, certain results from the joint work of Matt Kaufmann and Jim Schmerl in the mid-1980s on 'lofty' models of arithmetic come in handy for the analysis of the error, and for circumventing it.

In part I, after going over some history, and preliminaries, I will discuss (1) the gap in the Barwise-Schlipf paper, and (2) the aforementioned Feferman-Stavi proof. In part II, I will focus on how the gap can be circumvented with a proof strategy very different from that Barwise and Schlipf.​

Slides

​

Recall that given a complete theory $T$ and a type $p(x)$ the Hanf number for $p(x)$ is the least cardinal $\kappa$ so that any model of $T$ of size $\kappa$ realizes $p(x)$ (if such a $\kappa$ exists and $\infty$ otherwise). The Hanf number for $T$, denoted $H(T)$, is the supremum of the successors of the Hanf numbers for all possible types $p(x)$ whose Hanf numbers are $\lt\infty$. We have seen so far in the seminar that for any complete, consistent $T$ in a countable language $H(T) \leq \beth_{\omega_1}$ (a result due to Morley). In this talk I will present the following theorems: (1) The Hanf number for true arithmetic is $\beth_{\omega}$ (Abrahamson-Harrington-Knight) but (2) the Hanf number for False Arithmetic is $\beth_{\omega_1}$ (Abrahamson-Harrington)

PA is the first order fragment of Peano's axiomatization of the natural numbers. The natural numbers, N, is called the standard model of PA. But by compactness theorem in first order logic, there are also models of PA different from N, which are called non-standard models of arithmetic. Like in N, every element of a non-standard model M has a binary expansion, which can be regarded as the characteristic function of a subset of N. The standard system of M is the collection of all such subsets of N. It is known that standard systems of non-standard models are always Scott sets and every Scott set of cardinality less than or equal to the first uncountable cardinal is the standard system of some non-standard model. However, the general Scott set problem, whether every Scott set is the standard system of some non-standard model, remains one of the major open problems in the model theory of arithmetic. This talk will present some history of Scott set problem, as well as two constructions of non-standard models with uncountable standard systems.

Slides

When $A \subseteq \mathcal{M} \vDash PA^{\ast}$, we say that $A$ is a basis for $\mathcal{M}$ if for all $X \subseteq A$, the submodel $M_{X}$ generated by $X$ is the unique $\mathcal{N} \prec \mathcal{M}$ such that $X = \mathcal{N} \cap A$, and that such $A$ is solid if for all finite $X,Y \subseteq A$, whenever $f: \mathcal{M}_{X} \to \mathcal{M}_{Y}$ is an isomorphism, then $f \upharpoonright_{X}$ is one-to-one onto $Y$. We will discuss what role a solid basis can play in controlling the amount of indiscernibility and the automorphisms of a model. Also, using a set of types called an 'AH-set', we will construct a solid basis.

In this talk, we will review Morley's 1963 article 'Omitting Classes of Elements' (in modern parlance, omitting types). In this paper, Morley investigates the question of how large a structure's cardinality must be before it is forced to realize a type (for example, an ordered field with cardinality greater than the continuum must contain non-Archimedean elements). Given a fixed language, there is a cardinal $\kappa$ such that for every theory $T$ and any type $\Sigma$, if $T$ has a model of size $\kappa$ omitting $\Sigma$ then it has such a model in every cardinality. Morley's main result is that given a countable language $L$, if for every $\alpha < \omega_1$ there is a model of $T$ of size $\geq \beth_\alpha$ which omits $\Sigma$, then there is such a model in every cardinality (and if $L$ has at most $\aleph_\beta$ symbols, we replace '$\omega_1$' in this statement by '$\omega_{\gamma + 1}$' where $2^{\aleph_\beta} = \aleph_\gamma$). The proof uses the Erdős–Rado partition theorem and indiscernible sequences.

I will continue to speak about the construction in Jim Schmerl's paper on the pentagon lattice.

The goal of Gödel’s argument that the theory (T) of Peano Arithmetic is not complete, was to show that the Gödel sentences, $G$ , and it’s negation, are not provable in T, unless T is inconsistent. In this paper we examine the first half of this argument, namely, that from a hypothetical derivation, $P_{G}$, of $G$, a derivation, $P_{f}$, can be constructed that ends in a contradiction. We make the observation that the Gödel argument depends on the metatheory concept of representability that, in turn, depends on the metatheory concept of soundness. Our analysis leads to two main observations, the first well know, and the second, a challenge to the standard undecidability argument.

1 – The existence of $P_G$ implies that T is unsound. This conclusion does not require the further construction, from $P_G$, of the derivation $P_f$.

2 - We argue that effectuation of the construction of $P_f$ is obstructed, because that effectuation requires acceptance of a contradiction in the metatheory regarding the soundness of T.

This is joint work with Catherine Hennix.

I will continue to speak about Jim Schmerl's recent paper on the pentagon lattice $\mathbf{N}_5$. In this talk, I will outline the main result that no model of PA has a 'mixed' elementary extension such that the resulting interstructure lattice is isomorphic to the pentagon.