Khutoretskii's theorem for generalized computable families
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.
- Classical recursion theory. The theory of functions and sets of natural numbers
- Degrees in Which the Recursive Sets are Uniformly Recursive
- Generalized computable numerations and nontrivial Rogers semilattices
- Generalized computable universal numberings
- scientific article; zbMATH DE number 194103 (Why is no real title available?)
- scientific article; zbMATH DE number 1873436 (Why is no real title available?)
- On the cardinality of the upper semilattice of computable enumerations
- On the limit property of the greatest element in the Rogers semilattice
- The Rogers semilattices of generalized computable enumerations
- Universal generalized computable numberings and hyperimmunity
- Universal generalized computable numberings and hyperimmunity
- Weak reducibility of computable and generalized computable numberings
- Bounded reducibility for computable numberings
- Minimal generalized computable enumerations and high degrees
- Dichotomy theorems for families of non-cofinal essential complexity
- Computability and numberings
- Extremal numberings and fixed point theorems
- On the embedding of the first nonconstructive ordinal in the Rogers semilattices
- Embedding of the first nonconstructive ordinal into the Rogers semilattices of families of arithmetic sets
- On Non-principal Arithmetical Numberings and Families
- Some properties of precompletely and positively numbered sets
- On cardinalities of Rogers semilattices for families in the Ershov hierarchy
- Fixed point theorems for minimal numberings
- Notes on classes of minimal numberings of arithmetical set families
- On e-principal and e-complete numberings
This page was built for publication: Khutoretskii's theorem for generalized computable families
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2300906)
