NYLogic

I will give an overview over the theory of bounded forcing axioms, and explore some that are compatible with the continuum hypothesis. One of these is an axiom I propose to call the bounded forcing axiom for countably closed forcing (which at first may sound like an absurd concept, since already $MA_{\omega_1}$ for countably closed forcing is a theorem of ZFC). I will then focus on the bounded forcing axiom for subcomplete forcing (BSCFA), and show a result that was obtained in joined work with Kaethe Minden, that in the presence of CH, this axiom is equivalent to the absoluteness of the set of branches of any tree of height and width $\omega_1$. Time permitting, I may also mention some 'predicative' strengthenings of bounded forcing axioms whose versions for subcomplete forcing allow us to conclude the existence of a definable well-order of the power set of $\omega_1$, assuming the mantle is a ground.

We will study infinite two player games and the large cardinal strength corresponding to their determinacy. For games of length $\omega$ this is well understood and there is a tight connection between the determinacy of projective games and the existence of canonical inner models with Woodin cardinals. For games of arbitrary countable length, Itay Neeman proved the determinacy of analytic games of length $\omega \cdot \theta$ for countable $\theta\> \omega$ from a sharp for $\theta$ Woodin cardinals. We aim for a converse at successor ordinals and sketch how to obtain $\omega+n$ Woodin cardinals from the determinacy of $\boldsymbol\Pi^1_{n+1}$ games of length $\omega^2$. Moreover, we outline how to generalize this to construct a model with $\omega+\omega$ Woodin cardinals from the determinacy games of length $\omega^2$ with $\Game^{\mathbb{R}}\boldsymbol\Pi^1_1$ payoff.
This is joint work with Juan P. Aguilera.

Around 25 years ago, Laskowski noticed that the same combinatorial condition, the non-independence property (NIP), provides an important dividing line in both probably approximately correct (PAC) learning and model theory. In recent work, Hunter Chase and I use stability theoretic dividing lines to characterize learnability in various other settings of learning. For instance, a class is online learnable if and only if it is stable. In this talk, we will focus on query learning, where model theoretic techniques allow for a characterization of learnability and new learning algorithms using input from stability theory. We will assume basic familiarity with first order logic, but will introduce all notions we use from machine learning.

We'll discuss Shelah's technology of $(\mathcal L, N)$ models and its applications to independence results in PA. This includes an alternative proof of the Paris-Harrington theorem and a sharpening to a $\Pi^0_1$ true but unprovable statement of some mathematical interest. Time permitting, we'll also connect these ideas to Kripke's notion of Fulfillment and Wilkie's theorem on Why PA.

When considering subrings of the field $\mathbb Q$ of rational numbers, one can view Hilbert's Tenth Problem as an operator, mapping each set $W$ of prime numbers to the set $HTP(R_W)$ of polynomials in $\mathbb Z[X_1,X_2,\ldots]$ with solutions in the ring $R_W=\mathbb Z[W^{-1}]$. The set $HTP(R_{\emptyset})$ is the original Hilbert’s Tenth Problem, known since 1970 to be undecidable. If $W$ contains all primes, then one gets $HTP(\mathbb Q)$, whose decidability status is open. In between lie continuum-many other subrings of $\mathbb Q$.

We will begin by discussing topological and measure-theoretic results on the space of all subrings of $\mathbb Q$, which is homeomorphic to Cantor space. Then we will present a recent result by Ken Kramer and the speaker, showing that the HTP operator does not preserve Turing reducibility. Indeed, in some cases it reverses it: one can have $V<_T W$, yet $HTP(R_W) <_T HTP(R_V)$. Related techniques reveal that every Turing degree contains a set $W$ which is HTP-complete, with $W'\leq_1 HTP(R_W)$. On the other hand, the earlier results imply that very few sets $W$ have this property: the collection of all HTP-complete sets is meager and has measure $0$ in Cantor space.

