MIT Logic Seminar

Spring 2010
Wednesday 4:30 - 5:30 pm
Room 2-142

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


  • Special Logic Seminar

    Monday, January 25, 2010, 3 PM in 2-131:

    Dilip Raghavan (University of Toronto)

    Cofinal Types of Ultrafilters

    A directed set D is said to be Tukey reducible to another directed set E, written D≤TE, if there is a function f: D → E which maps unbounded subsets of D to unbounded subsets of E. We say D and E are Tukey equivalent, written D≡TE, if D≤TE and E≤TD. The notion of Tukey equivalence tries to capture the idea that two directed posets "look cofinally the same", or have the same "cofinal type". As such, it provides a device for a "rough classification" of directed sets based upon their "cofinal type", as opposed to an exact classification based on their isomorphism type. This notion has recently received a lot of attention in various contexts in set theory. In joint work with Todorcevic, I have investigated the Tukey theory of ultrafilters on the natural numbers, which can naturally be viewed as directed sets under reverse containment. In the case of ultrafilters, Tukey reducibility is coarser than the well studied Rudin-Keisler reducibility (RK reducibility). I will present some recent progress on the Tukey theory of ultrafilters, focusing on the question "under what conditions is Tukey reducibility actually equivalent to RK reducibility?".


  • Special Logic Seminar

    Wednesday, January 27, 2010, 3 PM in 2-135:

    Jan Reimann (University of California, Berkeley)

    Definability and Randomness

    In mathematical logic, one often tries to classify objects by their descriptive complexity, for example, how many quantifier changes are needed to define a subset of the natural numbers. In the theory of dynamical systems, one uses measure theoretic concepts like entropy to describe complex, i.e. random behavior.

    Both approaches can be combined to define randomness for individual objects such as infinite binary sequences. I will discuss various aspects of the following general question: Given an infinite binary sequence, does there exist a (non-atomic) probability measure with respect to which this sequence is random? I will argue that the view from logic opens up new and perhaps unexpected perspectives on the concept of randomness, in particular concerning the role of infinity, but also in relation to other areas like geometric measure theory.


  • Special Logic Seminar

    Friday, January 29, 2010, 3 PM in 2-131:

    Benjamin Miller (Las Cruces, New Mexico)

    Dichotomy Theorems in Descriptive Set Theory

    Since the inception of the subject, dichotomy theorems have played a central role in the development of descriptive set theory. We will discuss approaches to establishing such theorems using ideas from ergodic theory and graph theory.


  • Special Logic Seminar

    Wednesday, February 10, 2010, 4:30PM in 2-142:

    Cameron Freer (MIT)

    The Computability of Exchangeable Sequences

    Exchangeable stochastic processes are of central interest in probability, statistics, and combinatorics. A sequence of random variables is said to be exchangeable if its joint distribution is invariant under the action of the symmetric group on its indices. de Finetti's theorem states that given an exchangeable sequence of real random variables, there is an a.s. unique random measure (whose distribution is known as the mixing measure) conditioned on which the sequence is i.i.d. The question of the computability of the mixing measure has become increasingly important in machine learning and statistics.

    We discuss recent work with Ackerman and Roy that settles this and related questions using techniques from computability theory. We present a computable extension of de Finetti's theorem, and highlight some applications to nonparametric Bayesian statistics and to the design of probabilistic programming languages. We also present a construction that implies the impossibility of a general algorithm for computing conditional distributions, and describe a new method for using forcing arguments in computable probability theory.


    Genericity arguments in groups of finite Morley rank

    The Cherlin-Zilber Algebraicity Conjecture proposes that the simple groups of finite Morley rank, or equivalently the uncountably categorical simple groups, are in-fact Chevalley groups over algebraically closed fields. We shall give a brief overview of the progress towards this conjecture thus far, which has generally involved transfer of methods from the classification of the finite simple groups. There are however crucial model theoretic results proved using the Cherlin's genericity arguments.

    Toricity Theorem. Any p-torsion lies inside a divisible abelian group unless the ambient group of finite Morley rank contains an infinite elementary abelian p-group.

    C(T) Theorem. The centralizer of a divisible abelian torsion group in a connected group of finite Morley rank is itself connected.

    We shall give a flavor of the project demonstrating how the two theorems are applied together in the Prufer 2-rank two case, and we shall prove the C(T) Theorem.


  • February 24: No Logic Seminar


    Blum-Shub-Smale machines and Turing-like degrees

    The Blum-Shub-Smale (BSS) model for computation over reals generalizes Turing machines for more general computation. Early work showed that there is a universal BSS machine and that restricting the runtime of BSS machines leads to a complexity hierarchy with interesting parallels and interactions with discrete complexity theory.

    However, many standard techniques from computability theory cannot be transferred over directly to the BSS context. In particular, there is no enumeration of all BSS machines because each may include real-valued parameters. Hence, the degree structure of the BSS-degrees (defined analogously to the Turing degrees) must be explored with novel techniques.

    In this talk, we will introduce the BSS model and outline some of the foundational results and some new results (joint with Johanna Franklin) in the exploration of the degree structure. In particular, time permitting, we will discuss connections between BSS degrees and Julia sets from dynamical systems.


    Introducing the Bounded Jump

    In recent work with Rod Downey and Selwyn Ng, we show that, for the usual Turing Jump, analogs of Sacks' and Shoenfield's jump inversion fail for both the truth table and bounded Turing (more commonly known as weak truth table) reducibilities. This gives further evidence that since the Turing jump is defined with respect to Turing reducibility, perhaps it is not the "right" jump to be considering on stronger reducibilities. Together with Bernie Anderson, we have defined what we call the bounded jump, a jump operator on the bounded Turing degrees. I will present some desirable properties of the bounded jump.


  • March 17: No Logic Seminar


  • March 24: No Logic Seminar (Spring Break)


  • March 31: No Logic Seminar


  • Thursday April 8, 4:30 pm in 2-136:
    Victoria Gitman (NYC College of Technology – CUNY)
    A natural model of the multiverse axioms

    In the past decades, set theorists studied a multitude of set theoretic universes constructed as forcing extensions or sub-models and often incorporating strong axioms of infinity. Cohen's forcing was generalized to build extensions according to nearly any desired recipe, while Gödel's construction of L was generalized to obtain increasingly sophisticated sub-models. Against this background, it can be argued that set theory moved away from the study of the set theoretic universe to that of the set theoretic Multiverse. Philosophically, a multiverse encompasses a rich collection of possible ZFC-universes. It should include universes satisfying or failing to satisfy Continuum Hypothesis, Martin's Axiom, Diamond Principle, etc. Some universes in the multiverse should be countable from the perspective of other universes, some ill-founded, and some ultrapowers. The multiverses admit a purely mathematical, non-philosophical treatment as mathematical objects in ZFC. We define that a multiverse is simply a nonempty set or class of models of ZFC. The Multiverse Axioms for such collections are intended to capture the richness and interconnectedness of the ZFC worlds. They include:

    • A definable class of a member of the multiverse is also a member.
    • A forcing extension of a member of the multiverse is also a member.
    • Every member of the multiverse is countable/ill-founded from the perspective of another member.
    • Every member of the multiverse is an internal ultrapower of another member; every definable elementary embedding of a member is an iterate of an embedding of another member.

    In this talk, I will introduce the multiverse axioms and show that the collection of all countable computably saturated models of ZFC is a natural model of the multiverse axioms if it is non-empty. A model is computably saturated if it already realizes all its finitely realizable computable types. This is a joint work with Joel David Hamkins.


    Completeness of S4 with respect to the Measure Algebra

    Long before Kripke-frames became the yardstick semantics for the propositional modal language, Tarski and McKinsey interpreted the modal language in topological spaces. Under the topological semantics, formulae are evaluated to arbitrary subsets of a topological space and necessity and possibility are interpreted, respectively, as the interior and closure topological operators. In 1944, Tarski and McKinsey showed that the logic S4 is sound and complete with respect to the usual metric topology of the real interval [0, 1]. Since then, the result has been refined and extended to higher dimensional metric spaces and subspaces.

    But we can also look at the real interval from a measure-theoretic point of view. In recent talks at Stanford and Berkeley, Dana Scott introduced a new model for the propositional modal language — the Measure Algebra. Elements in the Measure Algebra are Lebesgue-measureable subsets of the real interval, [0, 1], up to sets of measure zero, and the algebra is equipped with Boolean operators as well as an interior operator. In evaluating modal formulae to the Measure Algebra, we assign to a given formula an equivalence class of sets that differ from one another by a set of measure zero. This allows us to speak of the probability or weight of any formula under a given valuation. I show that the propositional modal logic S4 is complete for the Measure Algebra. This result extends the classic 1944 result of Tarski and McKinsey to the measure-theoretic structure of the real interval and opens the way for investigating the logic of measure spaces more generally. A first corollary to the proof of completeness that I present is that non-theorems of S4 can be falsified on subsets of [0, 1] of measure arbitrarily close to 1. A second corollary is that Intuitionistic logic is complete for the sub-lattice of open elements of the Measure Algebra.


    Computability and Complexity of Julia Sets

    In this talk I will survey the recent study of the computational properties of dynamical systems that arise from iterating quadratic polynomials on the complex plane. These give rise to the amazing variety of fractals known as Julia sets, and are closely connected to the Mandelbrot set. Julia sets are perhaps the most drawn objects in Mathematics due to their fascinating fractal structure. I will present both positive and negative results on the computability and computational complexity of Julia sets.


    Regular representations of uniform TC0

    The complexity class DLOGTIME-uniform AC0 is known to be a modest subclass of DLOGTIME-uniform TC0. The weakness of AC0 is due, put in logical terms, to the fact that the logics corresponding to AC0 do not have the relativization property and hence they are not regular. This weakness of AC0 has been elaborated in the line of research on the Crane Beach Conjecture. In this talk we show that DLOGTIME-uniform TC0 can be logically characterized in terms of quantifier logics with cardinality quantifiers FO{<}(CS), where S is the range of some polynomial of degree at least two. Then we adapt the key properties of abstract logics to accomodate built-in relations and define the regular interior R-int(L) and regular closure R-cl(L), of a logic L. Finally we show that the Crane Beach Conjecture can be interpreted as a statement concerning the regular interior of a logic and that the regular closure of AC0 is TC0. Joint work with Lauri Hella and Kerkko Luosto.


    The limits of determinacy in second order arithmetic

    The enterprise of calibrating the strength of theorems of classical mathematics, primarily in terms of the (set existence or comprehension) axioms needed to prove them, was begun by Harvey Friedman in the 1970's. It is now called Reverse Mathematics as, to prove that some set of axioms is actually necessary to establish a given theorem, one reverses the standard paradigm by proving that the axioms follow from the theorem (in some weak base theory). The original motivations for the subject were foundational and philosophical. It has become a remarkably fruitful and successful endeavor supplying a framework for both the philosophical questions about existence assumptions and foundational or mathematical ones about construction techniques needed to construct objects that the theorems assert exist.

    There is one common base theory and four more standard systems beyond it. Most theorems of classical mathematics have turned out to be equivalent to one of these systems. We will briefly describe this state of affairs and then move on to a situation that falls far outside the realm of standard reverse mathematics: axioms of determinacy.

    The story begins with Friedman's result [1971] that Borel determinacy is not provable in ZFC (no power set) and Martin's proof [1975] that it is provable in ZFC (with just the required number of iterations of the power set axiom). We then move to low levels of the Borel hierarchy and provability in second order arithmetic (Z2). Friedman proved that Σ05 determinacy is not provable in second order arithmetic and Martin [1974] improved this to Σ04 and presented a proof of Δ04 determinacy that he claimed could be carried out in Z2. Moving up from the bottom, Steel [1976] showed that open Σ01 determinacy is equivalent to the fourth of the standard systems while Tanaka [1990] showed that determinacy for the difference of two open sets is equivalent to the fifth and strongest of them. Various researchers then investigated the strength of Σ02 and Σ03 determinacy reaching about Π13 comprehension.

    Our recent work with Montalbán on this topic began with the realization that the proof by Martin apparently establishing the boundary between provability and unprovability for levels of arithmetic determinacy in second order arithmetic was not a proof in Z2. We have now established the true results which turned out to be quite different and unusual. Determinacy at the various levels of the difference hierarchy on Π03 sets climb up the entire hierarchy of Π1n comprehension axioms in proof theoretic strength. Thus the provability boundary lies well below Δ04 determinacy. These results supply the first natural mathematical theorems that occupy any, let alone all, of the levels above Π12. They also provide a Gödel like phenomena for Σ12 sentences in second order arithmetic (or ZFC) with natural mathematical sentences: φ(n) is provable for each n but ∀ n φ(n) is not provable.

    Joint work with Antonio Montalbán.


    Cantor Codings

    An essential feature of Gödel's 1931 incompleteness proofs is the use of an encoding ("Gödel numbering") of syntactical objects and and relationships (for a given formal system) as non-negative integers and relationships among those integers. We describe a new encoding based on Cantor's pairing function f(x,y) = (1/2)[xx+2xy+yy+3x+y] and use it to obtain simpler and more direct proofs of theorems of Gödel and Matiyasevich. In particular, we use the coding to prove that for every recursively enumerable set W there is a polynomial p(x,y,...) such that ∀ x [x ∈ W ⇔ ∃ y,... (p(x,y,...) = 0)]. We also note possible applications of Cantor coding to analysis and complexity theory.