Midwest Computability Seminar

XXI


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, April 17th, 2018.
PLACE: Ryerson Hall 352 (the Barn), The University of Chicago.
1100 East 58th Street, Chicago, IL 60637.


Speakers:

Schedule:


Abstracts:

Peter Cholak

Title: Encodable by thin sets

Abstract: Let c be a coloring of n-tuples (of ω) by finitely many colors. For l less than the number of colors, a set T is l-thin iff c uses at most l colors to color all the n-tuples from T. We say a set S is RTn<∞,l-encodable iff there is a coloring c as above such that every l-thin set computes S. Wang showed that when l is "large" only the computable sets are RTn <∞,l-encodable. Dorais, Dzhafarov, Hirst, Mileti, and Shafer showed that the hyperarithmetic sets are RTn <∞,l-encodable for "small" l. Cholak and Patey showed that the arithmetic sets are RTn <∞,l-encodable for "medium" l. Of course, what is missing here is the exact definition of small, medium, and large. In the talk we will provide "tight" definitions, at least, for a "few" n. This is joint work with Ludovic Patey. Much of this will be a repeat of my talk at SEALS 2018 but there will be more material.


Meng-Che "Turbo" Ho

Title: Finitely-generated groups are universal

Abstract: It is well-known that any structure can be coded in a graph. Hirschfeldt, Khoussainov, Shore, and Slinko showed that any structure can be coded in a partial ordering, lattice, integral domain, or 2-step nilpotent group, and showed that certain computability properties are preserved under this coding. Recently, Miller, Poonen, Schoutens, and Shlapentokh added fields to this list, and they gave a category-theoretic framework to establish their result. Around the same time, Montalbán introduced the notion of effective interpretation and showed that effectively bi-interpretable structures share many computability-theoretic properties. Thus, using either of these notions, we may define the notions of a class of structures being universal. Harrison-Trainor, Melnikov, Miller, and Montalbán showed that these two notions are indeed equivalent. In joint work with Harrison-Trainor, we use these ideas to define a class of structures being universal within finitely-generated structures. We then use small cancellation techniques from group theory to show that the class of finitely-generated groups with finitely-many constants named is universal within finitely-generated structures. One application of this is to the study of Scott sentences of finitely-generated groups. Julia et al. showed that a finitely-generated structure always have a Σ3 Scott sentence, but most interesting classes of finitely-generated groups admit d-Σ2 Scott sentences. Using the same coding technique, Harrison-Trainor and I construct a finitely-generated group that admits no d-Σ2 Scott sentence.


Ethan McCarthy

Title: Cototal enumeration degrees and the degree spectra of minimal subshifts

Abstract: A set of natural numbers is cototal if it is enumeration-reducible to its complement. The degrees of cototal sets, the cototal degrees, form an intermediate structure between the Turing degrees and the enumeration degrees. We characterize the cototal degrees as the degrees of maximal anti-chain complements on ω<ω, the degrees of enumeration-pointed trees on 2<ω, and the degrees of languages of minimal subshifts on 2ω. As a corollary, we obtain a characterization of the Turing degree spectra of nontrivial minimal subshifts: they are the enumeration cones of cototal sets.


Joe Miller

Title: A structural dichotomy in the enumeration degrees

Abstract: The continuous degrees measure the computability-theoretic content of elements of computable metric spaces. They properly extend the Turing degrees and naturally embed into the enumeration degrees. Although nontotal (i.e., non-Turing) continuous degrees exist, they are all very close to total: joining a continuous degree with a total degree that is not below it always results in a total degree. We call this property "almost totality". Recently, Andrews, Igusa, M., and Soskova proved that almost totality characterizes the continuous degrees inside the enumeration degrees.

In this talk, I will describe another natural structural characterization of the continuous degrees. Kalimullin introduced the notion of a K-pair in order to define the enumeration jump. K-pairs, which can be thought of as "robust minimal pairs", play a part in almost all known definability results in the enumeration degrees. Indeed, they were used to define totality, and hence almost totality. We show that the non-continuous enumeration degrees are exactly the halves of nontrivial K-pairs relative to some (total) degree. Along with the earlier definition of the continuous degrees, this gives us a structural dichotomy in the enumeration degrees.

This talk is on joint work with Ganchev, Kalimullin, and Soskova.


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.