arxiv: 2605.03066 · v1 · submitted 2026-05-04 · 🧮 math.LO

Recognition: unknown

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

Patrizio Cintioli

Pith reviewed 2026-05-08 02:11 UTC · model grok-4.3

classification 🧮 math.LO

keywords tt-degreesm-degrees1-degreessemirecursive setssimple setscylinderscomputably enumerable setsreducibility

0 comments

The pith

There exists a computably enumerable tt-degree containing no computably enumerable irreducible m-degree.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper answers Odifreddi's question in the negative by exhibiting a c.e. tt-degree whose only c.e. m-degree consists entirely of simple sets. These sets cannot be cylinders, so the m-degree necessarily splits into several distinct 1-degrees and contains no irreducible representative. The argument rests on the structural properties of semirecursive sets with rigid complements constructed by Degtev. A reader cares because the result shows that Jockusch's 1969 theorem, which places an irreducible m-degree inside every c.e. tt-degree, is optimal and cannot be strengthened to demand that the irreducible m-degree itself be c.e.

Core claim

We prove the existence of a c.e. tt-degree that does not contain any c.e. irreducible m-degree. The proof relies on the structural properties of c.e. semirecursive sets with a rigid complement originally constructed by 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. This demonstrates that Jockusch's theorem guaranteeing an irreducible m-degree in every c.e. tt-degree is strictly optimal and cannot be generally strengthened to require such an m-degree to be computably enumerable.

What carries the argument

c.e. semirecursive sets with rigid complement, whose unique c.e. m-degree consists only of simple non-cylinder sets that split into multiple 1-degrees.

If this is right

Jockusch's theorem cannot be strengthened to require the irreducible m-degree to be c.e.
There exist c.e. tt-degrees in which every c.e. m-degree is reducible.
The m-degrees inside certain c.e. tt-degrees must fragment at the 1-degree level.
Odifreddi's Problem 3 receives a negative solution.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Analogous examples may exist for other reducibilities such as wtt-degrees.
The precise number of 1-degrees inside the m-degree of a Degtev set could be determined by further calculation.
The distinction between c.e. and non-c.e. irreducible degrees may appear in other structural questions about simple sets.
Similar rigidity properties might be used to control degree splittings in broader classes of c.e. sets.

Load-bearing premise

The unique c.e. m-degree inside the tt-degree of these Degtev sets consists solely of simple sets that cannot be cylinders.

What would settle it

Exhibiting a cylinder among the c.e. sets that are m-equivalent to one of Degtev's semirecursive sets with rigid complement would falsify the claim.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives a negative answer to Odifreddi's long-open question by showing a c.e. tt-degree whose unique c.e. m-degree splits into multiple 1-degrees via Degtev sets.

read the letter

The core result is that there exists a c.e. tt-degree containing no c.e. irreducible m-degree. The construction takes Degtev's semirecursive sets with rigid complement, shows that the tt-degree they generate has exactly one c.e. m-degree, and that every set in it is simple. Simple sets cannot be cylinders, so the m-degree necessarily splits into several 1-degrees. This also establishes that Jockusch's 1969 theorem cannot be strengthened to guarantee a c.e. irreducible m-degree in every case.

Referee Report

0 major / 3 minor

Summary. The manuscript proves the existence of a c.e. tt-degree containing no c.e. irreducible m-degree (i.e., an m-degree consisting of a single 1-degree). It does so by taking the tt-degree of a c.e. semirecursive set with rigid complement as constructed by Degtev, showing that this tt-degree contains a unique c.e. m-degree whose members are all simple sets. Because simple sets are necessarily non-cylinders, the m-degree splits into multiple 1-degrees. The argument thereby supplies a negative answer to Problem 3 posed by Odifreddi and demonstrates that Jockusch's 1969 theorem guaranteeing an irreducible m-degree in every c.e. tt-degree is optimal with respect to the c.e. requirement.

Significance. If the central claims hold, the result is significant: it resolves a long-standing question in the structure theory of c.e. degrees under strong reducibilities and shows that the irreducible m-degree whose existence is guaranteed by Jockusch cannot in general be taken to be c.e. The proof is an existence argument that correctly invokes the known structural properties of Degtev sets and the non-cylinder property of simple sets; no new parameters or ad-hoc constructions are introduced.

