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

- 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 University)**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.