Extensions of two constructions of Ahmad

Issue title: Oberwolfach Workshop on Computability Theory 2021

Guest editors: Vasco Brattka, Noam Greenberg, Iskander Kalimullin and Mariya Soskova

Article type: Research Article

Authors: Goh, Jun Le^{a; *} | Lempp, Steffen^b | Ng, Keng Meng^c | Soskova, Mariya I.^d

Affiliations: [a] Department of Mathematics, University of Wisconsin, Madison, WI, USA | [b] Department of Mathematics, University of Wisconsin, Madison, WI, USA | [c] Division of Mathematical Sciences, School of Physical and Mathematical Sciences, College of Science, Nanyang Technological University, Singapore | [d] Department of Mathematics, University of Wisconsin, Madison, WI, USA

Correspondence: [*] Corresponding author. junle.goh@wisc.edu.

Abstract: In her 1990 thesis, Ahmad showed that there is a so-called “Ahmad pair”, i.e., there are incomparable Σ20-enumeration degrees a0 and a1 such that every enumeration degree x<a0 is ⩽a1. At the same time, she also showed that there is no “symmetric Ahmad pair”, i.e., there are no incomparable Σ20-enumeration degrees a0 and a1 such that every enumeration degree x0<a0 is ⩽a1 and such that every enumeration degree x1<a1 is ⩽a0. In this paper, we first present a direct proof of Ahmad’s second result. We then show that her first result cannot be extended to an “Ahmad triple”, i.e., there are no Σ20-enumeration degrees a0, a1 and a2 such that both (a0,a1) and (a1,a2) are an Ahmad pair. On the other hand, there is a “weak Ahmad triple”, i.e., there are pairwise incomparable Σ20-enumeration degrees a0, a1 and a2 such that every enumeration degree x<a0 is also ⩽a1 or ⩽a2; however neither (a0,a1) nor (a0,a2) is an Ahmad pair.

Keywords: Enumeration degrees, Ahmad pairs, Ahmad triples

DOI: 10.3233/COM-210380

Journal: Computability, vol. 11, no. 3-4, pp. 269-297, 2022