Midwest Computability Seminar


The Midwest Computability Seminar meets twice in the fall and twice in the spring at University of Chicago.  Researchers in computability theory and their students and postdocs from University of Chicago, University of Notre Dame, and University of Wisconsin-Madison plus some others throughout the area regularly attend. Normally we have two half hour talks and two 1-hour talks and a few hours to talk and collaborate with each other.  The seminar started in the fall of 2008.

: Tuesday, September 28th, 2010.
PLACE: Ryerson, University of Chicago.
1100 East 58th Street, Chicago, IL 60637.




Maurice Chiodo
Title: Enumerating subgroups, and the computational complexity of recognising torsion-freeness, in finitely presented groups.
Abstract: We give a construction for a finitely presented group G for which the set of finitely presented groups that embed into G is not recursively enumerable. We do this by showing that from a description of a recursively enumerable set A, we can uniformly construct a finitely presented group G(A) such that the set of orders of torsion elements in G(A) is one-one equivalent to A. As a corollary we show an earlier result by Lempp that the set of torsion-free finitely presented groups is Pi-0-2 complete in the Arithmetic Hierarchy.

Peter Gerdes
Title: A w-REA Set Forming A Minimal Pair With 0'
Abstract: It is easy to see that no n-REA set can form a (non-trivial) minimal pair with  0'  and only slightly more difficult to observe that no w-REA set can form a (non-trivial) minimal pair with 0''.  Shore has asked whether this can be improved to show that no w-REA set forms a (non-trivial) minimal pair with 0'.  We show that no such improvement is possible by constructing a w-REA set C forming a minimal pair with 0'.

Damir Dzhafarov
Title: Reverse mathematics and equivalents of the axiom of choice.
Abstract: I will discuss recent joint work with Carl Mummert studying the reverse mathematics of various maximality principles classically equivalent to the axiom of choice.  We show that these principles have a wide range of strengths in the context of second-order arithmetic, from being equivalent to Z_2, to lying below ACA_0 and being incomparable with WKL_0.  Principles of the latter kind form a rich and complicated structure.  I will discuss some recent development in its study, and how choice principles fit into it.  For example, our results show that modulo \Sigma^0_2 induction, the principle FIP, which asserts that every family of nonempty sets has a maximal subfamily with the property that any finite intersection of its members is nonempty, lies strictly below the principle AMT studied by Hirschfeldt, Shore, and Slaman [2009], and implies the principle OPT.  This gives a surprising connection between the reverse mathematical content of model theoretic principles on the one hand, and of set-theoretic principles on the other.

Andy Lewis
Title: The search for natural definability in the Turing degrees
 Abstract: While the definability of all jump classes other than low has been established through coding techniques, there remains a conspicuous lack of
any natural definability results in the Turing degrees -- I shall detail the state of affairs in a program which looks to address this issue by systematically analyzing the order theoretic properties satisfied by the degrees in the various jump classes.

Previous Seminars:

   If you haven't been receiving the announcements, and you would like to be included in the list, send me an email to antonio at uchicago.edu.