Turing reducibility as algebraic embeddability (Q1972201): Difference between revisions

Let \(\text{{Sym}}(\omega)\) be the group of all permutations of \(\omega\) (the set of natural numbers). Given a Turing degree \(d\), consider the group \(G_d=\{f\in\text{{Sym}}(\omega)\mid\text{{deg}}(f)\leq d\}\). It is known that the group \(G_d\) provides sufficiently valuable information about the degree \(d\) and, moreover, much can be restored not only from the isomorphism type of this group but also from its elementary properties; see the author's article [Algebra Logika 27, No. 1, 19-36 (1988; Zbl 0649.03024)]. In the article under review, it is proven that, for arbitrary Turing degrees \(d\) and \(s\), the inequality \(d\leq s\) holds if and only if \(G_d\) is embeddable in \(G_s\).