Rigid many-one degrees contain infinite antichains of $1$-degrees
Odifreddi asked whether every non-irreducible many-one degree must contain an infinite antichain of one-one degrees. Positive answers are known for computably enumerable many-one degrees (Degtev) and, more recently, for many-one degrees admitting a $Δ^0_2$ representative (Batyrshin). In this note we isolate a rigidity principle behind these phenomena. Call a set $A\subseteqω$ \emph{$m$-rigid} if every total computable $m$-autoreduction of $A$ is eventually the identity. We prove that if $A$ is $m$-rigid, then its many-one degree $°_m(A)$ contains an infinite antichain of $1$-degrees. The…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.19960
curl -X POST /api/v1/records/arxiv/2602.19960/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.19960/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'