Midwest Computability Seminar

XXVIII
Part v


The Midwest Computability Seminar will meet remotely in the winter and spring of 2022, jointly with the Computability Theory and Applications Online Seminar. The recurring Zoom link is:

https://notredame.zoom.us/j/99754332165?pwd=RytjK1RFZU5KWnZxZ3VFK0g4YTMyQT09

Meeting ID: 997 5433 2165

Passcode: midwest


slides    Panopto video     YouTube video


DATE: Monday, April 4th, 2022

TIME: 3:30 - 4:30 PM Central Time


SPEAKER: Jun Le Goh - University of Wisconsin

TITLE: Extensions of embeddings in the Σ02 enumeration degrees

ABSTRACT: In order to measure the algorithmic content of partial functions, or the positive information content of subsets of the natural numbers, one can use the notion of enumeration reducibility. The associated degree structure, known as the enumeration degrees (e-degrees), forms a superstructure of the Turing degrees. We present ongoing work with Steffen Lempp, Keng Meng Ng and Mariya Soskova on the algebraic properties of a countable substructure of the e-degrees, namely the Σ02 e-degrees.

The Σ02 e-degrees are analogous to the computably enumerable (c.e.) Turing degrees but these structures are not elementarily equivalent as partial orders. Indeed, Ahmad showed that there are incomparable Σ02 e-degrees a and b such that if c < a, then c < b, implying that a cannot be expressed as the join of two degrees below it. This stands in contrast to Sacks's splitting theorem for the c.e. Turing degrees.

One can view Ahmad's result as a two-quantifier sentence in the language of partial orders which holds in the Σ02 e-degrees. While it is easy to compute whether a given one-quantifier sentence is true in the Σ02 e-degrees (because all finite partial orders embed), the corresponding task for two-quantifier sentences (which corresponds to an extension of embeddings problem) is not known to be algorithmically decidable. Towards solving this problem, we investigate the extent to which Ahmad's result can be generalized. For instance, we show that it does not generalize to triples: For any incomparable Σ02 e-degrees a, b and c, there is some x such that one of the following holds: x is below a but not below b, or x is below b but not below c.

We shall also discuss speculative generalizations of the above result, and how they may lead to an algorithm which decides a class of two-quantifier sentences in the Σ02 e-degrees.



Past and Future Sessions

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.