Logic Workshop

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.

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.

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.

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.

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

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.

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.

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.

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.

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.