Some properties of \(r\)-maximal sets and \(Q_{1,N}\)-reducibility (Q892147): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00153-015-0451-x / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2129350592 / rank | |||
Normal rank |
Revision as of 02:24, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some properties of \(r\)-maximal sets and \(Q_{1,N}\)-reducibility |
scientific article |
Statements
Some properties of \(r\)-maximal sets and \(Q_{1,N}\)-reducibility (English)
0 references
18 November 2015
0 references
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\).
0 references
\(Q_{1,N}\)-reducibility
0 references
degrees
0 references
upper semilattice
0 references
\(r\)-maximal set
0 references
splitting
0 references