On quasi-reducibility for c.e. sets Part I. The structure of the <i>Q</i> -degrees and the <i>sQ</i> -degrees
Abstract We study the structure of the c.e. $Q$- and $sQ$-degrees. For both structures, we show that there are join irreducible degrees but no Ahmad pairs. We show that the structures are not distributive, and that the lattice $N_{5}$ embeds in both structures. On the other hand the lattice $M_{5}$ cannot be embedded in the c.e. $sQ$-degrees, but a critical triple can be embedded. Finally, we show that no initial segment of the c.e. $sQ$-degrees or the c.e. $Q$-degrees is a lattice.
Authors
- Mariya I. Soskova (ORCID: https://orcid.org/0000-0003-4505-8006)
- Rod Downey
- Sapir Ben-Shahar
Institutions
- University of Wisconsin–Madison (US)
- Victoria University of Wellington (NZ)
Publication Details
- Journal
- Journal of Logic and Computation
- Published
- 2025-12-03
- DOI
- https://doi.org/10.1093/logcom/exaf076
- Primary Topic
- Computability, Logic, AI Algorithms
- Type
- article
- Field-Weighted Citation Impact
- 0.00