Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.19960 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910033432805376 |
|---|---|
| author | Cintioli, Patrizio |
| author_facet | Cintioli, Patrizio |
| contents | 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 proof uses a uniform duplication construction: for each computable parameter $S$ we define $B_S\equiv_m A$ so that any injective reduction $B_S\le_1 B_T$ induces an $m$-autoreduction of $A$ and therefore forces $S\subseteq^{*}T$. Choosing an almost-inclusion infinite antichain of computable sets yields the desired infinite $1$-antichain inside $°_m(A)$.
As applications, Jockusch's rigidity theorem implies that every $1$-generic set is $m$-rigid, giving a comeager family of positive instances. Moreover, $m$-rigidity holds with Lebesgue measure $1$ (indeed, every Martin-Löf random real is $m$-rigid). Consequently, Odifreddi's Question~5 has a positive answer \emph{with probability $1$} for a fair-coin random $A\in 2^ω$; any counterexample (if it exists) is confined to a null set (and, by genericity, also to a meager set). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_19960 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Rigid many-one degrees contain infinite antichains of $1$-degrees Cintioli, Patrizio Logic 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 proof uses a uniform duplication construction: for each computable parameter $S$ we define $B_S\equiv_m A$ so that any injective reduction $B_S\le_1 B_T$ induces an $m$-autoreduction of $A$ and therefore forces $S\subseteq^{*}T$. Choosing an almost-inclusion infinite antichain of computable sets yields the desired infinite $1$-antichain inside $°_m(A)$. As applications, Jockusch's rigidity theorem implies that every $1$-generic set is $m$-rigid, giving a comeager family of positive instances. Moreover, $m$-rigidity holds with Lebesgue measure $1$ (indeed, every Martin-Löf random real is $m$-rigid). Consequently, Odifreddi's Question~5 has a positive answer \emph{with probability $1$} for a fair-coin random $A\in 2^ω$; any counterexample (if it exists) is confined to a null set (and, by genericity, also to a meager set). |
| title | Rigid many-one degrees contain infinite antichains of $1$-degrees |
| topic | Logic |
| url | https://arxiv.org/abs/2602.19960 |