Odifreddi's Problem 3 on Irreducible m-Degrees
Odifreddi asked, as Problem 3 in his surveys "Strong Reducibilities" (1981) and "Reducibilities" (1999), whether every computably enumerable -degree contains a c.e. irreducible -degree, meaning an -degree consisting of a single -degree. Answered negatively: there is a c.e. -degree containing no c.e. irreducible -degree. This also shows Jockusch's 1969 theorem, which produces an irreducible -degree inside every c.e. -degree, is strictly optimal and cannot be strengthened to make that degree c.e.
- Result
- Disproved
- Status
- Resolved
- AI contribution
- AI co-developed
- Method
- Argument
- Field
- Computability theory
- Posed by
- Piergiorgio Odifreddi
- Year posed
- 1981
- Years open
- 45y
- Solved
- 2026-05-04
- Model
- Gemini Deep Think
- Vendor
- Google DeepMind
- Collaborators
- Patrizio Cintioli
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 20 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What the AI did
Credited at the level of the paper rather than the lemma. The author describes the work as the result of an extended human-AI interaction in which several structural ideas and technical arguments emerged from exploratory sessions with Gemini Deep Think, after which he fully reworked and verified all arguments and takes sole responsibility for their correctness. Nothing is attributed step by step, so the contribution is real but unitemised.
Verification
A five-page arXiv preprint, not peer-reviewed. The construction rests on Degtev's c.e. semirecursive sets with rigid complement, so it is short enough to check by hand, but no independent check is on record.
Source
Submitted by Curator34