MIT Logic Seminar
Wednesday 4:30 - 5:30 pm
There will be tea and cookies available before the seminar in the math
department common room, 2-290. Please join us there!
- 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
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
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
- October 8: No Logic Seminar
- October 15:
Joel David Hamkins (The College of Staten Island of CUNY and
The CUNY Graduate Center)
The technique of forcing in set theory is customarily
as a method for constructing outer as opposed to inner models of set
A set theorist typically has a model of set theory V and constructs
model V[G], the forcing extension, by adjoining a V-generic filter G
some partial order P in V. A switch in perspective, however, allows
view forcing as a method of describing inner models as well. The
simply to search
inwardly for how the model V itself might have arisen by forcing.
set theoretic universe V, we consider the classes W over which V can
realized as a forcing extension V = W[G] by some W-generic filter G.
change in viewpoint is the basis for a collection of questions
the topic we refer to as set-theoretic geology. In this talk, I will
some of the most interesting initial results in the topic, along
abundance of open questions, many of which concern fundamental
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
in W. The model V satisfies the Ground Axiom if there are no such W
contained in V. The model W is a bedrock of V if W is a ground of V
satisfies the Ground Axiom. The mantle of V is the intersection of
grounds of V. The generic mantle of V is the intersection of all
all set forcing extensions of V. Our main initial result is that
of ZFC is the mantle and generic mantle of another model of ZFC. We
this theorem while also controlling the HOD of the final model, as
the generic HOD, the intersection of the HODs of all forcing
Iteratively taking the mantle penetrates down through the inner
what we call the outer core, what remains when all outer layers of
have been stripped away. Many fundamental questions remain open.
This is joint work with Gunter Fuchs (Muenster) and Jonas Reitz (New
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
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
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.
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
are typical examples of $\aleph_1$-categorical theories. If T is $\aleph_1$-categorical and has
one countable model then all countable models of T form an $(\omega + 1)$-chain under
embedding (proved by Morley, Baldwin and Lachlan). We investigate which of these models
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
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
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
Noetherian. The essential point is that the failure of the Weierstrass division property means that too
ideals are prime in this Denjoy-Carleman ring than could be in a Noetherian ring. Using model theory we
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
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