An algebraic decomposition of the recursively enumerable degrees and the coincidence of several degree classes with the promptly simple degrees

Abstract

We specify a definable decomposition of the upper semilattice of recursively enumerable (r.e.) degrees <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="bold upper R"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="bold">R</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathbf {R}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> as the disjoint union of an ideal <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="bold upper M"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="bold">M</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathbf {M}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and a strong filter <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="bold upper N bold upper C"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="bold">N</mml:mi> <mml:mi mathvariant="bold">C</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathbf {NC}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. The ideal <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="bold upper M"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="bold">M</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathbf {M}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> consists of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="bold 0"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn mathvariant="bold">0</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathbf {0}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> together with all degrees which are parts of r.e. minimal pairs, and thus the degrees in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="bold upper N bold upper C"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="bold">N</mml:mi> <mml:mi mathvariant="bold">C</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathbf {NC}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> are called noncappable degrees. Furthermore, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="bold upper N bold upper C"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="bold">N</mml:mi> <mml:mi mathvariant="bold">C</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathbf {NC}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> coincides with five other apparently unrelated subclasses of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="bold upper R bold colon bold upper E bold upper N bold upper C"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="bold">R</mml:mi> <mml:mo mathvariant="bold">:</mml:mo> <mml:mi mathvariant="bold">E</mml:mi> <mml:mi mathvariant="bold">N</mml:mi> <mml:mi mathvariant="bold">C</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathbf {R: ENC}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, the effectively noncappable degrees; <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="bold upper P bold upper S"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="bold">P</mml:mi> <mml:mi mathvariant="bold">S</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathbf {PS}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, the degrees of promptly simple sets; <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="bold upper L bold upper C"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="bold">L</mml:mi> <mml:mi mathvariant="bold">C</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathbf {LC}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, the r.e. degrees cuppable to <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="bold 0 prime"> <mml:semantics> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn mathvariant="bold">0</mml:mn> </mml:mrow> </mml:mrow> <mml:mo>′</mml:mo> </mml:msup> <mml:annotation encoding="application/x-tex">{\mathbf {0}}’</mml:annotation> </mml:semantics> </mml:math> </inline-formula> by a low r.e. degree; <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="bold upper S bold upper P bold upper H overbar"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="bold">S</mml:mi> <mml:mi mathvariant="bold">P</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mover> <mml:mi mathvariant="bold">H</mml:mi> <mml:mo mathvariant="bold" stretchy="false">¯</mml:mo> </mml:mover> </mml:mrow> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">{\mathbf {SP\bar H}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, the degrees of non-<inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="h h"> <mml:semantics> <mml:mrow> <mml:mi>h</mml:mi> <mml:mi>h</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">hh</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-simple r.e. sets with the splitting property; and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="bold upper G"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="bold">G</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathbf {G}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, the degrees in the orbit of an r.e. generic set under automorphisms of the lattice of r.e. sets.