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!

For more information, or to be added to the mailing list, contact Cameron Freer or Mia Minnes.

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 essentially 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).

 

 

 

Calendar

 

Fall 2008 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.

Links

Archives