Khutoretskii's theorem for generalized computable families (Q2300906)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Khutoretskii's theorem for generalized computable families |
scientific article |
Statements
Khutoretskii's theorem for generalized computable families (English)
0 references
28 February 2020
0 references
In this paper, the author presents sufficient conditions for generalized computable numberings to satisfy the statement of Khutoretskii's theorem. As a consequence, the author gives an affirmative answer to the question concerning limitedness of greatest elements of Rogers semilattices for families of hyperarithmetic sets. A numbering \(\rho \in\mathrm{Com}^A(\mathcal F)\) is \(B\)-universal if \(\nu\leq^B\rho\ \) for all \(\nu\in\mathrm{Com}^A(\mathcal F)\). A numbering \(\rho\) is indecomposable if, for all numberings \(\rho_0\) and \(\rho_1\), the equivalence \(\rho=\rho_0\oplus\rho_1\) implies one of the equivalences \(\rho=\rho_0\) or \(\rho=\rho_1\). A set \(A\) is said to be high over \(B\) if \(B \leq_T A\) and \(B^{\prime\prime}\leq_T A^\prime\). Theorem 1. Let \(B\) be a noncomputable set, \(B \leq A\), and \(\mathcal F\) be an \(A\)-computable family. For any numberings \(\delta,\rho\in \mathrm{Com}^A(\mathcal F) \) such that \(\delta\) is not \(B\)-universal and \(\rho\nleq\delta \), there is a numbering \(\nu\in\mathrm{Com}^A(\mathcal F)\) for which \(\delta <\nu\) and \(\rho\nleq\nu\). Theorem 3. Let \(A\) be a high set over \(B\) and \(\mathcal F\) be an \(A\)-computable family. Suppose also that \(\delta,\rho\in \mathrm{Com}^A(\mathcal F) \), \(\rho\nleq\delta\), and \(\rho\) is indecomposable and \(B\)-universal. Then there exists a numbering \(\nu \in \mathrm{Com}^A(\mathcal F)\) such that \(\delta<\nu\) and \(\rho\nleq\nu\). Corollary 1. Let \(\alpha\geq 2\) be a computable ordinal, \(\mathcal F\) be a \(\Sigma^0_\alpha\)-computable family, \(\delta,\rho\in \mathrm{Com}^0_\alpha(\mathcal F) \), \(\delta<\rho\), and \(\rho\) be indecomposable. Then there exists a numbering \(\nu\in \mathrm{Com}^0_\alpha(\mathcal F) \) \(\delta<\nu\) and \(\rho\nleq\nu\). Corollary 2. Let \(\alpha\geq 2\) be a computable ordinal. If the Rogers semilattice of a \(\Sigma^0_\alpha\)-computable family has a greatest element, then that element is limit.
0 references
Rogers semilattices
0 references
numbering
0 references
hyperarithmetic sets
0 references
computable ordinal
0 references
generalized computable family
0 references
generalized computable numbering
0 references
Khutoretskii's theorem
0 references