We will present our recent work on Jensen's class of subcomplete forcing notions and some of its variants. Of particular interest to us will be models of the Subcomplete Forcing Axiom, SCFA. This axiom implies many of the more striking consequences of MM such as SCH and the failure of $\square_\kappa$ for all uncountable $\kappa$ (both of which are due to Jensen). However, in stark contrast to MM (and its weaker variants like PFA and MA), the natural model of SCFA satisfies not only CH but in fact $\diamondsuit$. As a result SCFA is consistent with many of the consequences of $\diamondsuit$ often ruled out by forcing axioms such as the existence of Souslin trees. Indeed it seems that nearly all consequences of MM that are known not to follow from SCFA do not follow simply because of the consistency of SCFA with $\diamondsuit$ or CH. This leads to many questions of the form: given a statement that is consistent with SCFA, but inconsistent with MM, is it equivalent to CH or $\diamondsuit$ modulo ZFC $+$ SCFA? For example, does SCFA + $\neg$CH imply there are no Souslin trees?

In our talk we will show that the answer to this question and many related ones is 'no'. Our proof introduces two new classes of forcings notions, called $\infty$-subproper and $\infty$-subcomplete respectively, which generalize Jensen's original discoveries. Each class is iterable by nice iterations in the sense of Miyamoto. We'll discuss these results as well as show how to use the iteration theorems to construct several new models of SCFA $+$ $\neg$CH, many of which are as striking as the natural model of SCFA $+$ $\diamondsuit$. This includes models of SCFA $+$ $\neg$CH with Souslin trees and models of SCFA where $\mathfrak{d} = \aleph_1 < \mathfrak{c} = \aleph_2$. No previous knowledge of subversion forcing or nice iterations will be assumed. This is joint work with Gunter Fuchs.

In 1964, Ulam introduced his eponymous sequence, defined as starting with two integers a and b, and such that every subsequent term is the smallest integer that can be written as a sum of two distinct prior terms in exactly one way. This sequence has mystified number theorists ever since---there are many examples of conjectures about Ulam sequences that are very well supported numerically, but seem impossible to prove due to the chaotic nature of the sequence. In this talk, we'll show that in contrast families of Ulam sequences seem to be incredibly rigid, and that by appealing to a non-standard model of arithmetic, we can actually prove some interesting results in this direction.

It is known that every computable relational structure is isomorphic to a primitive recursive structure on a primitive recursive universe. This talk is devoted to the primitive recursive structures with the universe consisting of all natural numbers. This is a new notion which indeed is stronger than the standard notion. However, the new notion allows us to obtain non-trivial results on the complexity of isomorphisms between primitive recursive copies of structures. In this talk I will give a survey of the results obtained by myself, A. Melnikov, K.M. Ng and others.

Suppose every (definable) set of real numbers has the Ramsey property and (definable) relations on the real numbers can be uniformized by a function on a set which is comeager in the Ellentuck topology. Then there are no (definable) MAD families. As it turns out, there are also no (fin x fin)-MAD families, where fin x fin is the two-dimensional Fubini product of the ideal of finite sets. We also comment on work in progress regarding higher dimensional products. All results are joint work with Asger Törnquist.

We will continue discussing Shelah's technique of $(\mathcal L, n)$ models and their applications to independence results in PA. This includes a new proof of Paris-Harrington and an example of a concrete true but unprovable $\Pi^0_1$ sentence. Time permitting we'll also discuss the connection of these ideas to Wilkie's theorem on Why PA? and Kripke's notion of fulfillment.

A full satisfaction class for a model of Peano Arithmetic is an assignment of truth values to all sentences in the sense of the model that respects Tarski's inductive conditions for satisfaction relation. In 1976, Lachlan proved that every model of PA that has a full satisfaction class is recursively saturated. Lachlan's construction is intricate. Recently, Bartosz Wcisło developed a general method based on Lachlan's argument that allowed him to show that if a model has a full satisfaction class, then it also has a partial inductive satisfaction class, improving a previous result by Stuart Smith. I will outline Wcisło's method, and I'll survey some related results.

