7 papers · 1 filter
A Computably Enumerable -Degree Without Computably Enumerable Irreducible -Degrees
Patrizio Cintioli
In this paper, we provide a negative solution to Problem 3 formulated by P.~Odifreddi in his survey articles \textit{``Strong Reducibilities''} (1981) and \textit{``Reducibilities'…
\texorpdfstring{}{D}-maximal many-one degrees contain least finite-one degrees
Patrizio Cintioli
Richter, Stephan, and Zhang asked whether every nonrecursive many-one degree contains a least finite-one degree. We prove this for every nonrecursive \ce\ many-one degree containin…
A computably enumerable many-one degree with no least finite-one degree
Patrizio Cintioli
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…
Dense Chains, Antichains, and Universal Partial Orders Inside a Bounded Finite-One Degree
Patrizio Cintioli
We construct a nonrecursive set \(A\le_T\emptyset'\) and a uniformly computable family of sets \(C_0,C_1,\dots\), all bounded finite-one equivalent to \(A\), such that the correspo…
A -introimmune set in \texorpdfstring{}{Pi01} and introimmunity for several reducibilities
Patrizio Cintioli
We prove that there exists a weak truth-table introimmune set in the class , settling the question left open in previous work of whether the known existence result…
-Rigidity and Finite-One Degrees Inside Typical Many-One Degrees
Patrizio Cintioli
In recent work, the notion of -rigidity was introduced as a sufficient condition for the existence of infinite antichains of -degrees inside many-one degrees. Motivated by a…