NYLogic

I will talk about connections between three properties of a forcing class $\Gamma$: the most well-known one is the bounded forcing axiom at $(\omega_1,\lambda)$ for this class, introduced by Goldstern and Shelah for proper forcing. The second property is a two cardinal version of $\Sigma^1_1$ absoluteness, at $(\omega_1,\lambda)$, and the third is the preservation of Aronszajn trees of height $\omega_1$ and width $\lambda$. Under the assumption that $\lambda=\lambda^\omega$ and forcings in $\Gamma$ don't add countable subsets of $\lambda$, I will show that these properties are equivalent. The class of forcing notions satisfying Jensen's property of subcompleteness is a canonical class that does not add reals and it is a corollary of the above result that the bounded forcing axiom for subcomplete forcing at $(\omega_1,2^\omega)$ is equivalent to the preservation of Aronszajn trees of height $\omega_1$ and width $2^\omega$. This generalizes a prior result, obtained jointly with Kaethe Minden. I will discuss some further results, as well as some open questions, on the preservation of Aronszajn trees of height $\omega_1$ and other widths.

This is a continuation of a talk from last semester.

A model $(M, < ,\ldots)$ is said to be $\kappa$-like if $|M| = \kappa$ but for all $a \in M$, $|\{x \in M \mid x < a\}| < \kappa$. Based on the paper, the theory of $\kappa$-like models of arithmetic by R. Kaye, we will identify some axiom schemes true in such models of $I\Delta_0$ and investigate their interesting properties. ​

Several years ago I introduced the Diagonal Reflection Principle (DRP), a maximal form of simultaneous stationary reflection. Roughly, DRP asserts that for all regular $\theta \ge \omega_2$, there are stationarily many sets $W$ of size $\omega_1$ such that every stationary element of $W$ reflects to $W$ (i.e. if $S \subset [\theta]^\omega$ is stationary and $S \in W$, then $S \cap [W \cap \theta]^\omega$ is stationary). In that paper I showed that that $\text{MM}^{+\omega_1}$--even just the '$+\omega_1$' version of the forcing axiom for $\sigma$-closed forcings--implies DRP. In this talk I will prove that MM, even its technical strengthening $\text{MM}^{+\omega}$, does NOT imply DRP, contrary to my initial expectations. This is joint work with Hiroshi Sakai.

In this talk, I will discuss the relative complexity of the isomorphism and bi-embeddability relations for various classes of countable abelian groups from the point of view of descriptive set theory. This is joint work with Filippo Calderoni.

A virtual large cardinal is (usually) the critical point of a generic elementary embedding from a rank-initial segment of the universe into a transitive $M\subset V$, as introduced by Gitman and Schindler (2018). A notable feature is that all virtual large cardinals are consistent with $V=L$, and they've proven useful in characterising several properties in descriptive set theory. We'll work with the virtually $\theta$-measurable, $\theta$-strong and $\theta$-supercompact cardinals, where the $\theta$ in particular indicates that the generic embeddings have $H_\theta^V$ as domain, and investigate how these level-by-level virtual large cardinals relate both to each other and to the existence of winning strategies in certain games. This is work in progress and joint with Philipp Schlicht.

In 1959, MacDowell and Specker proved that every model of Peano Arithmetic has an elementary end extension. Since then, the theorem has been a constant source of new results, as well as a subject of extensions and generalizations. I will give a quick survey of those developments, including some very recent results.

A sequence of random variables is exchangeable when its distribution is invariant to reorderings of the sequence. This notion of symmetry and its generalizations to arrays, graphs, and other structures, arise in many statistical contexts. Representation theorems due to de Finetti, Aldous-Hoover, and others, describe how exchangeable structures can be written in a way that exposes conditional independence, which is often important for computational purposes. However, these results are not obviously computable. We will present several positive and negative results examining the computable content of these theorems, and will also describe several implications for the design of probabilistic programming languages. Joint work with Nathanael Ackerman, Jeremy Avigad, Daniel Roy, and Jason Rute.​

In their 2004 seminal paper, 'Fraisse Limits, Ramsey Theory, and Topological Dynamics of Automorphism Groups,' Kechris, Pestov, and Todorcevic, tied together the fields of model theory, Ramsey theory, descriptive set theory, and topological dynamics, via the concept of homogeneity. A key tool used is a combinatorial concept called finite constraint. We will show that a class of graphs called metrically homogeneous graphs, of interest to model theorists and combinatorialists, is finitely constrained, and we show how this is used to derive a whole host of topological and topological dynamical consequences.

