# MIT Logic Seminar

### Schedule

• September 3: Organizational Meeting

The First-Order Variable Hierarchy on Finite Ordered Graphs

The "k-variable fragment" FO^k consists of first-order formulas in which every subformula has at most k free variables. While the "variable hierarchy" FO^1, FO^2, ... is increasingly expressive in general, it had been open whether every first-order property of finite ordered graphs could be defined in FO^3 (i.e., using only 3 variables). We prove that the variable hierarchy is, in fact, strict in terms of expressive power on finite ordered graphs. In particular, we show that any first-order definition of k-CLIQUE requires k/4 variables. Our proof uses techniques from random graph theory, circuit complexity and Ehrenfeucht-Fraisse games.

The first-order theory of finitely generated fields

It has been conjectured that any reasonable property of finitely generated fields (e.g., "the absolute transcendence degree is odd") can be characterized by the truth of a single first-order sentence. This conjecture is still open. I will survey work towards it by F. Pop, myself, and T. Scanlon extending earlier work by J. Robinson, Yu. Ershov, and R. Rumely.

Jacques Herbrand and the early development of proof theory

In honor of the centenary of Jacques Herbrand (1908–1931), an examination of what led Herbrand to his "fundamental theorem", now known as Herbrand's Theorem, about the relation between full first-order logic and truth-functional logic. I discuss also the applications Herbrand made of his Theorem, and its significant effects in proof theory of that era, and beyond.

Degrees of Categoricity of Algebraic Fields

Let F be a computable field: a countable field in which the addition and multiplication are given by computable functions. We investigate the Turing degrees d such that F is d-computably categorical, meaning that d is able to compute isomorphisms between F and any other computable field isomorphic to F. We prove that algebraic fields can fail to be 0'-computably categorical, but that there is a degree d, low relative to 0', such that every algebraic field is d-computably categorical. We also prove analogous results, one jump lower, for computable fields with splitting algorithms.

• October 8: No Logic Seminar

• October 15: Joel David Hamkins (The College of Staten Island of CUNY and The CUNY Graduate Center)

Set-theoretic Geology

The technique of forcing in set theory is customarily thought of as a method for constructing outer as opposed to inner models of set theory. A set theorist typically has a model of set theory V and constructs a larger model V[G], the forcing extension, by adjoining a V-generic filter G over some partial order P in V. A switch in perspective, however, allows us to view forcing as a method of describing inner models as well. The idea is simply to search inwardly for how the model V itself might have arisen by forcing. Given a set theoretic universe V, we consider the classes W over which V can be realized as a forcing extension V = W[G] by some W-generic filter G. This change in viewpoint is the basis for a collection of questions constituting the topic we refer to as set-theoretic geology. In this talk, I will present some of the most interesting initial results in the topic, along with an abundance of open questions, many of which concern fundamental issues.

A ground model of the universe V is a class W such that V is obtained by set forcing over W, so that V = W[G] for some W-generic filter G over a poset P in W. The model V satisfies the Ground Axiom if there are no such W properly contained in V. The model W is a bedrock of V if W is a ground of V and satisfies the Ground Axiom. The mantle of V is the intersection of all grounds of V. The generic mantle of V is the intersection of all grounds of all set forcing extensions of V. Our main initial result is that every model of ZFC is the mantle and generic mantle of another model of ZFC. We prove this theorem while also controlling the HOD of the final model, as well as the generic HOD, the intersection of the HODs of all forcing extensions. Iteratively taking the mantle penetrates down through the inner mantles to what we call the outer core, what remains when all outer layers of forcing have been stripped away. Many fundamental questions remain open.

This is joint work with Gunter Fuchs (Muenster) and Jonas Reitz (New York City Tech).

New equivalences to being a subtle cardinal

Subtle cardinals are at the heart of a lot of combinatorial characterizations of large cardinals. We will explore the many guises of subtlety (including some new ones), and see how it combines with indescribability to lead to supercompactness.

• October 29: Asher Kach (University of Connecticut)

Embeddings of Computable Structures

