zbMATH — the first resource for mathematics

Discrete families of recursive functions and index sets. (English. Russian original) Zbl 0828.03014
Algebra Logic 33, No. 2, 85-94 (1994); translation from Algebra Logika 33, No. 2, 147-165 (1994).
Second order index sets of the discrete families of partial recursive functions (PRF) are studied.
Let \(\{\varphi_e\}_{e \in \omega}\) be a Gödel numbering of the set of PRF. The \(e\)-th computable numbering is defined as follows: \(\nu^e : = \lambda i,x. \varphi_e (\langle i,x \rangle)\), and let \(\nu^e\) enumerate the family of PRF \(F^{(e)} : = \{ \lambda x. \nu^e (i,x)\}_{e \in \omega}\). Denote by \(I(F)\) the set \(\{e : F^{(e)} = F\}\), and denote by \(R_1\) the family of total recursive functions.
The authors show:
If \(A\) is a non-recursive recursively enumerable set then \(\{\langle i,j \rangle : W_i \cap W_j = \emptyset\;\&\;W_i \cup W_j = A \cap W_i\;\&\;W_i\) is nonrecursive} is \(\Pi_3\)-complete.
The family \(\{e : F^{(e)} \subseteq R_1\) is effectively discrete} is \(\Sigma_3\)-complete.
The family \(\{e : F^{(e)} \subseteq R_1\) is discrete}, as well as the family \(\{e : F^{(e)} \subseteq R_1\) is discrete, but not effectively discrete} are both \(\Pi_3\)-complete.
The index set of any family \(F\) of total recursive functions which has exactly one (i.e. \(|L \{F\} |= 1)\) numbering up to numbering equivalence, is \(\Pi_4\)-complete.
The article contains a series of other results closely related to the above-mentioned ones. A number of open problem are listed.

03D20 Recursive functions and relations, subrecursive hierarchies
03D45 Theory of numerations, effectively presented structures
Full Text: DOI
[1] S. A. Badaev, ?Computable enumerations of families of general recursive functions,?Algebra Logika,16, No. 2, 129-148 (1977). · Zbl 0388.03018
[2] Yu. L. Ershov, ?Theorie der Numerierungen I,?Z. Math. Log. Grund. Math.,19, No. 4, 289-388 (1973). · Zbl 0295.02025
[3] Yu. L. Ershov,Theory of Numerations [in Russian], Nauka, Moscow (1977).
[4] R. V. Freivald, E. B. Kinber, and R. Wiehagen, ?Inductive inference and computable one-one numberings,?Z. Math. Log. Grund. Math.,28, No. 5, 463-479 (1982). · Zbl 0541.03025 · doi:10.1002/malq.19820282708
[5] S. S. Goncharov, ?Autostability of models and Abelian groups,?Algebra Logika,19, No. 1, 23-44 (1980).
[6] W. A. Howard and M. B. Pour-El, ?A structural criterion for recursive enumeration without repetition,?Z. Math. Log. Grund. Math.,10, No. 2, 105-114 (1964). · Zbl 0132.24703 · doi:10.1002/malq.19640100802
[7] A. B. Khutoretskii, ?On the cardinality of the upper semilattice of computable enumerations,?Algebra Logika,10, No. 5, 561-569 (1971).
[8] S. Lempp, ?Hyperarithmetical index sets in recursion theory,?Trans. Am. Math. Soc.,303, No. 2, 559-583 (1987). · Zbl 0652.03030 · doi:10.1090/S0002-9947-1987-0902785-2
[9] S. S. Marchenkov, ?The computable enumerations of families of recursive functions,?Algebra Logika,11, No. 5, 588-607 (1972).
[10] T. G. McLaughlin, ?The family of all recursively enumerable classes of finite sets,?Trans. Am. Math. Soc.,155, No. 1, 127-136 (1971). · Zbl 0221.02022 · doi:10.1090/S0002-9947-1971-0276084-7
[11] T. G. McLaughlin, ?Complete index sets of recursively enumerable families,?Comp. Math.,24, No. 1, 83-91 (1972). · Zbl 0306.02040
[12] V. L. Selivanov, ?Enumerations of families of general recursive functions,?Algebra Logika,15, No. 2, 205-226 (1976).
[13] V. L. Selivanov, Ph.D. Dissertation [unpublished], University of Kazan (1977).
[14] V. L. Selivanov, ?On index sets of classes of numberings,? in:Probability Methods and Cybernetics [in Russian], Vol. 14, Kazan (1978), pp. 90-103. · Zbl 0411.03037
[15] V. L. Selivanov, ?Some remarks about classes of recursively enumerable sets,?Sib. Mat. Zh.,19, No. 1, 153-160 (1978). · Zbl 0387.03013
[16] R. I. Soare,Recursively Enumerable Sets and Degrees, Springer-Verlag, Berlin (1987). · Zbl 0667.03030
[17] F. I. Validov, ?Recursively enumerable sets and discrete families of general recursive functions,?Izv. Vyssh. Uchebn. Zav., Ser. Mat., No.4, 6-11 (1984). · Zbl 0556.03037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.