We will present the following striking theorem, due to Towsner: If $(M, \mathcal X) \models \mathsf{RCA}_0 + I\Sigma_n$ is countable, then for any (!!!) $W \subseteq M$ there is a countable expansion with the same first order part, $(M, \mathcal Y)$, where $\mathcal X \subseteq \mathcal Y$ so that $(M, \mathcal Y) \models \mathsf{RCA}_0 + I\Sigma_n$ and the set $W$ is $\Delta_{n+1}$ definable. Time permitting, we will then sketch some nice applications of this theorem to the study of conservative extensions of fragments of arithmetic.

Given a countable transitive model of set theory and a notion of forcing in it, there is a natural countable Borel equivalence relation on generic objects over the model; two generics are equivalent if they yield the same generic extension. We study generic reals arising from familiar notions of forcing, e.g., Cohen and random forcing, under this equivalence relation and describe their relative complexity using the techniques of invariant descriptive set theory.

In this talk, I will discuss fields with a strong form of model completeness (called almost quantifier elimination) and sketch a proof that PAC fields with almost QE are simple. Time permitting, I will discuss a version of the theorem for differential fields.

The C-sequence number of an uncountable regular cardinal $\kappa$ is a cardinal invariant that provides a measure of the amount of compactness that holds at $\kappa$. We will begin this talk by introducing the C-sequence number and proving some of its basic properties, linking it to familiar notions including large cardinals and square principles. We will then outline a number of consistency results regarding the C-sequence number at inaccessible cardinals and successors of singular cardinals. We will end by exploring how the C-sequence number interacts with the existence of complicated colorings and the infinite productivity of the $\kappa$-Knaster condition. This is joint work with Assaf Rinot.

I will review some results about Mathias forcing over models of RCA0. This method has recently been used by Slaman and Yokoyama to prove conservativity results for Ramsey's Theorem for pairs. I will mostly discuss just the method, rather than this new result in particular.

Sun proved that, assuming $\kappa$ is a weakly compact cardinal, a subset $W\subseteq\kappa$ is $\Pi^1_1$-indescribable (or equivalently weakly compact) if and only if $W\cap C\neq\emptyset$ for every $1$-club $C\subseteq \kappa$; here, a set $C\subseteq\kappa$ is $1$-club if and only if $C\in\textrm{NS}_\kappa^+$ and whenever $\alpha<\kappa$ is inaccessible and $C\cap \alpha\in\textrm{NS}_\alpha^+$ then $\alpha\in C$. We generalize Sun's characterization to $\Pi^1_1$-indescribable subsets of $P_\kappa\lambda$, which were first defined by Baumgartner by using a natural two-cardinal version of the cumulative hierarchy. Using the minimal strongly normal ideal of non-strongly stationary sets on $P_\kappa\lambda$, which is distinct from $\textrm{NS}_{\kappa,\lambda}$ when $\kappa$ is inaccessible, we formulate a notion of $1$-club subset of $P_\kappa\lambda$ and prove that a set $W\subseteq P_\kappa\lambda$ is $\Pi^1_1$-indescribable if and only if $W\cap C\neq\emptyset$ for every $1$-club $C\subseteq P_\kappa\lambda$. We also show that elementary embeddings considered by Schanker witnessing near supercompactness lead to the definition of a normal ideal on $P_\kappa\lambda$, and indeed, this ideal is equal to Baumgartner's ideal of non-$\Pi^1_1$-indescribable subsets of $P_\kappa\lambda$. Additionally, we will discuss an application which answers a question of Cox-Lücke.

Generic elementary embeddings have many applications throughout set theory. For example, Solovay's original proof that every stationary subset of a regular uncountable cardinal $\kappa$ can be partitioned into $\kappa$ disjoint stationary sets involves the use of a generic ultrapower embedding obtained by forcing with the nonstationary ideal. The generic ultrapower construction leads naturally to a characterization of the nonstationary ideal on a regular uncountable cardinal $\textrm{NS}_\kappa$ in terms of generic elementary embeddings. We will show that this characterization can be generalized to various ideals associated to large cardinals. Specifically, we will discuss characterizations of the $\Pi^m_n$-indescribability ideals, the subtle ideal and the ineffability ideal in terms of generic elementary embeddings as well as potential applications.

We consider effective Mathias forcing over a countable Turing ideal. In particular, we show that a Mathias generic constructed with conditions from a countable ideal $\mathcal{I}$ need not compute a Mathias generic over every smaller ideal $\mathcal{J} \subseteq \mathcal{I}$, answering a question of Cholak, Dzhafarov, and Soskova. This is joint work with Henry Towsner and Dan Turetsky.

I will continue speaking about some results in the reverse mathematics of combinatorial principles which utilize Mathias forcing.

