Calendar
September 6:
Set Theory Seminar
11:00am NY time
Hybrid (email Victoria Gitman for meeting id)
Room: 3207
Reflecting Ordinals and Forcing
Corey Switzer
Kurt Gödel Research Center
Abstract
Let $n \lt \omega$ and $\Gamma$ either $\Pi$ or $\Sigma$. An ordinal $\alpha$ is called $\Gamma^1_n$-reflecting if for each $\beta \lt\alpha$ and each $\Gamma^1_n$-formula $\varphi$ if $L_\alpha \models \varphi(\beta)$ then there is a $\gamma \in (\beta, \alpha)$ so that $L_\gamma \models \varphi(\beta)$ where here $\models$ refers to full second order logic. The least $\Sigma^1_n$-reflecting ordinal is called $\sigma^1_n$ and the least $\Pi^1_n$-ordinal is called $\pi^1_n$. These ordinals provably exist and are countable (for all $n \lt \omega$). They arise naturally in proof theory, particularly in calibrating consistency strength of strong arithmetics and weak set theories. Moreover, surprisingly, their relation to one another relies heavily on the background set theory. If $V=L$ then for all $n \lt \omega$ we have $\sigma^1_{n+3} \lt \pi^1_{n+3}$ (due to Cutland) while under PD for all $n \lt \omega$ we have $\sigma^1_n \lt \pi^1_n$ if and only if $n$ is even (due to Kechris).
Surprisingly nothing was known about these ordinals in any model which satisfies neither $V=L$ nor PD. In this talk I will sketch some recent results which aim at rectifying this. In particular we will show that in any generic extension by any number of Cohen or Random reals, a Sacks, Miller or Laver real, or any lightface, weakly homogeneous Borel ccc forcing notion agrees with $L$ about which ordinals are $\Gamma^1_n$-reflecting (for any $n$ and $\Gamma$). Meanwhile, in the generic extension by collapsing $\omega_1$ many interesting things happen, not least amongst them that $\sigma^1_n$ and $\pi^1_n$ are increased - yet still below $\omega_1^L$ for $n > 2$. Along the way we will discuss the plethora of open problems in this area. This is joint work with Juan Aguilera.
Video
September 6:
Logic Workshop
2:00pm NY time
Room: 4419 (NOTICE THE ROOM CHANGE!)
Weak and Strong Variants of Baumgartner's Axiom for Polish Spaces
Corey Switzer
Kurt Gödel Research Center
Abstract
(One version of) Cantor's second best theorem states that every pair of countable, dense sets of reals are isomorphic as linear orders. From the perspective of set theory it's natural to ask whether some variant of this theorem can hold consistently when 'countable' is replaced by 'uncountable'. This was shown in the affirmative by Baumgartner in 1973 who showed the consistency of 'all $\aleph_1$-dense sets of reals are order isomorphic' where a set is $\kappa$-dense for a cardinal $\kappa$ if its intersection with any open interval has size $\kappa$. The above became known as Baumgartner's axiom, denoted BA, and is an important axiom in both combinatorial set theory and set theoretic topology. BA has natural higher dimensional analogues - i.e., statements with the same relation to $\mathbb R^n$ that BA has to $\mathbb R$. It is a long standing open conjecture of Steprāns and Watson that BA implies its higher dimensional analogues.
In the talk I will describe some attempts to break the ice on this open problem mostly by looking at a family of weaker and stronger variants of BA and investigating their combinatorial, analytic and topological consequences. We will show that while some weak variants of BA have all the same consequences as BA, even weaker ones do not. Meanwhile a strengthening of BA for Baire and Polish space gives much more information.
September 13:
Logic Workshop
2:00pm NY time
Room: 4419 (NOTICE THE ROOM CHANGE!)
Rigid real closed fields
David Marker
University of Illinois at Chicago
Abstract
Shelah showed that it is consistent that there are uncountable rigid non-archimedean real closed fields and, later, he and Mekler proved this in $\textbf{ZFC}$. Answering a question of Enayat, Charlie Steinhorn and I show that there are countable rigid non-archimedean real closed fields by constructing one of transcendence degree two.
September 20:
Logic Workshop
No seminar
September 27:
Logic Workshop
2:00pm NY time
Room: 4419
Baby measurable cardinals
Victoria Gitman
CUNY
Abstract
Measurable cardinals and other large cardinals on the larger side of things are characterized by the existence of elementary embeddings $j:V\to \mathcal M$ from the universe $V$ of sets into a transitive submodel $\mathcal M$. The clear pattern the large cardinals in that region follow is that the closer the submodel $\mathcal M$ is to $V$ the stronger the large cardinal notion. Smaller large cardinals, such as weakly compact or Ramsey cardinals, are known chiefly for their combinatorial properties, such as the existence of large homogeneous sets for colorings. But, it turns out that they too have elementary embeddings characterizations with embeddings on the correspondingly small models $M$ of (a fragment) of set theory (usually ${\rm ZFC}^-$, the theory ${\rm ZFC}$ with powerset axiom removed). Elementary embeddings of $V$ are often by-definable with the existence of certain ultrafilters or systems of ultrafilters. The classical example is that $\kappa$ is measurable if and only if there is a $\kappa$-complete ultrafilter on $\kappa$. The model $\mathcal M$ is then the transitive collapse of the ultrapower of $V$ by $U$. The connection between elementary embedding and ultrafilters also exists in the case of the small elementary embeddings. A typical elementary embedding characterization of a small large cardinal $\kappa$ follows the following template: for every $A\subseteq\kappa$, there is a (technical condition) model $M$, with $A\in M$, for which there is an $M$-ultrafilter $U$ on $\kappa$ with (technical properties). A subset $U\subseteq P(\kappa)\cap M$ is an $M$-ultrafilter if the structure $\langle M,\in, U\rangle$, with a predicate for $U$, satisfies that $U$ is a $\kappa$-complete ultrafilter on $\kappa$, meaning that $U$ measures all the sets in $M$ and its completeness applies to sequences that are elements of $M$. The reason we need to add a predicate for $U$ is that in most interesting case, and in contrast to the situation with measurable cardinals, $U$ is not an element of $M$ (indeed in most cases, $P(\kappa)$ does not exist in $M$). While the structure $M$ usually satisfies some large fragment of ${\rm ZFC}$, once, we add a predicate for the $M$-ultrafilter $U$, the structure $\langle M,\in, U\rangle$ can fail to satisfy even $\Sigma_0$-separation. In this talk, I will discuss how smaller large cardinals follow the pattern that the more set theory the structure $\langle M,\in, U\rangle$ satisfies the stronger the resulting large cardinal notion. I will use these observations to introduce a new hierarchy of large cardinals between Ramsey and measurable cardinals. This is joint work with Philipp Schlicht, based on earlier work by Bovykin and McKenzie.
September 27:
Set Theory Seminar
11:00am NY time
Hybrid (email Victoria Gitman for meeting id)
Room: 3207
Cichoń's maximum with the uniformity and the covering of the $\sigma$-ideal $\mathcal{E}$ generated by closed null sets
Takashi Yamazoe
Kobe University
Abstract
Let $\mathcal{E}$ denote the $\sigma$-ideal generated by closed null sets on $\mathbb{R}$. We show that the uniformity and the covering of $\mathcal{E}$ can be added to Cichoń's maximum with distinct values, more specifically, it is consistent that $\aleph_1\lt\mathrm{add}(\mathcal{N})\lt\mathrm{cov}(\mathcal{N})\lt\mathfrak{b}\lt\mathrm{non}(\mathcal{E})\lt\mathrm{non}(\mathcal{M})\lt\mathrm{cov}(\mathcal{M})\lt\mathrm{cov}(\mathcal{E})\lt\mathfrak{d}\lt\mathrm{non}(\mathcal{N})\lt\mathrm{cof}(\mathcal{N})\lt2^{\aleph_0}$ holds.
Video
October 4:
Logic Workshop
No seminar
CUNY holiday
October 11:
Logic Workshop
No seminar
CUNY holiday
October 18:
Logic Workshop
2:00pm NY time
Room: 4419
Old and new decidability results for theories of Abelian lattice-ordered groups
Brian Wynne
CUNY
Abstract
An Abelian lattice-ordered group (l-group) is an Abelian group with a lattice order that is invariant under translations. Examples include $C(X)$, the set of continuous real-valued functions on a topological space $X$ with pointwise operations and order, the $L_p$ spaces, and certain spaces of measures. After surveying some of the known decidability results for various classes of l-groups, I will present new decidability results concerning existentially closed l-groups.
October 18:
Set Theory Seminar
11:00am NY time
Hybrid (email Victoria Gitman for meeting id)
Room: 3207
On a cofinal Reinhardt embedding without Powerset
Hanul Jeon
Cornell University
Abstract
Reinhardt embedding is an elementary embedding from $V$ to $V$ itself, whose existence was refuted under the Axiom of Choice by Kunen's famous theorem. There were attempts to get a consistent version of a Reinhardt embedding, and dropping the Axiom of Powerset is one possibility. Richard Matthews showed that $\mathsf{ZFC} + \mathrm{I}_1$ proves $\mathsf{ZFC}$ without Powerset is consistent with a Reinhardt embedding, but the embedding $j\colon V\to V$ in the Matthews' model does not satisfy the cofinality (i.e., for every set $a$ there is $b$ such that $a\in j(b)$). In this talk, I will show from $\mathsf{ZFC} + \mathrm{I}_0$ that $\mathsf{ZFC}$ without Powerset is consistent with a cofinal Reinhardt embedding.
Video
October 25:
Logic Workshop
2:00pm NY time
Room: 4419
Computing away negation using ancients: from existential to Diophantine sentences
Hans Schoutens
CUNY
Abstract
Last semester, I discussed geometric methods for decidability over a complete discrete valuation ring (DVR) in equal characteristic, suggesting that these methods could be applied effectively. In this talk, I aim to clarify the computability issues surrounding this topic while at the same time shifting focus to the case of mixed characteristic. Whereas quantifier elimination (QE) results are established for p-adic numbers, the general landscape remains less explored. I will demonstrate that for any existential sentence over a computable ring, we can effectively construct a positive existential (or Diophantine) sentence which is logically equivalent to the original in every excellent Henselian DVR containing the ring. This construction hinges on Resolution of Singularities, which is feasible in characteristic zero.
Furthermore, I will utilize ultraproducts, specifically the protoproduct variant, to show how Diophantine statements over a DVR can be reduced to those over a residue ring. Since the residue ring is Artinian—and in the case of p-adics, even finite—the associated problems become significantly more manageable. However, it is important to note that this approach does not yet yield a general QE result, as it applies only to sentences, not formulas. The challenge lies in the dependence of certain effective bounds on parameters. I will provide insights into how to derive a bound based on a refined notion of complexity within the equational system—beyond simply considering its degree—using ultraproducts. Additionally, I will address a request from the audience in my last talk by demonstrating that this bound is indeed effective.
And somehow it will also require some delving into the theory of Witt vectors and ancient elements, as I will explain.
October 25:
Set Theory Seminar
11:00am NY time
Hybrid (email Victoria Gitman for meeting id)
Room: 3207
More Borel chromatic numbers
Stefan Geschke
University of Hamburg
Abstract
Borel chromatic numbers of definable graphs on Polish spaces have been studied for 25 years, starting with the seminal paper by Kechris, Solecky and Todorcevic. I will talk about some recent results about the consistent separation of uncountable Borel chromatic numbers of some particular graphs and about the Borel chromatic number of graphs related to Turing reducibility.
Slides
Video
October 29:
MOPA
1:00pm NY time
Virtual (email Victoria Gitman for meeting id)
The Kaufmann–Clote question on end extensions of models of arithmetic and the weak regularity principle
Sun Mengzhou
National University of Singapore
Abstract
We investigate the end extendibility of models of arithmetic with restricted elementarity. By utilizing the restricted ultrapower construction in the second-order context, for each $n \in \mathbb{N}$ and any countable model of $\mathrm{B}\Sigma_{n+2}$, we construct a proper $\Sigma_{n+2}$-elementary end extension satisfying $\mathrm{B}\Sigma_{n+1}$, which answers a question by Clote positively. We also give a characterization of countable models of $\mathrm{I}\Sigma_{n+2}$ in terms of their end extendibility similar to the case of $\mathrm{B}\Sigma_{n+2}$. Along the proof, we will introduce a new type of regularity principles in arithmetic called the weak regularity principle, which serves as a bridge between the model's end extendibility and the amount of induction or collection it satisfies.
The talk is based on this paper from arxiv:2409.03527.
Slides
Video
November 1:
Logic Workshop
No seminar
There will be no Logic Workshop talk at CUNY on November 1, the first day of the three-day Rutgers MAMLS Fall Fest. Talks this afternoon are to be given by Justin Moore (3:00 pm) and Valentina Harizanov (4:30 pm) in Rutgers University’s Murray Hall in downtown New Brunswick, NJ. Those planing to attend should please register in advance here, where further information is available.
November 5:
MOPA
1:00pm NY time
Virtual (email Victoria Gitman for meeting id)
Separations between categoricity-like properties of first-order theories
Piotr Gruza
University of Warsaw
Abstract
A theory is tight if and only if every two extensions of it, in the language of that theory, are bi-interpretable iff they are equal. The property of being tight can be seen as a kind of local categoricity in a suitable category of theories and interpretations. Examples of tight theories include $\text{PA}$, $\text{Z}_{2}$, $\text{ZF}$, and $\text{KM}$. Neatness, semantic tightness, and solidity are strengthenings of tightness, with solidity being the strongest and the other two being intermediate. During the talk we will focus on relations between those properties in the context of arithmetic theories and theories of finite sets.
Partly based on a joint work with Leszek Kołodziejczyk and Mateusz Łełyk.
Video
November 8:
Set Theory Seminar
11:00am NY time
Hybrid (email Victoria Gitman for meeting id)
Room: 3207
Distributivity and Base trees for $P(\kappa)/ {\lt} \kappa$
Geoff Galgon
Abstract
For $\kappa$ a regular uncountable cardinal, we show that distributivity and base trees for $P(\kappa)/{\lt}\kappa$ of intermediate height in the cardinal interval $[\omega, \kappa)$ exist in certain models. We also show that base trees of height $\kappa$ can exist as well as base trees of various heights $\geq \kappa^+$ depending on the spectrum of cardinalities of towers in $P(\kappa)/{\lt}\kappa$. These constructions answer questions of V. Fischer, M. Koelbing, and W. Wohofsky in certain models.
Slides
Video
November 8:
Logic Workshop
2:00pm NY time
Room: 4419
External definability
Artem Chernikov
University of Maryland
Abstract
An object (e.g. a set, a relation, a group, etc.) is externally definable in a structure $M$ if it is given by the intersection with $M$ of an object definable (with parameters) in some elementary extension of $M$. If all types over $M$ are definable (for example, if the theory of $M$ is stable), then all externally definable sets are already definable. This fails beyond stability, e.g. in linear orders (take a cut of some irrational number over the rationals) or in the Rado graph (where all subsets of a model are externally definable). An important theorem of Shelah shows that at least the expansion of an NIP structure $M$ by all externally definable sets $M^{\text{ext}}$ remains NIP. While externally definable sets in NIP structures are well behaved, partially explained by the existence of 'honest definitions' introduced in joint work with Simon, many questions remain open. In this talk I will survey some topics in the study of externally definable sets and discuss some new results on externally definable groups in NIP structures.
November 12:
MOPA
1:00pm NY time
Virtual (email Victoria Gitman for meeting id)
Separations between categoricity-like properties of first-order theories: part II
Piotr Gruza
University of Warsaw
Abstract
A theory is tight if and only if every two extensions of it, in the language of that theory, are bi-interpretable iff they are equal. The property of being tight can be seen as a kind of local categoricity in a suitable category of theories and interpretations. Examples of tight theories include $\text{PA}$, $\text{Z}_{2}$, $\text{ZF}$, and $\text{KM}$. Neatness, semantic tightness, and solidity are strengthenings of tightness, with solidity being the strongest and the other two being intermediate. During the talk we will focus on relations between those properties in the context of arithmetic theories and theories of finite sets.
Partly based on a joint work with Leszek Kołodziejczyk and Mateusz Łełyk.
Video
November 15:
Logic Workshop
2:00pm NY time
Room: 4419
Computable reductions on groups and fields
Russell Miller
CUNY
Abstract
Hjorth and Thomas established that the complexity of the isomorphism problem for torsion-free abelian groups of finite rank grows dramatically higher as the rank increases: for each $r$, there is no Borel function $F$ that maps each rank-$(r+1)$ group $G$ to a rank-$r$ group $F(G)$ in such a way that $G_0\cong G_1\iff F(G_0)\cong F(G_1)$. We say that there is no Borel reduction from isomorphism on $\operatorname{TFAb}_{r+1}$ to isomorphism on $\operatorname{TFAb}_r$. (From lower to higher rank, in contrast, such a reduction is readily seen.)
Fields of transcendence degree $r$ over $\mathbb Q$ have very similar computability properties to groups in $\operatorname{TFAb}_r$. This being so, we extend their investigations to include the isomorphism relations on the classes $\operatorname{FD}_r$ of such fields. We show that there do exist reductions (not merely Borel, but actually computable, and moreover functorial) from each $\operatorname{TFAb}_r$ to the corresponding $\operatorname{FD}_r$, and also from each $\operatorname{FD}_r$ to $\operatorname{FD}_{r+1}$ (which proves more challenging than it was for the groups!). It remains open whether a theorem analogous to that of Hjorth-Thomas holds for the fields, but we use the notion of countable reductions to show that the fundamental obstacle to a reduction from $\operatorname{TFAb}_{r+1}$ to $\operatorname{TFAb}_r$ is the uncountability of these spaces. This is joint work with Meng-Che 'Turbo' Ho and Julia Knight.
November 15:
Set Theory Seminar
11:00am NY time
Hybrid (email Victoria Gitman for meeting id)
Room: 3207
Definable hypergraphs on large spaces
Philipp Schlicht
University of Siena
Abstract
The open graph dichotomy states that the complete graph on the Cantor space is least among open graphs on analytic sets with respect to the ordering given by continuous graph homomorphisms. Ben Miller used dichotomies of this form to prove many interesting theorems in descriptive set theory. I will survey some applications to the descriptive set theory of generalised Cantor spaces. Recent results include connections with the determinacy of a class of long games.
Video
November 19:
MOPA
1:00pm NY time
Virtual (email Victoria Gitman for meeting id)
Saturation properties for propositionally sound satisfaction classes
Bartosz Wcisło
University of Gdańsk
Abstract
Over the last years, a lot of progress has been achieved in understanding the arithmetical strength of axiomatic theories of compositional truth. It turned out that a theory $\mathsf{CT}^-$ of compositional truth for arithmetical sentences can become non-conservative over $\mathsf{PA}$ upon adding some seemingly benign principles.
One of the principles whose arithmetical strength is still unknown is the axiom of propositional soundness which says that for any arithmetical sentence $\phi$ which is a propositional tautology, $\phi$ is true in the sense of the truth predicate. It is an open problem whether this axiom together with $CT^-$ is conservative over $PA$.
In our talk, we will show that if $(M,T)$ is a model of $\mathsf{CT}^-$ satisfying the propositional soundness principle, then $(M,T)$ satisfies a certain amount of saturation: if $(\phi_i)_{i \lt c}$ is a sequence of sentences such that for any standard $i$, $\phi_i$ is true in the sense of the truth predicate, then there is a nonstandard $d$ such that for each $i \in [0,d]$, $\phi_i$ is true. This puts very strong limitations on any possible conservativeness proof. The result may be seen as a counterpart to the classical theorem of Lachlan which says that the arithmetical part of any model of $\mathsf{CT}^-$ is recursively saturated.
Video
November 22:
Set Theory Seminar
Special time: 10:30am NY time
Hybrid (email Victoria Gitman for meeting id)
Room: 3207
Identity crises phenomena between the first supercompact cardinal and Vopěnka's Principle
Alejandro Poveda
Harvard University
Abstract
We will report on some recent results on the large cardinal hierarchy between the first supercompact cardinal and Vopěnka's Principle. We present various consistency results as well as a conjecture as for how the large-cardinal hierarchy of $\text{Ultimate}$-$L$ looks like at these latitudes. The main result will be the consistency with very large cardinals of a new Kimchi-Magidor configuration; namely, we will present a model where every supercompact cardinal is supercompact with inaccessible target points. This answers a question of Bagaria and Magidor. This configuration is a consequence of a new axiom (named $\mathcal A$) which regards the mutual relationship between superstrong and tall cardinals. Time permitting we shall discuss the interplay between $\mathcal A$ and $\text{Ultimate}$-$L$ and propose a few open questions.
Video
November 26:
MOPA
1:00pm NY time
Virtual (email Victoria Gitman for meeting id)
Well-founded models of fragments of Collection
Zachiri Mckenzie
University of Chester
Abstract
Let $\mathsf{M}$ be the weak set theory (with powersets) axiomatised by: $\textsf{Extensionality}$, $\textsf{Pair}$, $\textsf{Union}$, $\textsf{Infinity}$, $\textsf{Powerset}$, transitive containment ($\textsf{TCo}$), $\Delta_0\textsf{-Separation}$ and $\textsf{Set-Foundation}$. In this talk I will discuss the relationship between two alternative versions of the set-theoretic collection scheme: Collection and Strong Collection. Both of these schemes yield $\mathsf{ZF}$ when added to $\mathsf{M}$, but when restricted the $\Pi_n$-formulae (denoted $\Pi_n\textsf{-Collection}$ and $\textsf{Strong } \Pi_n\textsf{-Collection}$) these alternative versions of set-theoretic collection differ. In particular, over the theory $\mathsf{M}$, $\textsf{Strong }\Pi_n\textsf{-Collection}$ is equivalent to $\Pi_n\textsf{-Collection}+\Sigma_{n+1}\textsf{-Separation}$. And, $\mathsf{M}+\textsf{Strong }\Pi_n\textsf{-Collection}$ proves the consistency of $\mathsf{M}+\Pi_n\textsf{-Collection}$. In this talk I will show that, despite this difference in consistency strength, every countable well-founded model of $\mathsf{M}+\Pi_n\textsf{-Collection}$ satisfies $\textsf{Strong } \Pi_n\textsf{-Collection}$. If time permits I will outline how this argument can be refined to show that $\mathsf{M}+\Pi_n\textsf{-Collection}+\Pi_{n+1}\textsf{-Foundation}$ proves $\Sigma_{n+1}\textsf{-Separation}$.
Video
November 29:
Logic Workshop
No seminar
CUNY holiday: happy Thanksgiving!
December 3:
MOPA
1:00pm NY time
Virtual (email Victoria Gitman for meeting id)
Varieties of truth definitions
Mateusz Łełyk
University of Warsaw
Abstract
In the talk we address the following problem: how many essentially different truth definitions (for the language of arithmetic) are there? Formally, a truth definition for us is just a sentence $\phi$ in some language $L$, which extends the elementary arithmetic (a.k.a. $I\Delta_0 + \exp$) and such that for some $L$-formula $\Theta(x)$, $$\phi\vdash \psi\equiv\Theta(\ulcorner\psi\urcorner),$$ for every sentence $\psi$ in the language of arithmetic. In other words $\phi$ is a sentence which can define a truth predicate for arithmetic (via a formula $\Theta(x)$). We investigate the structure of the definability relation between so defined truth definitions. To be more precise: we say that a truth definition $\phi$ (in a language $L$) defines a truth definition $\phi'$ (in a language $L'$) if and only if there are $L$-formulae $A_1,\ldots,A_n$ such that $\phi\vdash \phi'[A_1/R_1,\ldots,A_n/R_n]$, where $R_i$'s are all the non-arithmetical predicates from the language $L'$ and $\phi'[A_1/R_1,\ldots,A_n/R_n]$ denotes the result of translating $\phi'$ by substituting $A_i$ for each occurrence of $R_i$. We note that this translation does not relativize the quantifiers in $\phi'$ and keeps the arithmetical symbols unchanged. Our main result is that the structure consisting of truth definitions which are conservative over the basic arithmetical theory forms a countable universal distributive lattice. Additionally, we (slightly) generalize the result of Pakhomov and Visser showing that the set of (Gödel codes of) definitions of truth is not $\Sigma_2$-definable in the standard model of arithmetic.
This is joint work with Piotr Gruza which was published in here.
Video
December 6:
Logic Workshop
2:00pm NY time
Room: 4419
Lattices of elementary submodels of recursively saturated models of PA
Roman Kossak
CUNY
Abstract
Much work on elementary submodels of recursively saturated models of PA was done, beginning in the 1980s, by Craig Smoryński, Richard Kaye, Henryk Kotlarski, Jim Schmerl, and myself. The set of all elementary substructures of a recursively saturated model $M$ ordered by inclusion forms a lattice $Lt(M)$. Kotlarski asked whether $Lt(M)$ depends on $M$. In the talk, I will describe the architecture of $Lt(M)$, and I will survey what is known and what is still open about Kotlarski's question.
December 10:
MOPA
1:00pm NY time
Virtual (email Victoria Gitman for meeting id)
Models of fragments of PA with low Scott rank
Leszek Kołodziejczyk
University of Warsaw
Abstract
The infinitary logic $L_{\omega_1, \omega}$ extends first-order logic by allowing countable disjunctions and conjunctions of formulas. Every countable structure can be described up to isomorphism (within the class of countable structures) by an $L_{\omega_1, \omega}$ sentence. This gives rise to a particular way of measuring the complexity of countable structures: there is a natural alternation hierarchy $(\Pi^{\text{in}}_\alpha: \alpha \lt \omega_1)$ of $L_{\omega_1, \omega}$ formulas, and the Scott rank of a structure $A$ is the smallest ordinal $\alpha$ such that $A$ can be described up to isomorphism by a $\Pi^{\text{in}}_{\alpha+1}$ sentence.
In recent years, beginning with a paper by Montalban and Rossegger, the Scott rank of models of arithmetic has attracted some attention. We now know, for instance, that every nonstandard pointwise definable model of ${\rm PA}$ has Scott rank at least omega, that all other nonstandard models of ${\rm PA}$ must have rank at least $\omega+1$, and that recursively saturated models of ${\rm PA}$ have rank exactly $\omega+1$. This naturally leads one to ask about possible Scott ranks of models of subtheories of ${\rm PA}$. In particular: what is the lowest possible Scott rank of a structure satisfying $I\Sigma_n + \lnot B\Sigma_{n+1}$? What about $B\Sigma_n + \lnot I\Sigma_n$?
We prove that every nonstandard model of $B\Sigma_n$ must have Scott rank at least $n+1$. Moreover, this lower bound is tight: it is realized both by the most familiar models of $I\Sigma_n + \lnot B\Sigma_{n+1}$, namely pointwise $\Sigma_{n+1}$-definable substructures of models of $I\Sigma_{n+1}$, and by the most familiar models of $B\Sigma_n + \lnot I\Sigma_n$, namely initial segments generated by the $\Sigma_n$-definables of models of $I\Sigma_n$. Time permitting, we also hope to mention a few other facts about Scott ranks of models of fragments of ${\rm PA}$.
This is joint work in progress with Mateusz Łełyk and Patryk Szlufik.
Video