Types of minimal numberings with hyperimmune oracles
Assylbek Issakhov
Authors: Assylbek Issakhov and Fariza Rakymzhankyzy
Let \(F\) be a family of total functions which is computable by an oracle \(A\), where \(A\) is an arbitrary set. A numbering \(\alpha:\omega\mapsto \mathcal F\) is called \(A\)-computable if the binary function \(\alpha(n)(x)\) is \(A\)-computable, [1]. We call a numbering \(\alpha\) decidable (resp., positive, and Friedberg) if equivalence relation \(\theta_{\alpha} = \{ (x,y) \mid \alpha (x) = \alpha (y) \}\) is computable (resp., c.e., and identity).
An infinite set \(A\) is hyperimmune iff no recursive function majorizes \(A\). A degree is called hyperimmune if it contains a hyperimmune set, otherwise it is hyperimmune free. Every nonzero degree comparable with \(0'\) is hyperimmune.
In [2] it was proved that there is a c.e. noncomputable set \(B\) such that \(B\leq_{T} A\) iff for all families \(S\) of sets, it is true that if \(S\) has an \(A\)-computable Friedberg numbering, then \(S\) has infinitely many positive non-decidable \(A\)-computable numberings.
It is known that if \(\mathcal F\) is an infinite \(A\)-computable family of total functions, where \(A\) is a hyperimmune set, then \(\mathcal F\) has infinitely many pairwise nonequivalent \(A\)-computable Friedberg numberings, [3].
Let \(\mathcal F\) be an infinite \(A\)-computable family of total functions, where \(A\) is a hyperimmune set. Then
Theorem. \(\mathcal F\) has infinitely many pairwise nonequivalent positive non-decidable \(A\)-computable numberings.
Theorem. \(\mathcal F\) has infinitely many pairwise nonequivalent minimal non-positive \(A\)-computable numberings.
We know that if \(\mathcal F\) is an infinite \(A\)-computable family of total functions, where \(\emptyset' \leq_{T} A\), then the Rogers semilattice \(R_{A} (\mathcal F)\) contains an ideal without minimal elements, [4]. Now we are interested in investigating such property for the case with hyperimmune oracles.
Bibliography
- S. A. Badaev, S. S. Goncharov, Generalized computable universal numberings, Algebra and Logic, vol. 53 (2014), no. 5, pp. 355–364.
- F. Rakymzhankyzy, N.A. Bazhenov, A.A. Issakhov, B.S. Kalmurzayev, Minimal generalized computable numberings and families of positive preorders,Algebra and Logic, vol. 61 (2022), no. 3, pp. 188–206.
- A. A. Issakhov, F. Rakymzhankyzy, Hyperimmunity and \(A\)-computable numberings,The Bulletin of Symbolic Logic, vol. 24 (2018), no. 2, pp. 248–249.
- A. A. Issakhov, Ideals without minimal elements in Rogers semilattices,Algebra and Logic, vol. 54 (2015), no. 3, pp. 197–203.