Embedding countable partial orderings in the enumeration degrees and the \(\omega \)-enumeration degrees
type: Item
instance of: scholarly article
zbMATH Open document ID: 1267.03048
author: Ivan N. Soskov
author: Mariya I. Soskova
publication date: 2012-09-05T00:00:00Z
Mathematics Subject Classification ID: 03D30
zbMATH DE Number: 6078056
zbMATH Keywords: enumeration degrees
zbMATH Keywords: \(\omega \)-enumeration degrees
zbMATH Keywords: partial orderings
zbMATH Keywords: iterated jumps
zbMATH Keywords: good approximations
MaRDI profile type: Publication
OpenAlex ID: W2098886724
DOI: 10.1093/LOGCOM/EXQ051
Recommended article: Embedding of countable orders in Turing degrees
Recommended article: Q4895457
Recommended article: The -Enumeration Degrees
Recommended article: ON EXTENSIONS OF EMBEDDINGS INTO THE ENUMERATION DEGREES OF THE ${\Sigma_2^0}$-SETS
Recommended article: On the order dimension of locally countable partial orderings
Recommended article: Q4513972
Recommended article: Some applications of order-embeddings of countable ordinals into the real line
Recommended article: Extensions of Embeddings in the Computably Enumerable Degrees
Recommended article: Q4863245
Recommended article: Extension of embeddings in the computably enumerable degrees
title: Embedding countable partial orderings in the enumeration degrees and the \(\omega \)-enumeration degrees
published in: Journal of Logic and Computation
review text: 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 th…
reviewed by: Joseph S. Ullian
description: scientific article; zbMATH DE number 6078056