minor comments (3)

§2: The definition of 'rigid complement' is stated only informally; a precise recursive definition or reference to the exact clause in Degtev's original paper would help readers verify the subsequent claims about uniqueness of the c.e. m-degree.
§3, paragraph following the statement of the main theorem: the sentence 'the m-degree splits into multiple 1-degrees' would benefit from an explicit citation to the theorem that every non-cylinder m-degree contains at least two distinct 1-degrees.
References: the bibliography lists Degtev (1973) and Jockusch (1969) but omits the precise page or theorem numbers used in the argument; adding these would improve traceability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and for the positive recommendation to accept. The referee's summary accurately describes the main result, its relation to Odifreddi's Problem 3, and the optimality of Jockusch's theorem.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper establishes an existence result for a c.e. tt-degree lacking any c.e. irreducible m-degree by invoking the external structural properties of Degtev's semirecursive sets with rigid complement together with Jockusch's 1969 theorem. These supporting results originate from independent prior work by different authors and are not self-citations, self-definitions, or fitted parameters renamed as predictions. No derivation step reduces the target claim to an input by construction, and the argument remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof rests on the correctness of Degtev's construction of c.e. semirecursive sets with rigid complement and on standard facts about simple sets and cylinders in recursion theory. No new free parameters or invented entities are introduced in the abstract.

axioms (2)

domain assumption Degtev's c.e. semirecursive sets with rigid complement exist and have the stated structural properties.
Invoked in the abstract as the basis for the tt-degree construction.
standard math Simple sets cannot be cylinders.
Used to conclude that the unique c.e. m-degree splits into multiple 1-degrees.

pith-pipeline@v0.9.0 · 5550 in / 1320 out tokens · 40429 ms · 2026-05-08T02:11:30.908308+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

12 extracted references

[1]

A. N. Degtev,On m-degrees of simple sets. Algebra i Logika, 11(2), 1972, pp. 130–139

1972
[2]

A. N. Degtev,tt- and m-degrees. Algebra i Logika, 12, 1973, pp. 143–161

1973
[3]

Downey,On irreducible m-degrees

R. Downey,On irreducible m-degrees. Rendiconti del Seminario Matematico Università e Politecnico di Torino, 51(2), 1993, pp. 109–112

1993
[4]

C. G. Jockusch Jr.,Relationships between reducibilities. Transactions of the American Mathematical Society, 142, 1969, pp. 229–237

1969
[5]

Odifreddi,Strong Reducibilities

P. Odifreddi,Strong Reducibilities. Bulletin of the American Mathematical Society, 4(1), 1981, pp. 37–86

1981
[6]

Odifreddi,Classical Recursion Theory

P. Odifreddi,Classical Recursion Theory. Studies in Logic and the Foundations of Mathematics, Vol. 125, North-Holland, Amsterdam, 1989

1989
[7]

Odifreddi,Reducibilities

P. Odifreddi,Reducibilities. In: E.R. Griffor (ed.),Handbook of Computability Theory, Elsevier Science B.V., 1999, pp. 89–119

1999
[8]

Odifreddi,Classical Recursion Theory, Volume II

P. Odifreddi,Classical Recursion Theory, Volume II. Studies in Logic and the Foundations of Mathematics, Vol. 143, Elsevier, Amsterdam, 1999

1999
[9]

E. L. Post,Recursively enumerable sets of positive integers and their decision problems. Bulletin of the American Mathematical Society, 50, 1944, pp. 284–316

1944
[10]

Rogers Jr.,Theory of Recursive Functions and Effective Computability

H. Rogers Jr.,Theory of Recursive Functions and Effective Computability. McGraw-Hill, 1967

1967
[11]

R. I. Soare,Recursion theory and Dedekind cuts. Transactions of the American Mathematical Society, 140, 1969, pp. 271–294

1969
[12]

R. I. Soare,Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic, Springer-Verlag, Berlin Heidelberg, 1987. A C.E.tt-DEGREE WITHOUT C.E. IRREDUCIBLEm-DEGREES 5 Mathematics Division, School of Science and Technology, University of Camerino, Italy Email address:patrizio.cintioli@unicam.it

1987