Some properties of \(r\)-maximal sets and \(Q_{1,N}\)-reducibility
type: Item
instance of: scholarly article
title: Some properties of \(r\)-maximal sets and \(Q_{1,N}\)-reducibility
zbMATH Open document ID: 1348.03037
published in: Archive for Mathematical Logic
publication date: 2015-11-18T00:00:00Z
review text: If there is a computable function \(f\) such that, for all \(x\in\omega\), \[ \text{(a) }x\in A\Longleftrightarrow W_{f(x)}\nsubseteq B\text{, (b) }x\neq y\Longrightarrow W_{f(x)}\cap W_{f(y)}=\varnothing\text{, and (c) }\bigcup_{x\in\omega} W_{f(x)} \] is computable, we say that \(A\) is \(Q_{1,N}\)-reducible to \(B\). This relation, due to Bulitko, generates the \(Q_{1,N}\)-degrees. Condition (a) characterizes \(Q\)-reducibility, which yields the \(Q\) degrees; (a) and (b) together define \(Q_1\)-reducibility, generating the \(Q_1\) degrees. \(Q_1\)-reducibility was studied by the author and \textit{I. O. Chitaia} [Arch. Math. Logic 51, No. 5--6, 503--515 (2012; Zbl 1257.03065)]. The present paper gives comparable results about the \(Q_{1,N}\)-degrees. Among them: There is a pair of c.e. sets that has no least c.e. upper bound in the \(Q_{1,N}\) ordering, so that the c.e. \(Q_{1,N}\)-degrees are not an upper semilatice. If a set \(A\) belongs to the same \(Q_{1,N}\)-degree as an \(r\)-maximal set \(M\), then \(M\leq_{m}A\). If \(A\) and \(B\) are a Friedberg splitting of an \(r\)-maximal set, every c.e. set in the \(Q_{1,N}\)-degree of \(A\) is isomorphic to \(A\).
reviewed by: Joseph S. Ullian
Mathematics Subject Classification ID: 03D25
Mathematics Subject Classification ID: 03D30
zbMATH DE Number: 6511010
zbMATH Keywords: \(Q_{1,N}\)-reducibility
zbMATH Keywords: degrees
zbMATH Keywords: upper semilattice
zbMATH Keywords: \(r\)-maximal set
zbMATH Keywords: splitting
author: Roland Sh. Omanadze
MaRDI profile type: Publication
full work available at URL: s00153-015-0451-x
OpenAlex ID: W2129350592
cites work: On the Lattice of Recursively Enumerable Sets
cites work: ON WAYS OF CHARACTERIZING COMPLETE SETS
cites work: Some Properties of Recursively Inseparable Sets
cites work: Q4223080
cites work: Automorphisms of the lattice of recursively enumerable sets: Orbits
cites work: Splitting theorems in recursion theory
cites work: Semirecursive Sets and Positive Reducibility
cites work: Relationships Between Reducibilities
cites work: One class of partial sets
cites work: Upper semilattice of recursively enumerable Q-degrees
cites work: Q3794171
cites work: One strengthening of \(Q\)-reducibility
cites work: Q4542698
cites work: Major sets, classes of simple sets, and Q-complete sets
cites work: \(Q _{1}\)-degrees of c.e. sets
cites work: Q5573961
cites work: Nowhere simple sets and the lattice of recursively enumerable sets
cites work: Q3819052
cites work: On the Degrees of Index Sets. II
DOI: 10.1007/S00153-015-0451-X
Recommended article: Hyperhypersimple sets and Q1 -reducibility
Recommended article: Q3406680
Recommended article: Computably enumerable sets and quasi-reducibility
Recommended article: \(Q _{1}\)-degrees of c.e. sets
Recommended article: Q4542698
Recommended article: \(Q\)-reducibility and \(m\)-reducibility on computably enumerable sets
Recommended article: Degree structures of conjunctive reducibility
Recommended article: On the degree structure of equivalence relations under computable reducibility
Recommended article: Q-degrees of \(n\)-c.e. sets
Recommended article: Non-isolated quasi-degrees
description: scientific article; zbMATH DE number 6511010