Midwest Computability Seminar


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.

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




Alexandra Soskova

Title: Strong Jump Inversion

Abstract: We establish a general result with sufficient conditions for a structure 𝒜 to admit strong jump inversion. We say that a structure 𝒜 admits strong jump inversion provided that for every oracle X, if X' computes D(𝒞)' for some 𝒞 ≅ 𝒜, then X computes D(ℬ) for some ℬ ≅ 𝒜. C. Jockusch and R. Soare showed that there are low linear orderings without computable copies, but R. Downey and C. Jockusch showed that every Boolean algebra admits strong jump inversion. More recently, D. Marker and R. Miller have shown that all countable models of DCF0 (the theory of differentially closed fields of characteristic 0) admit strong jump inversion. Our conditions involve an enumeration of B1-types, where these are made up of formulas that are Boolean combinations of existential formulas. Our general result applies to some familiar kinds of structures, including some classes of linear orderings and trees, Boolean algebras with no 1-atom, with some extra information on the complexity of the isomorphism. Our general result gives the result of D. Marker and R. Miller. In order to apply our general result, we produce a computable enumeration of the types realized in models of DCF0. This also yields the fact that the saturated model of DCF0 has a decidable copy.

This is a joint work with W. Calvert, A. Frolov, V. Harizanov, J. Knight, C. McCoy, and S. Vatev.

Tim McNicholl

Title: Effective metric structure theory

Abstract: We will survey recent work on extending the classical computable structure theory program to uncountable metric structures by means of the framework of computable analysis. Specifically, we will summarize results on degrees of categoricity, index sets, and computable presentability for metric spaces and Banach space, especially Lebesgue spaces.

Uri Andrews

Title: Recent developments on the structure of ceers

Abstract: We consider the structure of c.e. equivalence relations (ceers) under computable reduction. That is, if E and R are ceers, then we say ER if and only if there is a computable function f: ω → ω so that nEm if and only if f(n)Rf(m). This structure is simultaneously reminiscent of the r.e. 1-degrees in some ways and the r.e. m-degrees in other ways, while having some interesting unique features of its own. I'll try to give an overview to let you know what is known about this structure and to point to some of the most important (purely based on my personal tastes) open problems in this area.

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.