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 Richard Shore.

Schedule

• February 6: Joseph Miller (University of Connecticut)
  Extracting information is hard
  Can randomness -- or more technically, "information" -- be effectively extracted from a semi-random source? A special case of this question was answered by von Neumann in 1951. He described a simple method for extracting an unbiased random sequence from the flips of a biased coin. A more general form of the question was asked by Reimann and Terwijn in the context of algorithmic randomness, so we will start with an introduction to Kolmogorov complexity, effective Hausdorff dimension, and Martin-Lf randomness. Kolmogorov complexity measures the information content of a finite binary string. Informally, the complexity of a string is defined to be the length of the shortest program that generates it. A closely related notion, effective (Hausdorff) dimension, measures the information density of a infinite binary sequences. We can now formulate the question in terms of effective dimension: is there a sequence that has effective Hausdorff dimension 1/2 -- in other words, a half-random sequence -- that does not compute a sequence of higher effective dimension? As it turns out, such sequences exist. We will discuss this result and its proof, which involves a novel forcing notion.

• February 13: Antonio Montalban (University of Chicago)
  The isomorphism problem for torsion-free Abelian groups is analytic complete
  We prove that the isomorphism problem for torsion-free Abelian groups is as complicated as any isomorphism problem could be in terms of the analytical hierarchy, namely $\Sigma^1_1$ complete.

• February 20: Brooke Anderson (Dartmouth)
  Strong notions of reducibility and completeness
  We consider a notion of Turing reducibility which is always total on recursively enumerable oracles. This notion of reducibility is implied by truth-table reducibility, but is different from truth-table, weak truth-table, bounded search and Turing reducibilities on r.e. sets. Moreover, it is not transitive. We add a condition, called positivity, to make this notion transitive and see that this is still different from other strong notions of reducibility. I will show how we can use complete sets to distinguish this reducibility from other notions. This is work for my thesis. This reducibility was first studied by Marcia Groszek, Rebecca Weber and Pete Winkler.

• February 27: Michael O'Connor(Cornell University)
  Using Tree Automata to Reason about Intuitionistic Logic
  Intuitionistic propositional logic has semantic and algebraic structures analogous to those of classical logic, but the the corresponding questions are often significantly harder. In this talk, I will indicate a connection between formulas in intuitionistic logic and tree automata and discuss how this can be used to answer some structural questions about the logic. No familiarity with intuitionistic logic will be assumed.

• March 5: Charles Steinhorn (Vassar)
  On ordered structures of higher rank
  It has been widely thought that o-minimal structures might lie at the first level of a hierarchy of ordered structures, in analogy with strongly minimal structures. In joint work with A. Onshuus, we develop a framework for ordered structures of finite rank. In particular, we analyze linear orders definable in o-minimal structures, and this will be the focus of the first part of the talk. This analysis appears to have an interesting application in mathematical economics---joint work with T. Brihaye, C. Michaux, and Onshuus---discussion of which is the subject of the second part of the talk.

