Calendar
January 26:
Memorial lectures for Martin Davis at the Courant Institute (New York University)
All are welcome to attend this special event in memory of Professor Martin Davis. There will be three lectures on his work from 1:00 - 2:30 pm, a memorial for Martin and Virginia Davis from 2:45 - 3:45 pm, and a reception afterwards from 4-6 pm. Preregistration is requested, ideally by January 15, using the website.
February 2:
Logic Workshop
2:00pm NY time
Room: 5417
Blurry HOD and the structure of leaps
Gunter Fuchs
CUNY
Abstract
For a cardinal $\kappa\ge 2$, one can weaken the concept 'x is ordinal definable' (i.e., x is the unique object satisfying some condition involving ordinal parameters) to 'x is $\lt\kappa$-blurrily ordinal definable,' meaning that x is one of fewer than $\kappa$ many objects satisfying some condition involving ordinal parameters. By considering the hereditary version of this, one naturally arrives at the inner model $\lt\kappa$-HOD, the class of all hereditarily $\lt\kappa$-blurrily ordinal definable sets. In ZFC, by varying $\kappa$, one obtains a hierarchy of inner models spanning all the way from HOD to V. The leaps are those stages in the hierarchy where something new is added. I have previously given a logic workshop talk about the basic theory of the blurry HOD hierarchy, and in this talk, after reviewing the basics, I want to focus on the consistency strengths of certain leap constellations, ranging from outright consistent, to equiconsistent with a measurable cardinal, to inconsistent.
February 2:
Set Theory Seminar
12:30pm NY time
Room: 6494
Hybrid (email Victoria Gitman for meeting id)
Mutual stationarity and the failure of SCH
Dima Sinapova
Rutgers University
Abstract
Mutual stationarity is a compactness type property for singular cardinals. Roughly, it asserts that given a singular cardinal $\kappa$, stationary subsets of regular cardinals with limit $\kappa$ have a 'simultaneous witness' for their stationarity. This principle was first defined by Foreman and Magidor in 2001, who showed that it holds when the stationary sets are of points of countable cofinality. They also showed that in general this does not generalize to higher cofinality. Whether the principle can consistently hold for higher cofinalities remained open, until a few years ago Ben Neria showed that from large cardinals mutual stationarity at $\langle\aleph_n\mid n\lt\omega\rangle$ can be forced for any fixed cofinality.
We show that we can obtain mutual stationarity at $\langle\aleph_n\mid n\lt\omega\rangle$ for any fixed cofinality together with the failure of SCH at $\aleph_\omega$. Along the way we reduce the Ben Neria's large cardinal hypothesis. This is joint work with Will Adkisson.
Video
February 9:
Logic Workshop
2:00pm NY time
Room: 5417
Properties of Generic Algebraic Fields
Russell Miller
CUNY
Abstract
The algebraic field extensions of the rational numbers $\mathbb{Q}$ – equivalently, the subfields of the algebraic closure $\overline{\mathbb{Q}}$ – naturally form a topological space homeomorphic to Cantor space. Consequently, one can speak of 'large' collections of such fields, in the sense of Baire category: collections that are comeager in the space. Under a standard definition, the 1-generic fields form a comeager set in this space. Therefore, one may think of a property common to all 1-generic fields as a property that one might reasonably expect to be true of an arbitrarily chosen algebraic field.
We will present joint work with Eisenträger, Springer, and Westrick that proves several intriguing properties to be true of all 1-generic fields $F$. First, in every such $F$, both the subring $\mathbb{Z}$ of the integers and the subring $\mathcal{O}_F$ of the algebraic integers of $F$ cannot be defined within $F$ by an existential formula, nor by a universal formula. (Subsequent work by Dittman and Fehm has shown that in fact these subrings are completely undefinable in these fields.) Next, for every presentation of every such $F$, the root set
$ R_F = \{ p\in \mathbb{Z}[X]:p(X)=0\text{ has a solution in }F\} $
is always of low Turing degree relative to that presentation, but is essentially always undecidable relative to the presentation. Moreover, the set known as Hilbert's Tenth Problem for $F$,
$ HTP(F) = \{ p\in \mathbb{Z}[X_1,X_2,\ldots]:p(X_1,\ldots,X_n)=0\text{ has a solution in }F^n\}, $
is exactly as difficult as $R_F$, which is its restriction to single-variable polynomials. Finally, even the question of having infinitely many solutions,
$\{ p\in \mathbb{Z}[X_1,X_2,\ldots]:p(\vec{X})=0\text{ has infinitely many solutions in }F^n\}, $
is only as difficult as $R_F$. These results are proven by using a forcing notion on the fields and showing that it is decidable whether or not a given condition forces a given polynomial to have a root, or to have infinitely many roots.
February 9:
Set Theory Seminar
12:30pm NY time
Virtual (email Victoria Gitman for meeting id)
Tukey-top ultrafilters under UA
Tom Benhamou
Rutgers University
Abstract
In the first part of the talk, we will provide some background and motivation to study the Glavin property. In particular, we will present a recently discovered connection between the Galvin property and the Tukey order on ultrafilters. This is a joint result with Natasha Dobrinen. In the second part, we will introduce several diamond-like principles for ultrafilters, and prove some relations with the Galvin property. Finally, we use the Ultrapower Axiom to characterize the Galvin property in the known canonical inner models. The second and third part is joint work with Gabriel Goldberg.
Video
Slides
February 13:
MOPA
1:00pm NY time
Virtual (email Victoria Gitman for meeting id)
The Borel complexity of first-order theories
Dino Rossegger
TU Wien
Abstract
The Borel hierarchy gives a robust way to stratify the complexity of sets of countable structures and is intimately tied with definability in infinitary logic via the Lopez-Escobar theorem. However, what happens with sets axiomatizable in finitary first-order logic, such as the set of structures satisfying a given finitary first-order theory T? Is the complexity of the set of T's models in any way related to the quantifier complexity of the sentences axiomatizing it? In particular, if a theory T is not axiomatizable by a set of sentences of bounded quantifier complexity, can the set of models of T still be at a finite level of the Borel hierarchy?
In this talk, we will present results concerning these questions:
In joint work with Andrews, Gonzalez, Lempp, and Zhu we show that the set of models of a theory T is $\Pi^0_\omega$-complete if and only if T does not have an axiomatization by sentences of bounded quantifier complexity, answering the last question in the negative. We also characterize the Borel complexity of the set of models of complete theories in terms of their finitary axiomatizations. Our results suggest that infinitary logic does not provide any efficacy when defining first-order properties, a phenomenon already observed by Wadge and Keisler and, recently, rediscovered by Harrison-Trainor and Kretschmer using different techniques.
Combining our results with recent results by Enayat and Visser, we obtain that a large class of theories studied in the foundations of mathematics, sequential theories, have a maximal complicated set of models.
Video
February 16:
Computability Seminar
10:30am NY time
Room: 3305
Largeness notions
Andrea Volpi
University of Udine
Abstract
Finite Ramsey Theorem states that fixed $n,m,k \in \mathbb N$, there exists $N \in \mathbb N$ such that for each coloring of $[N]^n$ with $k$ colors, there is a homogeneous subset $H$ of $N$ of cardinality at least $m$. Starting with the celebrated Paris-Harrington theorem, many Ramsey-like results have been studied using different largeness notions rather than the cardinality. I will introduce the largeness notion defined by Ketonen and Solovay based on fundamental sequences of ordinals. Then I will describe an alternative and more flexible largeness notion using blocks and barriers. If time allows, I will talk about how the latter can be used to study a more general Ramsey-like result.
February 16:
Logic Workshop
2:00pm NY time
Room: 5417
The Ginsburg-Sands theorem and computability
Damir Dzhafarov
University of Connecticut
Abstract
In their 1979 paper `Minimal Infinite Topological Spaces,’ Ginsburg and Sands proved that every infinite topological space has an infinite subspace homeomorphic to exactly one of the following five topologies on $\omega$: indiscrete, discrete, initial segment, final segment, and cofinite. The proof, while nonconstructive, features an interesting application of Ramsey's theorem for pairs ($\mathsf{RT}^2_2$). We analyze this principle in computability theory and reverse mathematics, using Dorais's formalization of CSC spaces. Among our results are that the Ginsburg-Sands theorem for CSC spaces is equivalent to $\mathsf{ACA}_0,$ while for Hausdorff spaces it is provable in $\mathsf{RCA}_0$. Furthermore, if we enrich a CSC space by adding the closure operator on points, then the Ginsburg-Sands theorem turns out to be equivalent to the Chain-Antichain Principle ($\mathsf{CAC}$). The most surprising case is that of the Ginsburg-Sands theorem restricted to $T_1$ spaces. Here, we show that the principle lies strictly between $\mathsf{ACA}_0$ and $\mathsf{RT}^2_2$, yielding perhaps the first natural theorem of ordinary mathematics (i.e., conceived outside of logic) to occupy this interval. I will discuss the proofs of both the implications and separations, which feature several novel combinatorial elements, and survey a new class of purely combinatorial principles below $\mathsf{ACA}_0$ and not implied by $\mathsf{RT}^2_2$ revealed by our investigation. This is joint work with Heidi Benham, Andrew DeLapo, Reed Solomon, and Java Darleen Villano.
February 23:
Logic Workshop
2:00pm NY time
Room: 5417
Commutativity of cofinal types of ultrafilters
Tom Benhamou
Rutgers University
Abstract
The Tukey order finds its origins in the concept of Moore-Smith convergence in topology, and is especially important when restricted to ultrafilters with reverse inclusion. The Tukey order of ultrafilters over $\omega$ was studied intensively by Blass, Dobrinen, Isbell, Raghavan, Shelah, Todorcevic and many others, but still contains many fundamental unresolved problems. After reviewing the topological background for the Tukey order, I will present a recent development in the theory of the Tukey order restricted to ultrafilters on measurable cardinals, and explain how different the situation is when compared to ultrafilters on $\omega$. Moreover, we will see an important application to the Galvin property of ultrafilters. In the second part of the talk, we will demonstrate how ideas and intuition from ultrafilters over measurable cardinals lead to new results on the Tukey order restricted to ultrafilters over $\omega$. This is joint with Natasha Dobrinen.
February 27:
MOPA
1:00pm NY time
Virtual (email Victoria Gitman for meeting id)
Explicit models of arithmetic do not have full standard system
Elliot Glazer
Harvard University
Abstract
It is well-known under ZFC that there is a nonstandard model of PA which has a full standard system, i.e. every subset of this model's standard cut is the intersection of the standard cut with some subset of the model which is definable from parameters. We show that the use of Choice here cannot be avoided. More precisely, we prove that it is consistent relative to ZF that no model of PA has full standard system, and it is provable in ZF (or just a fragment of second-order arithmetic) that no Borel model has full standard system. The proof is measure-theoretic in nature, and as a simpler first argument, we will prove from Projective Determinacy the stronger claim that no projective model has full standard system.
Since the power set of the naturals is trivially a Scott set, an immediate corollary of this result is that Scott's problem is independent of ZF.
Slides
Video
March 1:
Model Theory Seminar
12:30pm NY time
Room: 6495
Big Ramsey degrees in ultraproducts of finite structures
Rehana Patel
Wesleyan University
Abstract
I will present a transfer principle in structural Ramsey theory from finite structures to ultraproducts. In joint work with Bartosova, Dzamonja and Scow, we show that under certain mild conditions and assuming CH, when a class of finite structures has finite small Ramsey degrees, the ultraproduct has finite big Ramsey degrees for internal colorings. All Ramsey-theoretic definitions will be provided, and if time permits, I will give a sketch of the proof.
March 1:
Logic Workshop
2:00pm NY time
Room: 5417
Component Closed Structures on the Reals
Alf Dolich
CUNY
Abstract
A structure, R, expanding $(\mathbb{R}, \lt)$ is called component closed if whenever $X \subseteq R^n$ is definable so are all of $X$'s connected components. Two basic examples of component closed structures are $(\mathbb{R}, \lt, +, \cdot)$ and $(\mathbb{R}, \lt, \cdot, \mathbb{Z})$. It turns out that these two structures are exemplary of a general phenomenon for component closed structures from a broad class of expansions of $(\mathbb{R}, \lt)$: either their definable sets are very 'tame' (as in the case of the real closed field) or they are quite 'wild' (as in the case of the real field expanded by the integers).
March 5:
MOPA
1:00pm NY time
Virtual (email Victoria Gitman for meeting id)
Tightness and solidity in fragments of Peano Arithmetic
Piotr Gruza
University of Warsaw
Abstract
It was shown by Visser that Peano Arithmetic has the property that no two distinct extensions of it (in its language) are bi-interpretable. Enayat proposed to refer to this property of a theory as tightness and to carry out a more systematic study of tightness and its stronger variants, which he called neatness and solidity.
Enayat proved that not only $\text{PA}$, but also $\text{ZF}$, $\text{Z}_{2}$, and $\text{KM}$ are solid; and on the other hand, that finitely axiomatisable fragments of them are not even tight. Later work by a number of authors showed that many natural proper fragments of these theories are also not tight.
Enayat asked whether there are proper solid subtheories (containing some basic axioms that depend on the theory) of the theories listed above. We answer this question in the case of $\text{PA}$ by proving that for every $n$ there exists a solid theory strictly between $\text{I}\Sigma_{n}$ and $\text{PA}$. Furthermore, we can require that the theory does not interpret $\text{PA}$, and that if any true arithmetic sentence is added to it, the theory still does not prove $\text{PA}$.
Joint work with Leszek Kołodziejczyk and Mateusz Łełyk.
Video
March 8:
Logic Workshop
No seminar
March 8:
Set Theory Seminar
12:30pm NY time
Virtual (email Victoria Gitman for meeting id)
Model Theory of class-sized logics
Jonathan Osinski
Univeristy of Hamburg
Abstract
We consider logics in which the collection of sentences over a set-sized vocabulary can form a proper class. The easiest example of such a logic is $\mathcal L_{\infty \infty}$, which allows for disjunctions and conjunctions over arbitrarily sized sets of formulas and quantification over strings of variables of any infinite length. Model theory of $\mathcal L_{\infty \infty}$ is very restricted. For instance, it is inconsistent for it to have nice compactness or Löwenheim-Skolem properties. However, Trevor Wilson recently showed that the existence of a Löwenheim-Skolem-Tarski number of a certain class-sized fragment of $\mathcal L_{\infty \infty}$ is equivalent to the existence of a supercompact cardinal, and various other related results. We continue this work by considering several appropriate class-sized logics and their relations to large cardinals. This is joint work with Trevor Wilson.
Video
March 12:
MOPA
1:00pm NY time
Virtual (email Victoria Gitman for meeting id)
Restricted completions
Albert Visser
Utrecht University
Abstract
This talk reports on research in collaboration with Ali Enayat and Mateusz Łełyk.
Steffen Lempp and Dino Rossegger asked: is there a consistent completion of ${\sf PA}^-$ that is axiomatised by sentences of bounded quantifier-alternation complexity? We show that there is no such restricted completion. We also show that, if one changes the measure of complexity to being $\Sigma_n$, there is a restricted completion. Specifically, we show that the true theory of the non-negative part of $\mathbb Z[X]$ can be axiomatised by a single sentence plus a set of $\Sigma^0_1$-sentences.
In our talk we will sketch these two answers. One of our aims is to make clear is that the negative answer for the case of quantifier-alternation complexity simply follows from Rosser's Theorem viewed from a sufficiently abstract standpoint.
Video
March 15:
Set Theory Seminar
12:30pm NY time
Virtual (email Victoria Gitman for meeting id)
Squares, ultrafilters and forcing axioms
Chris Lambie-Hanson
Czech Academy of Sciences
Abstract
A uniform ultrafilter $U$ over a cardinal $\kappa > \omega_1$ is called indecomposable if, whenever $\lambda \lt\kappa$ and $f:\kappa \rightarrow \lambda$, there is a set $X \in U$ such that $f[X]$ is countable. Indecomposability is a natural weakening of $\kappa$-completeness and has a number of implications for, e.g., the structure of ultraproducts. In the 1980s, Sheard answered a question of Silver by proving the consistency of the existence of an inaccessible but not weakly compact cardinal carrying an indecomposable ultrafilter. Recently, however, Goldberg proved that this situation cannot hold above a strongly compact cardinal: If $\lambda$ is strongly compact and $\kappa \geq \lambda$ carries an indecomposable ultrafilter, then $\kappa$ is either measurable or a singular limit of countably many measurable cardinals. We prove that the same conclusion follows from the Proper Forcing Axiom, thus adding to the long list of statements first shown to hold above a strongly compact or supercompact cardinal and later shown also to follow from PFA. Time permitting, we will employ certain indexed square principles to prove that our results are sharp. This is joint work with Assaf Rinot and Jing Zhang.
Video
March 15:
Logic Workshop
2:00pm NY time
Room: 5417
Tennebaum's Theorem for quotient presentations and model-theoretic skepticism
Michał Godziszewski
University of Warsaw
Abstract
A computable quotient presentation of a mathematical structure $\mathcal A$ consists of a computable structure on the natural numbers $\langle \mathbb{N},\star,\ast,\dots \rangle$, meaning that the operations and relations of the structure are computable, and an equivalence relation $E$ on $\mathbb{N}$, not necessarily computable but which is a congruence with respect to this structure, such that the quotient $\langle \mathbb{N},\star,\ast,\dots \rangle$ is isomorphic to the given structure $\mathcal{A}$. Thus, one may consider computable quotient presentations of graphs, groups, orders, rings and so on. A natural question asked by B. Khoussainov in 2016, is if the Tennenbaum Thoerem extends to the context of computable presentations of nonstandard models of arithmetic. In a joint work with J.D. Hamkins we have proved that no nonstandard model of arithmetic admits a computable quotient presentation by a computably enumerable equivalence relation on the natural numbers. However, as it happens, there exists a nonstandard model of arithmetic admitting a computable quotient presentation by a co-c.e. equivalence relation. Actually, there are infinitely many of those. The idea of the proof consists is simulating the Henkin construction via finite injury priority argument. What is quite surprising, the construction works (i.e. injury lemma holds) by Hilbert's Basis Theorem. The latter argument is joint work with T. Slaman and L. Harrington.
March 19:
MOPA
1:00pm NY time
Virtual (email Victoria Gitman for meeting id)
The lattice problem for models of PA
Roman Kossak
CUNY
Abstract
The lattice problem for models of PA is to determine which lattices can be represented either as lattices of elementary substructures of a model of PA or, more generally, which can be represented as lattices of elementary substructures of a model N that contain a given elementary substructure M of N. I will talk about the history of the problem, from the seminal paper of Haim Gaifman from 1976 and other early results to some recent work of Jim Schmerl. There is much to talk about.
Video
March 22:
Set Theory Seminar
12:30pm NY time
Virtual (email Victoria Gitman for meeting id)
A choiceless answer to a question of Woodin
Arthur Apter
CUNY
Abstract
In a lecture presented in July 2023, Moti Gitik discussed the following question from the 1980s due to Woodin, as well as approaches to its solution and why it is so difficult to solve:
Question: Assuming there is no inner model of ZFC with a strong cardinal, is it possible to have a model $M$ of ZFC such that $M \vDash$'$2^{\aleph_\omega} > \aleph_{\omega + 2}$ and $2^{\aleph_n} = \aleph_{n + 1}$ for every $n \lt\omega$', together with the existence of an inner model $N^* \subseteq M$ of ZFC such that for the $\gamma, \delta$ so that $\gamma = (\aleph_\omega)^M$ and $\delta = (\aleph_{\omega + 3})^M,$ $N^* \vDash$'$\gamma$ is measurable and $2^\gamma \ge \delta$'?
I will discuss how to find answers to this question, if we drop the requirement that $M$ satisfies the Axiom of Choice. I will also briefly discuss the phenomenon that on occasion, when the Axiom of Choice is removed from consideration, a technically challenging question or problem becomes more tractable. One may, however, end up with models satisfying conclusions that are impossible in ZFC.
Reference: A. Apter, 'A Note on a Question of Woodin', Bulletin of the Polish Academy of Sciences (Mathematics), volume 71(2), 2023, 115--121.
Slides
Video
March 22:
Logic Workshop
2:00pm NY time
Room: 5417
Mediate cardinals
Kameryn Williams
Bard College at Simon's Rock
Abstract
In the late 1910s Bertrand Russell was occupied with two things: getting into political trouble for his pacifism and trying to understand the foundations of mathematics. His students were hard at work with him on this second occupation. One of those students was Dorothy Wrinch. In 1923 she gave a characterization of the axiom of choice in terms of a generalization of the notion of a Dedekind-finite infinite set. Unfortunately, her career turned toward mathematical biology and her logical work was forgotten by history.
This talk is part of a project of revisiting Wrinch's work from a modern perspective. I will present the main result of her 1923 paper, that AC is equivalent to the non-existence of what she termed mediate cardinals. I will also talk about some new independence results. The two main results are: (1) the smallest $\kappa$ for which a $\kappa$-mediate cardinal exists can consistently be any regular $\kappa$ and (2) the collection of regular $\kappa$ for which exact $\kappa$-mediate cardinals exist can consistently be any class.
March 26:
MOPA
1:00pm NY time
Virtual (email Victoria Gitman for meeting id)
The lattice problem for models of PA: part II
Roman Kossak
CUNY
Abstract
The lattice problem for models of PA is to determine which lattices can be represented either as lattices of elementary substructures of a model of PA or, more generally, which can be represented as lattices of elementary substructures of a model N that contain a given elementary substructure M of N. I will talk about the history of the problem, from the seminal paper of Haim Gaifman from 1976 and other early results to some recent work of Jim Schmerl. There is much to talk about.
Video
March 29:
Logic Workshop
No seminar
CUNY holiday.
April 2:
MOPA
1:00pm NY time
Virtual (email Victoria Gitman for meeting id)
Representations of lattices
Athar Abdul-Quader
Purchase College
Abstract
Following up on the series of talks on the history of the problem, in this talk we will discuss the main technique for realizing finite lattices as interstructure lattices, due to Schmerl in 1986. We will motivate this technique by studying an example: the Boolean algebra $\mathsf{B}_2$. We will see how we can modify the technique to produce elementary extensions realizing specific ranked lattices to ensure that such extensions are end, cofinal, or mixed extensions.
Video
April 5:
Logic Workshop
2:00pm NY time
Room: 5417
Decision problem for groups as equivalence relations
Meng-Che 'Turbo' Ho
California State University at Northridge
Abstract
In 1911, Dehn proposed three decision problems for finitely presented groups: the word problem, the conjugacy problem, and the isomorphism problem. These problems have been central to both group theory and logic, and were each proven to be undecidable in the 50's. There is much current research studying the decidability of these problems in certain classes of groups.
Classically, when a decision problem is undecidable, its complexity is measured using Turing reducibility. However, Dehn's problems can also be naturally thought of as computably enumerable equivalence relations (ceers). We take this point of view and measure their complexity using computable reductions. This yields behaviors different from the classical context: for instance, every Turing degree contains a word problem, but not every ceer degree does. This leads us to study the structure of ceer degrees containing a word problem and other related questions.
April 5:
Set Theory Seminar
12:30pm NY time
Virtual (email Victoria Gitman for meeting id)
TBA
Kameryn Williams
Bard College at Simon's Rock
Abstract
April 12:
Logic Workshop
2:00pm NY time
Room: 5417
Geometric tools for the decidability of the existential theory of $F_p[[t]]$
Hans Schoutens
CUNY
Abstract
I will give a brief survey how tools from algebraic geometry can be used in finding solutions to Diophantine equations over $F_p[[t]]$ and similar rings. These tools include Artin approximation, arc spaces, motives and resolution of singularities. This approach yields the definability of the existential theory of $F_p[[t]]$ (in the ring language with a constant for $t$) contingent upon the validity of resolution of singularities (Denef-Schoutens). Anscombe-Fehm proved a weaker result using model-theoretic tools and together with Dittmann, they gave a proof assuming only the weaker 'local uniformization conjecture.'
April 12:
Set Theory Seminar
12:30pm NY time
Virtual (email Victoria Gitman for meeting id)
TBA
Boban Velickovic
University of Paris
Abstract
April 19:
Logic Workshop
2:00pm NY time
Room: 5417
Some applications of model theory to lattice-ordered groups
Philip Scowcroft
Wesleyan University
Abstract
When does a hyperarchimedean lattice-ordered group embed into a hyperarchimedean lattice-ordered group with strong unit? After explaining the meaning of this question, I will describe some partial answers obtained via model theory.