Turing reducibility as algebraic embeddability
type: Item
instance of: scholarly article
title: Turing reducibility as algebraic embeddability
zbMATH Open document ID: 0937.03052
DOI: 10.1007/BF02674629
published in: Siberian Mathematical Journal
publication date: 2000-04-16T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 03D28
Mathematics Subject Classification ID: 03D30
zbMATH DE Number: 1432386
zbMATH Keywords: Turing reducibility
zbMATH Keywords: Turing degree
zbMATH Keywords: group of permutations of natural numbers
zbMATH Keywords: embedding of groups
author: Andrei S. Morozov
MaRDI profile type: Publication
cites work: Q5573961
cites work: Permutations and implicit definability
full work available at URL: https://doi.org/10.1007/bf02674629
OpenAlex ID: W2008347630
description: scientific article; zbMATH DE number 1432386