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

1. S. A. Badaev, S. S. Goncharov, Generalized computable universal numberings, Algebra and Logic, vol. 53 (2014), no. 5, pp. 355–364.
2. 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.
3. A. A. Issakhov, F. Rakymzhankyzy, Hyperimmunity and \(A\)-computable numberings,The Bulletin of Symbolic Logic, vol. 24 (2018), no. 2, pp. 248–249.
4. A. A. Issakhov, Ideals without minimal elements in Rogers semilattices,Algebra and Logic, vol. 54 (2015), no. 3, pp. 197–203.