Extensions of embeddings in the $\Sigma^0_2$ 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 Σ⁰₂ e-degrees.

The Σ⁰₂ 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 Σ⁰₂ 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 Σ⁰₂ e-degrees. While it is easy to compute whether a given one-quantifier sentence is true in the Σ⁰₂ 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 Σ⁰₂ 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 Σ⁰₂ e-degrees.

logic

Audience: researchers in the topic

---

Computability theory and applications

Series comments: Description: Computability theory, logic

The goal of this endeavor is to run a seminar on the platform Zoom on a weekly basis, perhaps with alternating time slots each of which covers at least three out of four of Europe, North America, Asia, and New Zealand/Australia. While the meetings are always scheduled for Tuesdays, the timezone varies, so please refer to the calendar on the website for details about individual seminars.

---