Embedding countable partial orderings in the enumeration degrees and the \(\omega \)-enumeration degrees (Q2907064)

The enumeration degrees (e-degrees) are a well-known extension of the Turing degrees generated by the relation \(\leq_{\mathrm e}\) of enumeration reducibility. Parallel to what \textit{R. W. Robinson} proved [Ann. Math. (2) 93, 285--314 (1971; Zbl 0259.02033)] for the c.e. degrees, this paper's main theorem is that, given any pair of e-degrees \(\mathbf a<\mathbf b\), any countable partial ordering can be embedded in \([\mathbf{a},\mathbf{b}]\) provided that \(\mathbf b\) contains a set that has a good approximation [\textit{A. H. Lachlan} and \textit{R. A. Shore}, Arch. Math. Logic 31, No. 4, 277--285 (1992; Zbl 0848.03023)]. Given a set \(A\), let \(\{A^{[s]}\}_{s\in\omega}\) be a uniformly computable sequence of finite sets. \(A^{[s]}\) is a \textit{good stage} if \(A^{[s]}\subset A\). The sequence \(\{A^{[s]}\}_{s\in\omega}\) is a \textit{good approximation} of \(A\) if and only if, for every \(n\), it contains a good stage that includes \(A\upharpoonright n\) and only finitely many good stages that do not. Then \(x\in A\) iff only finitely many good stages lack \(x\).NEWLINENEWLINE The upper semilattice of \(\omega\)-enumeration degrees may be regarded as an extension of the e-degrees. The enumeration jump \(A'\) of a set \(A\) codes all membership information about sets e-reducible to \(A\). The members of \(\omega\)-enumeration degrees are sequences of length \(\omega\) of natural numbers. The \(\omega\)-\textit{enumeration jump} of \(A=\{A_n\}_{n\in\omega}\) is the jump sequence \(\{P_n(A)\}_{n\in\omega}\), inductively defined: \(P_0(A)= A_n\); \(P_{n+1}(A)= A_{n+1}\oplus P_n'(A)\). So ``every member of the jump sequence contains full information on previous members''. For sequences \(A\) and \(B\) let \(A\leq_{\mathrm e} B\) mean \(A_n\leq_{\mathrm e} B_n\) uniformly in \(n\) (that is, by a uniform sequence of enumeration operators). Define \(A\leq_\omega B\), \(A\) \textit{is \(\omega\)-reducible to} \(B\), by \(A\leq_{\mathrm e} P(B)\). This generates the \(\omega\)-enumeration degrees. An embedding theorem similar to that for the e-degrees is proved for them.NEWLINENEWLINE Let \(\mathbf a^n\) be the \(n\)th \(\omega\)-enumeration jump of the degree \(\mathbf a\). For \(\Sigma^0_2\) \(\omega\)-enumeration degrees \(\mathbf a\) and \(\mathbf b\), \(\mathbf a\leq_\infty\mathbf b\) when and only when \(\mathbf a^n\leq_\omega\mathbf b^n\) for some \(n\). This relation gives rise to the \(\Sigma^0_2\) \(\omega\)-enumeration degrees modulo iterated jump, for which a further embedding result like those above is established.