- February 4: Organizational meeting
(Seminar cancelled due to David Mumford's lecture in the New opportunities for the interactions of mathematics and other
disciplines seminar at 4:30 in 4-349.)
Computable de Finetti measures
Classification of Theories of H-Free Graphs: Preliminary Results
Given a graph H, we say that a graph G is H-free if G does
contain a copy of H as a subgraph, induced or otherwise. Cherlin,
Shi have shown that for any fixed finite, connected graph H, the
the existentially complete H-free graphs is complete and model
question therefore arises: Given a finite connected graph H, can we
the theory of the existentially complete H-free graphs within
classification hierarchy (a taxonomy for complete first order
will provide some very preliminary results in this direction, and
plan for further investigation. All definitions will be given.
Do you know how much you know?
Kolmogorov complexity measures the information content of a
finite string. We define the mutual information of two finite strings as the
sum of their
individual complexities minus the complexity of their encoding as a
the strings are closely related, the complexity of the pair will be
hence the mutual information larger.
For infinite sequences there is no universally agreed-upon
definition for mutual
information. I'll present one contender and argue for its
plausibility, and discuss ongoing work with Denis Hirschfeldt on sequences that are low
for information: those that have finite mutual information with themselves.
These have nice
connections to K-triviality and other properties of computational
Some countable Borel equivalence relations
Borel equivalence relations is an area of descriptive set theory
which concerns the complexity of equivalence relations on a standard
Borel space (i.e., a Polish space equipped just with its
σ-algebra of Borel sets). There are interesting examples from
within logic, such as the Turing equivalence relation
≡T. Moreover, many classification problems for other
areas of mathematics can be regarded as equivalence relations on
standard Borel spaces. For instance, the classification problem for
torsion-free abelian groups of rank n corresponds to the
isomorphism equivalence relation on a suitable subspace of
P(Qn). Both of these examples are
instances of countable Borel equivalence relations, that
is, equivalence relations that are Borel as subsets of the plane and
which have the property that every equivalence class is countable.
After giving the definitions, I'll discuss what structure theory exists,
paying close attention to the role of these two special examples.
A local definition of the Turing jump
The issue of the definability of the Turing jump operator in terms
relation of relative computability alone was raised already by
Post  in the first paper on the structure of the Turing
degrees < DT, ≤T >.
It was proven
definable by Shore and Slaman  by a method that improved a
Jockusch and Shore  to convert an (as yet unpublished)
the double jump by Slaman and Woodin (see Slaman ) to one of
itself. This proof of the definability of the double jump relied on
metamathematical (absoluteness) and set theoretic (forcing) results
applied to the degrees as a whole but not to substructures. We will
a direct (purely recursion theoretic) approach that proves that the
jump is definable in any downward closed subset of D
closed under the jump and contains the degree
There are then many corollaries about definability in, and
possible automorphisms of, D and such jump ideals.
Effectiveness in nilpotent groups
It is known that if G is a finitely generated nilpotent
group, then G has solvable word problem (hence G is computable) and the terms in
the upper and lower central series of G are computable. Not surprisingly, the
terms in the upper and lower central series of an infinitely generated computable
nilpotent group need not be computable. In this talk, I will discuss ongoing
work with Barbara Csima about the complexity of the terms in the upper and lower
central series of computable nilpotent groups.
A finite automaton perspective on linear orders
Computable model theorists have analysed many classical
theorems on linear orders. A standard (and important) example is
although any infinite linear order must contain either an infinite
increasing chain or an infinite decreasing chain, there is a
computable linear order with no computable suborder of type ω
ω*. We will show that this theorem fails in the automatic
This pronounced difference between computable model theory and
automatic model theory is the departure point for further questions,
some of which will be mentioned in the talk.
Randomized Models and Continuous Logic
This lecture will present some results which will appear in a
forthcoming joint paper by Itai Ben Yaacov and me. The subject of
continuous model theory was initiated by C.C. Chang and me in the
1960's, and has recently been refined by Henson and others into a
more useable form that looks much like current first order model
theory. Given a first order structure M, a randomization of M is a
continuous structure whose elements are random elements of M. Given
a complete first order theory T, there is a corresponding complete
theory TR in continuous logic whose models are the
randomizations of M. TR has a natural set of axioms and
admits elimination of quantifiers. Heuristically, the random
elements of M behave much like the ordinary elements of M. This idea
is captured by a series of results showing that many model theoretic
properties hold for TR if and only if they hold for T.
These properties include separable categoricity, having a separable
saturated model, having a prime model, omega-stability, and
Trees, Sheaves and Definition by Recursion
We will show there is a topological space for which presheaves are the same thing as trees. We will further show that there is a sheaf on this topological space which has an important relationship with Baire space.
We will then use these connections to show how a definition by transfinite recursion can be thought of as an operation on sheaves, and how the well-definedness of such a definition can be through of as a property of the sheaf we are working on.
This will then allow us to define a second order tree as a sheaf on a tree and to expand our notion of definition by recursion to all well-founded second order trees (even those which are ill-founded as normal trees). We will then mention how these techniques can be used to prove a variant of the
Suslin-Kleene Separation theorem.
- May 6:
David Pincus (Harvard Medical School)
Dependent Choice and Two Topological Theorems
Dependent Choice, DC, allows one to choose a sequence with
value depending on the
previous choices. It is strictly stronger than making choices from
countably many predetermined sets. Two consequences of Dependent Choice in topology are
Urysohn's Lemma and
the countable Tychonoff Theorem. Fraenkel-Mostowski models will be
presented showing these
applications independent of each other. In one case the ZF transfer
of these independences
follows from known theorems; the other ZF transfer is open.
Closed unbounded subsets in Pκ(A)
I will talk about absoluteness of the property of containing
a closed unbounded subset of Pκ(A), where
Pκ(A) is the set
of all subsets x of A with cardinality |x| = κ. We will see some
older results concerning an analogous question in the context
of club subsets of cardinals, and then consider how (and if)
these results can be adapted in a more complicated world of