MIT Logic Seminar

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 Eric Rosen.

Schedule

• September 5: Organizational meeting

• September 12: No seminar

• September 19: Bjorn Poonen (U. C. Berkeley, visiting Harvard and MIT in Fall 2007)
  Characterizing Z in Q with a universal-existential formula
  Refining Julia Robinson's 1949 work on the undecidability of the first order theory of Q, we prove that Z is definable in Q by a formula with 2 universal quantifiers followed by 7 existential quantifiers. It follows that there is no algorithm for deciding, given an algebraic family of Q-morphisms, whether there exists one that is surjective on rational points.

• September 26: Eric Rosen (MIT)
  Schanuel's conjecture, the model theory of fields, and a theorem of Ax
  Schanuel's conjecture is a long standing open problem in transcendental number theory, which states that if real numbers x₁, ..., x_n are linearly independent over Q, then the transcendence degree of {x₁, ..., x_n, e^x₁, ... , e^x_n} over Q is at least n. In this talk I will explain some connections to the model theory of the real and complex fields with exponentiation. I will also sketch Ax's proof of a differential algebraic version of Schanuel's conjecture. Then I will briefly discuss recent attempts to extend Ax's result to differential fields of positive characteristic.

• October 3: Peter Koellner (Harvard)
  Incompatible &Omega-Complete Theories
  A very optimistic scenario for completing the axioms of ZFC is that there is a recursively axiomatizable set of axioms A such that ZFC + A is &Omega-complete for specifiable fragments of the universe of sets (such as the theory of V_&lambda where &lambda is the least inaccessible cardinal) and, moreover, that A is unique in that any other A' sharing these features is &Omega-equivalent to A. We prove that under reasonable assumptions that this scenario must fail. More precisely, we show that if there is one such set of axioms A and the &Omega-completeness of A is provable from large cardinal axioms admitting a "weak inner model theory'' then there must be another, incompatible &Omega-complete theory. In fact, there must be an array of such theories and we have a significant amount of control on their features. For example, one can arrange some to imply CH, others to imply not CH. This is joint work with Hugh Woodin.

  In this talk I will motivate the above scenario, introduce the basics of &Omega-logic and give a high-level sketch of the main proof.

• October 10: Matthew Foreman (U.C. Irvine)
  Has the CH been settled?
  A competing alternative to Woodin's "solution" to the Continuum Hypothesis is presented. This alternative is based on generalizing large cardinal axioms in a manner that makes them extremely relevant to "small" sets like the collection of real numbers.

• October 17: Peter Barendse (Boston University)
  A proof of Part(&omega, &omega₁)
  I will discuss the content and the context of a combinatorial theorem of Jech and Shelah generalizing Ramsey's Theorem.

• October 24: Byunghan Kim (Yonsei University)
  Category, imaginaries and amalgamation
  I will speak about the notion of generalized imaginaries (by Hrushovski) via categorical terminology, and its relationship with type-amalgamation.

• October 31: Rehana Patel (Harvard)
  Classification of a family of countably universal graphs
  In this talk, I will describe a family of countably universal graphs first identified by Cherlin, Shelah and Shi in 1999, and locate the theories of these graphs within Shelah's classification hierarchy. En route, I will discuss some connections between the algebraic closure operator for a complete relational theory and the failure of SOP₄, a property that characterises one of the levels of Shelah's classification. All definitions will be given.

• November 7: Jeremy Avigad (Carnegie Mellon)
  Computability and ergodic theory
  Let T be a measure-preserving transformation of a space (X, B, &mu), let f be a measurable function from X to the real numbers, and let x be any element of X. Think of x as denoting the state of a system, T x as denoting the state a unit of time later, and f as being some measurement that one can perform. Imagine now performing a sequence of measurements f(x), f(T x), f(T² x), ..., f(Tⁿ x) and taking their average. The pointwise ergodic theorem says that, in general, this sequence of averages will converge almost everywhere; the mean ergodic theorem says that, as a function of x, the averages converge in the L² norm.

  In general, one cannot compute rates of convergence from the initial data, and, indeed, the limit may not be computable (given reasonable notions of computability for the relevant objects). In short, the ergodic theorems cannot be given a direct computational interpretation. I will explain how proof-theoretic methods yield classically equivalent formulations of the ergodic theorems, which are computably valid; and additional information besides.

• November 14: Neil Immerman (UMass Amherst)
  You can't get there from here: Reasoning about reachability in shape analysis
  In shape analysis we automatically reason about the behavior of programs that allocate and deallocate memory cells and destructively update pointers. We have an abstract structure, A, that represents all the infinitely many possible data structures, i.e., finite graphs, that may occur at a certain point in a program. If s is the next statement to be executed, we must transform A to A' representing all the graphs that may occur after s has been executed.

  So that our representation remains precise and we can deduce useful properties of the program, it is important to reason well about whether certain points, b, are reachable from other points, a. I discuss some approaches that work surprisingly well including (1) adapting ideas from dynamic graph algorithms to compute A' with as precise as possible reachability knowledge; and, (2) writing first-order axioms for reachability for a first-order theorem prover. Usually it is the fact that b is not reachable from a that is harder to prove.

  Some of this work is in collaboration with Tal Lev-Ami, Bill Hesse, Tom Reps, Mooly Sagiv, Siddharth Srivastava, and Greta Yorsh.

• November 21: No seminar (Happy thanksgiving!)

• November 28: William Tait (University of Chicago)
  Cut elimination for subsystems of second-order number theory

• December 5: Liat Kessler (MIT)
  Holomorphic shadows in the eyes of model theory
  Zariski type structures and Zariski geometries were introduced by Hrushovski and Zilber in their study of strongly minimal sets. A motivating example is given by the structure of complex subvarieties in the Cartesian products of a compact complex manifold. We define a holomorphic shadow (in the role of a subvariety) in almost complex manifolds and show that holomorphic shadows in a compact real analytic almost complex manifold form a Zariski structure. Checking this leads to non-trivial geometric results.

• December 12: Richard Shore (Cornell, visiting MIT in Spring 2008)
  The atomic model theorem and type omitting
  We will analyze the complexity of constructing atomic models (of complete atomic theories) and witnesses to some other type omitting theorems. The analysis will be given both in terms of Turing degrees and reverse mathematics. In particular, we provide two type omitting theorems that make no mention of recursion theoretic notions but are nonetheless equivalent to the existence of hyperimmune and nonrecursive degrees, respectively. This is joint work with Denis Hirschfeldt and Theodore Slaman.