# MIT Logic Seminar

### Spring 2009 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

• February 4: Organizational meeting

• February 11: No seminar

(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

We prove a uniformly computable version of de Finetti's theorem. The classical result states that an exchangeable sequence of real random variables is a mixture of independent and identically distributed (i.i.d.) sequences of random variables. Moreover, there is a measure-valued random variable, called the directing random measure, conditioned on which the random sequence is i.i.d. The distribution of the directing random measure is unique and is called the de Finetti measure. We show that computable exchangeable sequences of real random variables have computable de Finetti measures.

This is joint work with Daniel Roy.

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 not contain a copy of H as a subgraph, induced or otherwise. Cherlin, Shelah and Shi have shown that for any fixed finite, connected graph H, the theory of the existentially complete H-free graphs is complete and model complete. The question therefore arises: Given a finite connected graph H, can we locate the theory of the existentially complete H-free graphs within Shelah's classification hierarchy (a taxonomy for complete first order theories)? I will provide some very preliminary results in this direction, and describe a 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 pair. When the strings are closely related, the complexity of the pair will be smaller and 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 weakness.

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 of the relation of relative computability alone was raised already by Kleene and Post [1954] in the first paper on the structure of the Turing degrees < DT, ≤T >. It was proven to be definable by Shore and Slaman [1999] by a method that improved a theorem of Jockusch and Shore [1984] to convert an (as yet unpublished) definition of the double jump by Slaman and Woodin (see Slaman [2008]) to one of the jump itself. This proof of the definability of the double jump relied on metamathematical (absoluteness) and set theoretic (forcing) results and applied to the degrees as a whole but not to substructures. We will describe a direct (purely recursion theoretic) approach that proves that the Turing jump is definable in any downward closed subset of D that is closed under the jump and contains the degree 0(ω). There are then many corollaries about definability in, and restrictions on possible automorphisms of, D and such jump ideals.

• March 25: No Seminar

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.

• April 8: No Seminar

A finite automaton perspective on linear orders

Computable model theorists have analysed many classical theorems on linear orders. A standard (and important) example is that 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 ω or ω*. We will show that this theorem fails in the automatic structures setting. 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 stability.

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 the nth 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 Pκ(A).