MIT Logic Seminar
Fall 2008
Wednesday 4:30 - 5:30 pm
Room 2-132
There will be tea and cookies available before the seminar in the math
department common room, 2-290. Please join us there!
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)
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.
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.
Links
Archives