Let $M$ be an inner model. $M$`s bedrock $B$, provided it exist, is the $\subseteq$-least inner model such that $M = B[g]$ for some set generic filter $g$.

We will discuss the interplay of (internal) iterability, strong cardinals and the existence of bedrocks in the case that $M$ is an extender model.

I will present results by Kaplan, Levi, and Simon (2017) showing that groups with two model-theoretic properties – omega-categorical and dp-minimal – are nilpotent-by-finite, i.e., they have normal nilpotent subgroups of finite index. Nilpotent-by-finite is a strong group-theoretic property, which can inform the use of groups in exploring various theories, including the theories of structures other than groups. This talk will define these properties (nilpotent-by-finite, omega-categorical, dp-minimal, as well as NIP), give examples of structures with and without these properties, and explain the group-theoretic consequences of the model-theoretic properties that are used in the paper.

I present a proof, from a joint paper with Sam Coskey, that the isomorphism relation for finitely generated models of PA is not smooth.

We consider three variations of the Löwenheim-Skolem Theorem type statements on stationary logics. These statements imply respectively that the size of the continuum is $\aleph_1$, $\aleph_2$ or very big (e.g. hyper, hyper, ... weakly Mahlo).

We also consider reflection principles in terms of games and strengthenings of generic supercompactness which are related to these three Löwenheim-Skolem Theorems for stationary logics.

I shall discuss recent joint work with Victoria Gitman and Asaf Karagila, in which we proved that Kelley-Morse set theory (which includes the global choice principle) does not prove the class Fodor principle, the assertion that every regressive class function $F:S\to {\rm Ord}$ defined on a stationary class $S$ is constant on a stationary subclass. Indeed, it is relatively consistent with KM for any infinite $\lambda$ with $\omega\leq\lambda\leq{\rm Ord}$ that there is a class function $F:{\rm Ord}\to\lambda$ that is not constant on any stationary class. Strikingly, it is consistent with KM that there is a sequence of classes $A_n$, each containing a class club, but the intersection of all $A_n$ is empty. Consequently, it is relatively consistent with KM that the class club filter is not $\sigma$-closed.

I will discuss realizing Easton functions in the presence of non-supercompact strongly compact cardinals and connections with indestructibility. This is joint work with Stamatis Dimopoulos and Toshimichi Usuba.

I will give a proof of the Ginsburg-Spanier theorem, as well as the nice corollary that multiplication is not definable in Presburger. ​

We will introduce the notions of virtual conditions and balanced conditions in definable partial orders, and apply these ideas to forcing extensions of the Solovay model. We will present a variety of independence results, and some ZF implications, for weak forms of the Axiom of Choice, and discuss related issues concerning the preservation of cardinals and chromatic numbers. Some of these results can be stated more generally using a natural classification of definable partial orders in terms of amalgamation properties.

This talk is a sequel to my talk in the Kolchin seminar. Let $p$ be a prime number and $e\geq 1$ a fixed natural number. We will consider the theory of separably closed non-trivially valued fields of characteristic $p$ and degree of imperfection $e$, either in a language where a $p$-basis is named or with $e$ commuting stacks of Hasse derivations. Denote the latter by $SCVH_{p,e}$.

We will first sketch a proof of the classification of imaginaries in $SCVH_{p,e}$ by the geometric sorts of Haskell-Hrushovski-Macpherson, using prolongations. We will then explain how these may be used to reduce more phenomena of geometric model theory in $SCVH_{p,e}$ to the algebraically closed case, e.g., a description of the stable part and the stably dominated types, yielding metastastability of $SCVH_{p,e}$. This is joint work with Moshe Kamensky and Silvain Rideau.

Can we define powerset(kappa) using the uB sets? Woodin showed that this cannot be done once there are supercompacts in the universe. Trang and the speaker recently showed that this cannot be done even much below than supercompacts, at the level of a Woodin cardinal that is a limit of Woodin cardinals. We will then discuss what powerset(kappa) could be.

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 in 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. During the talk I'll present ideas of the proof of the latter result, which is joint work with T. Slaman and L. Harington.

Ramsey's Theorem for pairs and 2 colors says that for every 2-coloring, $C$, of pairs of natural numbers, there is an infinite set $H$, such that all pairs from $H$ have the same constant color. $H$ is called a homogeneous set for $C$. We will also consider Ramsey's Theorem in other settings. For example, we can be given countably many $1$-colorings of natural numbers, $\{c_i\}$, and ask for a set $C$ such that, for each $i$, all but finitely many elements of $C$ have the same color with respect to $c_i$. Call $C$ a cohesive set for $\{c_i\}$. Among the questions we will explore here is what can be computed from homogeneous sets. For example, given countably many $1$-colorings $\{c_i\}$, is there a 2-coloring $C$, such that every homogeneous set for $C$ computes a cohesive set for $\{c_i\}$?

I will survey what is known about model companions of theories of (ordered) valued differential fields and discuss my ongoing work towards isolating a model companion for a certain theory of ordered valued differential fields, including positive results at the level of the value group.

In a recent exciting paper Learnability can be undecidable by S. Ben-David et. al. published in Nature Machine Intelligence the authors argue that certain abstract learnability questions are undecidable by ZFC axioms. The general learning problem considered there is to find a way of choosing a finite set that maximizes a particular expected value (within a certain range of error) with an obstacle that the probability distribution is unknown, or more formally:
given a family of functions $\mathcal{F}$ from some fixed domain $X$ to the real numbers and an unknown probability distribution $\mu$ over $X$, find, based on a finite sample generated by $\mu$, a function in $\mathcal{F}$ whose expectation with respect to $\mu$ is (close to) maximal.

The authors then provide a translation from this statistical framework to infinite comibnatorics: namely, they prove that existence of certain learning functions corresponding to the problem above (the so-called estimating the maximum learners, or EMX-learners) translates into the existence of the so-called monotone compression schemes, which in turn is equivalent to a statement in cardinal arithmetic that is indeed independent of ZFC. Specifically, let $X$ be an infinite set, $Fin(X)$ be the family of its finite subsets, and let $m > k$ be natural nubers. A monotone compressions scheme for $(X, m, k)$ is a function $f: [X]^k \rightarrow Fin(X)$ such that $$\forall A \in [X]^m \exists B \in [X]^k \: (B \subseteq A \subseteq f(B)).$$

The main result of the paper then is that there exists a monotone compressions scheme for $([0,1], m+1, m)$ for some $m$ if and only if $2^{\aleph_0} < \aleph_\omega$.

K.P. Hart immediately observed that the main combinatorial content of the results in the paper is related to Kuratowski's theorem on decompositions of finite powers of sets and that the monotone compression functions on the unit interval cannot, in a certain sense, be constructive or descriptively nice - namely, they cannot be Borel measurable. During the talk I will introduce the subject of the paper in question, and present the set-theoretic aspects of the main results.

In this talk we will outline results and facts from nonstandard analysis and introduce the concept of Loeb Measure.​

Adding Cohen subsets to each of a class of cardinals in turn is a common construction in set theory, and underlies many fundamental results. The construction comes in two basic flavors, products (as in Easton’s Theorem on the powers of regular cardinals) and iterations (forcing the GCH). These flavors are apparently quite similar, forcing at stage kappa to add subsets via the Cohen partial order Add(kappa,lambda). They differ only in the universe over which Add(kappa,lambda) is defined - in the case of products the ground model poset is used at each stage, whereas in typical iterations the poset is taken from the partial extension up to kappa. In this talk I will consider an alternative, in which we allow Add(kappa,lambda) to be defined over an arbitrary inner model (lying between the ground model and the extension up to kappa) at each stage. These generalized Cohen iterations are ZFC-preserving, although neither the proof for products nor for traditional iterations transfers directly. They allow constructions such as class iterations of class products of Cohen forcing, with applications including new work with Kameryn Williams on iterating the Mantle.

A Turing computable embedding is a Turing operator that maps one class of structures to another so as to preserve isomorphism. The embedding codes the input structure in the output structure. It is interesting when there is an effective decoding. It is also interesting when the decoding is very difficult. Recently, Harrison-Trainor, Melnikov, R. Miller, and Montalbán have defined very general notions of interpretation, in which the interpreting formulas have no fixed arity. Uniformly defined interpretations give us decoding. I will discuss some known Turing computable embeddings, looking for uniform interpretations that yield effective, or Borel, decoding.

1. Marker's embedding of directed graphs in undirected graphs,
2. Mal'tsev's embedding of fields in groups,
3. Friedman and Stanley's embedding of graphs in linear orderings.

The first two embeddings come with uniform 'effective' interpretations, which give uniform effective decoding. For the third, we do not even have uniform interpretation via $L_{\omega_1\omega}$ formulas.

The logic $L_{\omega_1 \omega}$ is obtained by closing finitary first-order logic under countable disjunction and conjunction. There is a kind of normal form for such sentences. For any structure $\mathcal{A}$ there is a sentence of $L_{\omega_1 \omega}$, known as its Scott sentence, which describes $\mathcal{A}$ up to isomorphism among countable structures. Given a countable scattered linear order $L$ of Hausdorff rank $\alpha < \omega_1$, we show that it has a $d$-$\Sigma_{2 \alpha+1}$ Scott sentence. From Ash's calculation of the back and forth relations for all countable well-orders, we obtain that this upper bound is tight, i.e., for every $\alpha < \omega_1$ there is a linear order whose optimal Scott sentence has this complexity.

Abstract

Definition: A collection $\mathcal F$ of forbidden subgraphs is a Rado family if the class of countable $\mathcal F$-free graphs contains a universal structure with respect to embeddings as induced subgraphs. (By 'forbidden' I mean forbidden as subgraphs; usage varies in the literature.)

We consider the following decision problem for Rado families.

Problem: Given a finite set $\mathcal F$ of finite, connected graphs, determine whether or not it is a Rado family.

Question: Is this a decidable problem?

If we specialize to the sake of a single constraint then we speak instead of a Rado constraint. Much is known, and much more conjectured, about the case of a single constraint.

Conjecture: The decision problem for the case of a single constraint is decidable.

Discussion

From the model theoretic side, a finite collection of forbidden subgraphs specifies a universal theory with some special properties: notably, there is a model companion. When we restrict to families of connected constraints, the theory has joint embedding and the model companion is complete. In model theoretic terms the question becomes whether the model companion has a countable universal model with respect to elementary embedding, for which a purely type theoretic criterion is known.

Decision problems for other model theoretic properties of the model companion are natural. We have focused on this one because the question came to us from graph theory. However, even in that form, two variants are relevant.

• Can we decide whether the model companion is $\aleph_0$-categorical?
• Dropping the connectedness hypothesis on the constraints, can we decide whether the model companion is complete?

The main source of positive answers to the universality problem appears to be the $\aleph_0$-categorical case, and this has some theoretical justification. The most direct route to understanding the original graph theoretical problem appears to take the detour through $\aleph_0$-categoricity.

As time allows, I would like to discuss the following three points.

• What we know, and what we expect, in the case of a single constraint;
• Methods of proof (algebraic closure; induction by pruning);
• The status of the decision problem for j.e.p. and its analog in the theory of permutation pattern classes (work of Braunfeld).

This is joint work with Shelah, e.g. [Sh689].

From non-trivial elementary embeddings $j_{1}\dots j_{r}:V_{\lambda}\rightarrow V_{\lambda}$, we obtain a sequence of polynomials $(p_{n}(x_{1},\dots,x_{r}))_{n\in\omega}$ that satisfies the infinite product $$\prod_{k=0}^{\infty}p_{k}(x_{1},\dots,x_{r})=\frac{1}{1-(x_{1}+\dots+x_{r})}.$$ From this infinite product, we deduce lower bounds of the cardinality of $|\langle j_{1},...,j_{r}\rangle/\equiv^{\alpha}|$ using analysis and analytic number theoretic techniques. Computer calculations that search for Laver-like algebras give some empirical evidence that these lower bounds cannot be greatly improved.

Gödel–Bernays set theory GB and Kelley–Morse set theory KM are two formal theories for second-order set theory, allowing both sets and proper classes as objects. GB is the weaker of the two theories, being conservative over ZF, while KM is the stronger. Set theorists have used KM in applications where GB is not strong enough; for instance, Kunen formulated his celebrated inconsistency result in the context of KM, as KM has the resources to directly allow talk of elementary embeddings of the universe of sets. But weaker theories than KM suffice for many of these applications. Between GB and KM there is a hierarchy of intermediate theories based upon restricting the logical complexity allowed in the comprehension axiom.

In this talk I will present a hierarchy of second-order set theories which refines the comprehension-based hierarchy. This hierarchy is based upon transfinite recursion principles, ordered first by the logical complexity of the properties allowed and second by the lengths of well-orders on which we may carry out the recursions. Theories in this hierarchy are separated in terms of consistency strength. The substantive new result to establish this hierarchy is the following: Let $k$ be a natural number. Suppose $(M,\mathcal{X})$ satisfies GB and that $\Gamma \in \mathcal{X}$ is a class well-order which is closed under addition. In case $k = 0$ further assume $\Gamma \ge \omega^\omega$. Then, if $(M,\mathcal{X})$ satisfies $\Pi^1_k$-Transfinite Recursion for recursions along $\Gamma$, there is $\mathcal{Y} \subseteq \mathcal{X}$ coded in $\mathcal{X}$ so that $(M,\mathcal{Y})$ satisfies GB plus the principle of $\Pi^1_k$-Transfinite Recursion for recursions along well-orders of length $< \Gamma$.