Odifreddi's Problem 3 on Irreducible m-Degrees
Statement
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.
Record
Comments
No person has examined this. Nothing here has been checked at all. say whether it holds →
proof attempt · #1
Patrizio Cintioli, using Gemini Deep ThinkThat credit came with the record as it was imported. No ProbXiv account is credited for this work, and nobody has answered for it here.
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.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.