A very nice result within linear orders is the existence of a computable presentation of $\omega + \omega^*$ having no computable infinite subset of order type $\omega$ or $\omega^*$. Of course, there are "nice" presentations of $\omega + \omega^*$ where this fails to happen. We explore whether this must always be the case for a myriad of classes of algebraic structures.

In particular we ask whether, given a class $C$ of algebraic structures, there are computable structures $S_1$ and $S_2$ in $C$ such that $S_1$ classically embeds into $S_2$ but for no computable presentations of $S_1$ and $S_2$ does $S_1$ computably embed into $S_2$. We answer this for a variety of classes: linear orders, graphs (directed and undirected), integral domains, commutative semigroups, ordered fields, equivalence relations, and boolean algebras.

This work is joint with Oscar Levin and joint with Joseph Miller.

Axioms for Nakano spaces

Nakano spaces are generalizations of classical $L_p$-spaces in which the parameter $p$ is allowed to vary randomly with the underlying measure space. In the recently developed framework of continuous logic for metric structures, certain natural classes of Nakano spaces have been recently shown to be axiomatizable, to admit elimination of quantifiers, and to be stable.

We will discuss these results and point out how to extract axioms.

Ramsey's theorem for trees

A partially ordered set P has the (n,k)-Ramsey property if every coloring of the n-chains of P with k colors has a monochromatic suborder isomorphic to P. In their paper "Reverse mathematics, computability, and partitions of trees", Chubb, Hirst, and McNicholl analyzed the proof theoretic strength of Ramsey's theorem for the complete binary branching tree. I will talk about joint work with Marcia Groszek and Joseph Mileti on Ramsey's theorem for arbitrary trees and answers to some questions raised by Chubb, Hirst, and McNicholl.

• Friday November 21: Bakhadyr Khoussainov (Auckland and Cornell) 2-142 4pm-5pm (Note the unusual day and time)

Computable Models of $\aleph_1$-categorical theories

A complete first order theory T (over a countable language) is $\aleph_1$-categorical if all of its models of cardinality $\aleph_1$ are isomorphic. The theories of vector spaces and algebraically closed fields are typical examples of $\aleph_1$-categorical theories. If T is $\aleph_1$-categorical and has more than one countable model then all countable models of T form an $(\omega + 1)$-chain under elementary embedding (proved by Morley, Baldwin and Lachlan). We investigate which of these models in the $(\omega + 1)$-chain are computable and which are not.

• November 26: No Logic Seminar

Applying Zariski-type structures to the question of Noetherianity of classes of functions

We are using a modified Zariski-type structure to check the question of Noetherianity of the rings of classes of smooth functions, Denjoy-Carleman quasi-analytic classes, (which will be defined in the talk).

Applying Weierstrass division to a function in a Denjoy-Carleman class might produce functions outside that class, as shown by Childress in 1976. Since the standard way of proving that a ring is Noetherian uses Weierstrass division, one is left without any natural methods for settling the issue.

We apply a modification of the concept of a Zariski-type structure to show that a Denjoy-Carleman ring is not Noetherian. The essential point is that the failure of the Weierstrass division property means that too many ideals are prime in this Denjoy-Carleman ring than could be in a Noetherian ring. Using model theory we can capture this phenomenon.

This is a joint work with Andreea Nicoara from UPenn.

• Friday December 5: Maryanthe Malliaris (UC Berkeley) 2-132 4pm-5pm
(Note the unusual day and time; the room has been changed back to our usual location)

Characteristic sequences in unstable theories

I will describe a program of studying the combinatorics of the parameter space of unstable formulas by associating to each $\varphi$ in $T$ a sequence of hypergraphs (the characteristic sequence'') and looking for graph-theoretic dividing lines which are both model-theoretically meaningful and allow for strong decompositions.

Adding club subsets using cardinal preserving forcing extensions

The goal is to provide a characterization of sets which have club subsets in cardinal preserving generic extensions. The major positive results are related to adding club subsets to subsets of \omega_1 and \omega_2 in \omega_1 and \omega_2 preserving extensions. Different approaches to forcing will be presented, and a constructible forcing will be described when possible.