There has been some interest recently in nonamalgamability phenomena between countable models of set theory, and forcing extensions of a fixed model in particular. Nonamalgamability is typically achieved by coding some forbidden object between a collection of models in such a way that each model on its own remains oblivious, but some combination of them can recover the forbidden information.

In this talk we will examine the problem of coding arbitrary information into a generic filter, focusing on two particular examples. First, I will present some results of joint work with Jonathan Verner where we consider surgical modifications to Cohen reals and sets of indices where such modifications are always possible. Later, I will discuss a recent result of S. Friedman and Hathaway where they achieve, using different coding, nonamalgamability between arbitrary countable models of set theory of the same height.

I will talk about a recent paper by Jim Schmerl which provides an alternative proof that every resplendent model of PA has a full truth class. The proof, surprisingly, boils down to studying kernels of digraphs. A kernel of a digraph is a set K such that for any a, b in K, (a, b) is not an edge, and for any a not in K, there is some b in K such that (a, b) is an edge. Schmerl shows that one can view the result that resplendent models have full truth classes as a particular instance of the result that resplendent digraphs which have local finite height have kernels.

We study the logical and computational properties of basic theorems of uncountable mathematics, including the Cousin and Lindeloef lemmas, published in 1895 and 1903. Historically, these lemmas were among the first formulations of open-cover compactness and the Lindeloef property, respectively. These notions are of great conceptual importance: the former is commonly viewed as a way of treating uncountable sets like e.g. [0,1] as 'almost finite', while the latter allows one to treat uncountable sets like e.g. the real numbers R as 'almost countable'. This reduction of the uncountable to the finite/countable turns out to have a considerable logical and computational cost: we show that the aforementioned lemmas, and many related theorems, are extremely hard to prove, while the associated sub-covers are extremely hard to compute. Indeed, in terms of the standard scale (based on comprehension axioms), a proof of these lemmas requires at least the full extent of second-order arithmetic, a system originating from Hilbert-Bernays’ Grundlagen der Mathematik. This observation has far-reaching implications for the Grundlagen's spiritual successor, the program of Reverse Mathematics, and the associated Goedel hierachy. We discuss similar theorems relating to the gauge integral, a generalisation of the Lebesgue and improper Riemann integrals that also uniquely provides a direct formalisation of Feynman's path integral.

Tao’s metastability, going back to Kreisel and Goedel, is a notion of convergence with nice computational properties. The trade-off involved in metastability is that one obtains uniform and effective information, but only about a finite (but arbitrarily large) domain. We apply this metastability trade-off, i.e. introducing finite domains to yield uniform and effective results, to concepts other than convergence. This results in theorems requiring full second order arithmetic for a proof. We obtain similar results for another notion inspired by proof theory, namely uniform theorems, in which the objects claimed to exist depend on few of the parameters in the theorem.

In 1989, Stuart Smith proved that for every full truth predicate T on a nonstandard model M of PA, there is a nonstandard formula that, according to T, defines an undefinable class of M. Recently, Bartosz Wcisło improved this by showing that there is also a nonstandard formula that defines an inductive partial truth predicate. The proof uses the technique of disjunctions with stopping conditions. I will discuss the proof, and, if time permits, I will also talk about the end extension problem for full truth predicates.

An uncountable cardinal $\kappa$ is strongly tall if it can be mapped arbitrarily high by ultrapower embeddings with critical point $\kappa$. Hamkins asked whether all strongly tall cardinals are strongly compact. We give a positive answer assuming GCH and discuss recent work of Gitik that shows that this cardinal arithmetic assumption is necessary.

In the presence of large cardinals, the $L(\mathbb{R})$ of any proper forcing extension is elementarily equivalent to the ground-model $L(\mathbb{R})$ (Neeman-Zapletal). Schindler showed that this generic absoluteness assertion is equiconsistent with a remarkable cardinal and can therefore be forced over $L$. Recently, Itay Neeman & I improved 'proper' to 'sigma-closed $\ast$ ccc' in Schindler's theorem, giving a totally different lower-bound argument. The proof naturally suggests a compactness property of trees on $\omega_1$, which is the subject of this talk.

