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
1100 East 58th Street, Chicago, IL 60637.
- Peter Cholak - University of Notre Dame
- Meng-Che "Turbo" Ho - Purdue University
- Ethan McCarthy - University of Wisconsin
- Joe Miller - University of Wisconsin
- 2:00 - 2:45: Peter Cholak
- 2:50 - 3:35: Ethan McCarthy
- 3:40 - 4:20: Break
- 4:20 - 5:05: Joe Miller
- 5:10 - 5:55: Meng-Che "Turbo" Ho
- 6:15 Dinner at Jolly
Pumpkin, 5215 S. Harper Ave.
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
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
Title: Cototal enumeration degrees and the degree spectra of
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 ω<ω,
degrees of enumeration-pointed trees on 2<ω, and the
languages of minimal subshifts on 2ω. As a corollary, we
characterization of the Turing degree spectra of nontrivial minimal
subshifts: they are the enumeration cones of cototal sets.
Title: A structural dichotomy in the enumeration degrees
Abstract: The continuous degrees measure the computability-theoretic
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.
If you haven't
been receiving the announcements and would like to be included
in the list, send an email to email@example.com.