Some properties of r-maximal sets and Q₁,N-reducibility
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\).
- Hyperhypersimple sets and \(\mathrm{Q}_{1}\)-reducibility
- Nonbounding \(n\)-c.e. \(Q\)-degrees
- Computably enumerable sets and quasi-reducibility
- \(Q _{1}\)-degrees of c.e. sets
- scientific article; zbMATH DE number 1779426
- \(Q\)-reducibility and \(m\)-reducibility on computably enumerable sets
- Degree structures of conjunctive reducibility
- On the degree structure of equivalence relations under computable reducibility
- Q-degrees of \(n\)-c.e. sets
- Non-isolated quasi-degrees
- \(Q _{1}\)-degrees of c.e. sets
- Automorphisms of the lattice of recursively enumerable sets: Orbits
- scientific article; zbMATH DE number 4059379 (Why is no real title available?)
- scientific article; zbMATH DE number 4091484 (Why is no real title available?)
- scientific article; zbMATH DE number 1232433 (Why is no real title available?)
- scientific article; zbMATH DE number 1779426 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- Major sets, classes of simple sets, and Q-complete sets
- Nowhere simple sets and the lattice of recursively enumerable sets
- On the Degrees of Index Sets. II
- On the Lattice of Recursively Enumerable Sets
- ON WAYS OF CHARACTERIZING COMPLETE SETS
- One class of partial sets
- One strengthening of \(Q\)-reducibility
- Relationships Between Reducibilities
- Semirecursive Sets and Positive Reducibility
- Some Properties of Recursively Inseparable Sets
- Splitting theorems in recursion theory
- Upper semilattice of recursively enumerable Q-degrees
- Upper semilattice of recursively enumerable Q-degrees
- Maximal pairs of computably enumerable sets in the computably Lipschitz degrees
- R.e. Prime powers and total rigidity
- sQ₁-degrees of computably enumerable sets
- Hyperhypersimple sets and \(\mathrm{Q}_{1}\)-reducibility
- Non-isolated quasi-degrees
- scientific article; zbMATH DE number 3961591 (Why is no real title available?)
- scientific article; zbMATH DE number 4059379 (Why is no real title available?)
- 1-reducibility inside an m-degree with a maximal set
- \(Q _{1}\)-degrees of c.e. sets
- scientific article; zbMATH DE number 1779426 (Why is no real title available?)
- Some properties of maximal sets
- On the bounded quasi‐degrees of c.e. sets
- r‐Maximal sets and Q1,N‐reducibility
This page was built for publication: Some properties of \(r\)-maximal sets and \(Q_{1,N}\)-reducibility
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q892147)