I will outline the proof of the generic-absoluteness theorem (joint with Neeman), explain how the Tree Reflection Principle offers an alternative to traditional coding by reshaping, and discuss some applications to forcing axioms. In particular, we will discuss an expansion of the Bagaria-Gitman-Schindler analysis of the Weak Proper Forcing Axiom.

Remarkable cardinals will be defined in the talk. No extensive knowledge of proper forcing will be assumed.

In this talk, I will give some key definitions related to automorphisms of countable models of Presburger arithmetic, and summarize some results (such as quantifier elimination and DP rank) for an expansion by a specific modest automorphism. At my second talk in two weeks, I will prove, or sketch proofs of, those results.

Complete theories are in the center of classical model theory, especially in Shelah's classification or stability theory. But there are other, incomplete, theories that rival the complete theories in importance.

For instance, there are the theories whose model classes are closed under direct product, direct limit and pure substructure (a generalization of direct summand). In modules, such model classes are exactly the definable subcategories that arise in representation theory, and they are in bijective correspondence with the closed subsets of the Ziegler spectrum (knowledge of which is not assumed in the talk). But even in a general context, these can be characterized as the classes that are axiomatized by implications of positive primitive formulas (= existentially quantified conjunctions of atomic formulas).

For another instance of implicational (and certainly incomplete) theories, consider the theories of the class of flat modules---or, to bring it down to earth, torsion-free abelian groups---which, over arbitrary rings, require infinitary implications.

Yet another example is that of the theory of all finite abelian groups, whose models are known as pseudofinite abelian groups.

I will discuss the role of such theories in the theory of modules. As an example, I will indicate why every abelian group is a direct summand of a pseudofinite abelian group.

In this talk, I will give some key definitions related to automorphisms of countable models of Presburger arithmetic, and summarize some results (such as quantifier elimination and DP rank) for an expansion by a specific modest automorphism. At my second talk, I will prove, or sketch proofs of, those results.

The hypergraph containers theorem, introduced by Balogh-Morris-Samotij and Saxton-Thomason, is a breakthrough in extremal combinatorics which gives a tool for controlling the number of independent sets in finite hypergraphs. (We do not assume any familiarity with the containers method!) The original proof depends on giving a program which constructs 'containers' for independent sets and analyzing its behavior to ensure the construction has the right properties. Inspired by the idea of pseudofinite dimension in ultraproducts, we give a new, elementary and nonalgorithmic, proof of the containers theorem which gives an direct characterization of the 'containers'. Joint work with Bernshteyn, Delcourt, and Tserunyan.

The axiom of disjunctive correctness (DC) asserts that the truth predicate commutes with disjunctions of arbitrary size in the sense of PA. In this talk we follow an unpublished paper of Enayat and Pakhomov discussing the strength of the theory CT^{-}(PA)+DC, and in particular showing that it implies Con(PA).

Peano’s original investigations into the foundations of arithmetic led to the observation that the axioms of PA are categorical for the Natural Numbers when treated in 2nd order logic. In this talk we will give a proof of Wilkie’s theorem which states that PA is in a sense the least such theory with this property. Arguably this justifies its significance in foundational studies. The proof uses the method of (L, n)-models, which I have previously talked about and I’ll discuss it’s use here as well.

Topoi are fundamental mathematical objects which lie at the crossroads between set theory, model theory, algebraic geometry and topology. One of the many ways of viewing a topos is as a mathematical universe with enough structure to contain models of first order theories. In this talk I will provide a gentle introduction to topoi. I will give several examples and walk through the basic properties that topoi possess which ensure they contain models of first order theories.

In this talk we will give background on $\mathcal{L}_{\infty, \omega}(L)$, categorical logic as well as Grothendieck topoi. We will then show how to make precise a version of Vaught's conjecture for a Grothendieck topos as well as discuss various analogs of Morley's theorem which hold in Grothendeick topoi. If we have time we will also briefly discuss analogs of other theorems of $\mathcal{L}_{\infty, \omega}$ for Grothendieck topoi.

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. ​

