A computably enumerable many-one degree with no least finite-one degree
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914467439181824 |
|---|---|
| author | Cintioli, Patrizio |
| author_facet | Cintioli, Patrizio |
| contents | Richter, Stephan, and Zhang asked whether every nonrecursive many-one degree contains a least finite-one degree. We solve this question in the negative, already within the class of computably enumerable many-one degrees. Positive answers are known in two disjoint natural settings: for a measure-one and comeager class of $m$-rigid sets, and, in a companion paper, for computably enumerable many-one degrees containing a $D$-maximal set. We construct a nonrecursive \ce\ set $A$ such that for every set $X \eqm A$ there exists a c.e.\ set $B \eqm A$ with $X \not\lfo B$. Hence the many-one degree of $A$ contains no least finite-one degree. The proof is a finite-injury priority construction based on virtual target sets and a dynamic trap mechanism forcing any putative finite-one reduction either to violate finite-oneness or to compute an incorrect reduction. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_10879 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A computably enumerable many-one degree with no least finite-one degree Cintioli, Patrizio Logic 03D30, 03D25 Richter, Stephan, and Zhang asked whether every nonrecursive many-one degree contains a least finite-one degree. We solve this question in the negative, already within the class of computably enumerable many-one degrees. Positive answers are known in two disjoint natural settings: for a measure-one and comeager class of $m$-rigid sets, and, in a companion paper, for computably enumerable many-one degrees containing a $D$-maximal set. We construct a nonrecursive \ce\ set $A$ such that for every set $X \eqm A$ there exists a c.e.\ set $B \eqm A$ with $X \not\lfo B$. Hence the many-one degree of $A$ contains no least finite-one degree. The proof is a finite-injury priority construction based on virtual target sets and a dynamic trap mechanism forcing any putative finite-one reduction either to violate finite-oneness or to compute an incorrect reduction. |
| title | A computably enumerable many-one degree with no least finite-one degree |
| topic | Logic 03D30, 03D25 |
| url | https://arxiv.org/abs/2604.10879 |