• March 12: Joseph Mileti (Dartmouth)
  Immunity, Measure, and Combinatorics
  We will discuss how hyperimmune sets ("sparse" subsets of the natural numbers originally arising in attempts to solve Post's problem), and the measure of some sets related to them, help us understand the reverse mathematics of several combinatorial statements.

• March 19: Ehud Hrushovski (Hebrew University of Jerusalem and Yale University)
  Invariant types and NIP
  Stability theory is based on the notion of an {\em invariant type}, giving a type over $M$ uniformly in a model $M$ of $T$. Generalizations were found to simple theories, but the methods did not apply to structures such as valued fields. Recent work on theories without Shelah's independence property (NIP) is beginning to show that invariant types are important in this context too, at various levels of generality. I will discuss some of the emerging theory, including uniqueness theorems and conjectures for invariant measures (joint work with Pillay) and the role of invariant types in the classification of definable equivalence relations in valued fields (joint work with Haskell, Macpherson.)

  
  

• March 26: Spring Break - No Seminar

  
  

• April 2: Paul Shafer (Cornell Uinversity)
  Reverse Mathematics and Menger's Theorem
  We discuss the axiomatic strength of two related theorems from infinite matching theory: Menger's theorem and its special case Konig's duality theorem. The infinite version of Konig's duality theorem states that in any bipartite graph there exists a cover obtained by selecting one vertex from each edge in some matching. Aharoni, Magidor, Shore, and Simpson have shown that transfinite recursion is both necessary and sufficient to prove Konig's duality theorem for countable graphs. We begin a similar analysis of the infinite version of Menger's theorem, which states that if A and B are sets of vertices in a graph, then there exists a collection of disjoint A-B paths and a selection of one vertex from each of these paths whose removal disconnects A and B. Menger's theorem for countable graphs requires transfinite recursion because it implies Konig's duality theorem. We will give an overview of the known proof of Menger's theorem which uses the stronger axioms of Pi_1^1-comprehension.

  
  

• April 9: David Pincus (Harvard Medical School)
  A Natural Model for a Choice Alternative
  Set theorists are familiar with L(R), the least model of set theory containing the ordinal and real numbers. In fact it has been shown that if the universe satisfies the axiom of choice (AC) and has suitable large cardinal axioms, L(R) satisfies the most appealing alternative to AC, the axiom of determinacy. There is another inner model in which AC fails under much more modest large cardinal assumptions about the universe. This is L(J), the least model of set theory containing the ordinal and Jensen real numbers. The theory of L(J) is very different. In fact it satisfies the Boolean prime ideal theorem, the Leibniz--Mycielski axiom, and the existence of a projective Dedekind-finite set of real numbers.

  
  

• April 16: Peter Barendse (Boston University)
  Regressive Functions
  Taking the idea as basic, we explore of the consistency strength and implication strength of various statements about regressive functions, from those provable in PA, to some which imply the existence of large large cardinals.

  
  

• April 23: Aki Kanamori (Boston University)
  $\diamondsuit_{\kappa^+}$ iff $2^\kappa = \kappa^+$ for uncountable $\kappa$.
  The principle $\diamondsuit_\kappa$ was the first of several combinatorial principles devised by Ronald Jensen in his investigations of the constructible universe. For four decades it has remained a pivotal principle through numerous results in set theory. In late 2007, Saharon Shelah established, surprisingly, that $\diamondsuit_{\kappa^+}$ is actually a consequence of the ostensiblly weaker $2^\kappa = \kappa^+$, except in the well-known case, $\kappa = \aleph_0$. We will (try to) give a complete proof of Shelah's result.

  
  

• April 30: Rebecca Weber (Dartmouth College)
  Definability and Invariance
  A collection of computably enumerable Turing degrees is called invariant if it corresponds to a collection of c.e. sets which are invariant in the usual sense, under automorphisms of the lattice of all c.e. sets. A sweeping definability result by Cholak and Harrington gives the degree invariance of a large number of classes of degrees: the high_n and non-low_n degrees for every n > 1. Another standard structure in computability theory is the lattice of Pi^0_1 classes, or sets of infinite paths through computable trees. Currently there is only one known degree invariant class in the Pi^0_1 classes. We will discuss the status quo and an in-progress translation of the Cholak/Harrington result to a substructure of the lattice of Pi^0_1 classes, with consequences for the lattice as a whole.

  
  

• May 7: Mia Minnes (Cornell University)
  Complexity and simplicity in automatic structures
  Automatic structures come from a specialization of computable structures in which the basic model of computation is the finite automaton instead of the Turing machine. The algorithmic and model theoretic study of such structures has been an active area of study since the mid 1990s. Moreover, automatic structures have seen applications in geometric groups theory, program verification, and decision procedures. We will discuss tight characterisation results for certain classes of automatic structures (including ordinals and partial orders). In contrast, we will also show that automatic structures in general can be very complicated (in terms of ordinal heights and Scott ranks).

  
  

• May 14: Reed Solomon (University of Connecticut)
  Computable categoricity and self-embeddings for computable trees
  There are a number of known results concerning the complexity of nontrivial self-embeddings of computable linear orders. In this talk we will consider similar questions in the context of computable trees as well as results concerning computable categoricity for computable trees.

Links

Logic at MIT
Other seminars at MIT
MIT Department of Mathematics

Archives

Fall 2007