The Weyl algebra (in $n$ variables) is a well-studied object, playing a key role in non-commutative algebra, differential algebra, theory of $D$-modules, mathematical physics, etc. It reflects the 'canonical commutation relations' from quantum physics, also known as Heisenberg's uncertainty principle: $p_nq_n-q_np_n=1$ (where $q_n$ and $p_n$ are the respective position and moment operators on the $n$-th particle). I’ll give a brief introduction to this object, and tell a little about its 'pathologies' in positive characteristic. The main motivation for this project is a paper by Kontsevich and Belov-Kanel, where they prove the equivalence of the Jacobian Conjecture (about the surjectivity of endomorphisms of polynomial rings) with the Dixmier Conjecture (about the surjectivity of endomorphisms of the Weyl algebra) using reduction modulo positive characteristic. They remark that a proof using 'non-standard analysis'--by which they presumably mean via model-theory/ultraproducts--would perhaps be more natural.

In reply to this request, I will propose a first-order theory of Weyl algebras, based on my study of non-standard polynomial rings (which, therefore, I will review as well). The key tool is an embedded model of PA, which in case of ordinary polynomials/Weyl algebra is just the natural numbers (viewed as the set of exponents), together with a Darboux action (corresponding to the differential action on a polynomial ring). At the moment, however, I can only do this when the (internal) characteristic is zero; this, however, is not the case if one takes ultraproducts of Weyl algebras in positive characteristic, and so, at present, the right framework for doing the Konsevich/Belov-Kanel argument is still wanting.

I shall present a new proof, with new applications, of the amazing extension theorem of Barwise (1971), which shows that every countable model of ZF has an end-extension to a model of ZFC + V=L. This theorem is both (i) a technical culmination of Barwise's pioneering methods in admissible set theory and the admissible cover, but also (ii) one of those rare mathematical results saturated with significance for the philosophy of set theory. The new proof uses only classical methods of descriptive set theory, and makes no mention of infinitary logic. The results are directly connected with recent advances on the universal $\Sigma_1$-definable finite set, a set-theoretic version of Woodin's universal algorithm.

Sy Friedman introduced an inner model, which he called the stable core, in order to study under what circumstances the universe $V$ is a class forcing extension of ${\rm HOD}$. He showed there is a definable predicate $S$, amenable to ${\rm HOD}$, such that $V$ is a class forcing extension of the structure $\langle {\rm HOD},\in,S\rangle$. Namely, there is an ${\rm ORD}$-cc class partial order $\mathbb P$ definable in $\langle {\rm HOD},\in,S\rangle$ and a generic filter $G\subseteq \mathbb P$ such that ${\rm HOD}[G]=V$, however the filter $G$ itself is not definable over $V$. The predicate $S$, consisting of triples $(\alpha,\beta,n)$ for $\alpha$ and $\beta$ strong limit cardinals and $n\geq 1$ such that $H_\alpha\prec_{\Sigma_n}H_\beta$ and $\Sigma_n$-collection holds in $H_\beta$, codes elementarity relations between nice enough initial segments $H_\alpha$ of $V$. Friedman's argument showed that the information necessary to define $\mathbb P$ is already contained in $S$ so that $V$ is already a class forcing extension of the stable core $\langle L[S],\in,S\rangle$.

In a joint work with Friedman and Sandra Müller, we investigated the properties of the stable core. We were interested to see whether the stable core is in any sense a canonical inner model, whether it has regularity properties, whether it is consistent with large cardinals, and whether we can code information into it using forcing. We showed that the stable core of $L[\mu]$, the canonical model for a single measurable cardinal, is $L[\mu]$ and therefore measurable cardinals are consistent with the stable core. By coding generic sets into the stable core over $L$ or $L[\mu]$, we showed that there is a generic extension of $L$ in which the ${\rm GCH}$ fails at every regular cardinal in the stable core and there is a generic extension of $L[\mu]$ in which there is a measurable cardinal which is not even weakly compact in the stable core. Our work leaves numerous open questions about the structure of the stable core in the presence of large cardinals beyond a measurable cardinal.