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.