Midwest Computability Seminar

XIII


The Midwest Computability Seminar is a joint venture between the University of Chicago, the University of Notre Dame, and the University of Wisconsin-Madison. It meets once or twice per semester at the University of Chicago, and is attended by faculty and students from these universities and others in the area. The seminar started in the fall of 2008.

DATE: Tuesday, October 1, 2013.
PLACE: Ryerson Hall 352 (the Barn), The University of Chicago.
1100 East 58th Street, Chicago, IL 60637.


Speakers, with links to slides if available:

Schedule:

Abstracts:

Peter Cholak
Title: On uniform splits of r.e. sets
Abstract: We discuss various splits of r.e. sets starting with the Friedberg split. It turns out that there are many other types of splits. However given an r.e. set W we can uniformly find a Friedberg split of W. We show this uniformity fails for all non-Friedberg splits.

Mushfeq Khan
Title: Density-one points of Π01 classes
Abstract: Recent work on effective versions of the Lebesgue Density Theorem has brought much attention to the class of density-one points: the reals X such that for every effectively closed (i.e., Π01) set C that contains X, the lower Lebesgue density of C at X is 1. As a result, we know a lot about how the 1-random density-one points behave. For example, they comprise a proper subclass of the difference random reals, and are therefore incomplete. This work has had unexpected side effects, such as the recent solution by Day, Miller, et al., of the ML-cupping problem.

However, not much is known about the behavior of density-one points in the absence of randomness. The property of being density-one can be viewed as a generalization of 1-genericity, and this leads to many interesting questions about them. We survey some results that are part of ongoing work in this area. For example, we now know that density-one points can, in general, be complete. We also investigate the thorny issue of dyadic density vs full density.

Víctor A. Ocasio-González
Title: Computability in the class of real closed fields
Abstract: The class of Real Closed Fields (RCF) is known to have very nice model theoretic properties, among them o-minimality and quantifier elimination. In our work, we consider some non-elementary subclasses of RCF and explore their computability theoretic properties. We locate the class of Archimedean Real Closed Fields using Turing computable embeddings and compare it with other non-elementary first order subclasses of RCF. We also explore relative categoricity and show that under some conditions one can obtain a sharp result on the complexity of the relative categoricity of a real closed field that is constructed using a linear order as an oracle.

Jonathan Stephenson
Title: Isomorphisms between lown and computable boolean algebras
Abstract: A long-standing problem in the area of computable structures is to determine for which n every lown boolean algebra is isomorphic to a computable boolean algebra. For those n where such isomorphisms exist, a related problem is that of determining how complicated the isomorphisms between lown boolean algebras and computable algebras must be.

Harris and Montalbán have demonstrated the existence of a low5 boolean algebra that is not isomorphic to any computable boolean algebra via a ∅(7)-computable map. Using Montalbán's machinery for diagonalizable structures, we can show that proofs in the style of Harris and Montalbán's exist for lown+2 boolean algebras whenever they exist for lown boolean algebras.

Previous Seminars:

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