A Computably Enumerable tt-Degree Without Computably Enumerable Irreducible m-Degrees

Abstract

In this paper, we provide a negative solution to Problem 3 formulated by P.~Odifreddi in his survey articles \textit{``Strong Reducibilities''} (1981) and \textit{``Reducibilities''} (1999). The problem asks whether every computably enumerable (c.e.) tt-degree contains a c.e.\ \textit{irreducible} m-degree (i.e., an m-degree consisting of only one $1$-degree). We answer this question in the negative by proving the existence of a c.e.\ tt-degree that does not contain any c.e.\ irreducible m-degree. Our proof relies on the structural properties of c.e.\ semirecursive sets with a rigid complement, originally constructed by A.~N.~Degtev. We show that the unique c.e.\ m-degree contained within the tt-degree of such a set consists of simple sets, which cannot be cylinders, and therefore necessarily splits into multiple $1$-degrees. Furthermore, our result demonstrates that a classical 1969 theorem by C.~G.~Jockusch Jr. -- which guarantees the existence of an irreducible m-degree within every c.e.\ tt-degree -- is strictly optimal and cannot be generally strengthened to require such an m-degree to be computably enumerable.

The pattern of consistency strength for membership in a computably enumerable set
Joel David Hamkins, Atticus Stonestrom
arXiv17 Oct 2026PreprintarXiv licenceFull textLogic & foundationsarXiv
A non-recursively enumerable set W⊆N, where N\W is recursively enumerable and the predicate n∈W expresses a fundamental property of n
Apoloniusz Tyszka
HAL16 Sep 2026PreprintCC BY-NC-ND 4.0Full textAlgebra & number theory Logic & foundationsHAL
Controllability of polynomial systems is undecidable and not recursively enumerable
Jun Liu, Ivan O. Shevchenko
arXiv19 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Strongly isotropy irreducible spaces whose Laplacians have all their eigenspaces irreducible
Emilio A. Lauret, Fiorela Rossi Bertone
arXiv10 Oct 2026PreprintarXiv licenceFull textGeometry & topologyarXiv
Finite-dimensional irreducible representations of Yangians
Mikhail Gradov, Aleksei Ilin
arXiv29 Oct 2026PreprintCC BY 4.0Full textAlgebra & number theoryarXiv

Cite

BibTeX RIS

BibTeX

@misc{cintioli2026computably,
  title = {{A Computably Enumerable $tt$-Degree Without Computably Enumerable Irreducible $m$-Degrees}},
  author = {Patrizio Cintioli},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2605.03066},
  eprint = {2605.03066},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.03066},
}

RIS

TY  - UNPB
TI  - A Computably Enumerable tt-Degree Without Computably Enumerable Irreducible m-Degrees
AU  - Patrizio Cintioli
PY  - 2026
DA  - 2026/09/21
PB  - arXiv
DO  - 10.48550/arxiv.2605.03066
UR  - https://arxiv.org/abs/2605.03066
AB  - In this paper, we provide a negative solution to Problem 3 formulated by P.~Odifreddi in his survey articles \textit{``Strong Reducibilities''} (1981) and \textit{``Reducibilities''} (1999). The problem asks whether every computably enumerable (c.e.) tt-degree contains a c.e.\ \textit{irreducible} m-degree (i.e., an m-degree consisting of only one $1$-degree). We answer this question in the negative by proving the existence of a c.e.\ tt-degree that does not contain any c.e.\ irreducible m-degree. Our proof relies on the structural properties of c.e.\ semirecursive sets with a rigid complement, originally constructed by A.~N.~Degtev. We show that the unique c.e.\ m-degree contained within the tt-degree of such a set consists of simple sets, which cannot be cylinders, and therefore necessarily splits into multiple $1$-degrees. Furthermore, our result demonstrates that a classical 1969 theorem by C.~G.~Jockusch Jr. -- which guarantees the existence of an irreducible m-degree within every c.e.\ tt-degree -- is strictly optimal and cannot be generally strengthened to require such an m-degree to be computably enumerable.
ER  -

Abstract

Related

Cite