An example on existence of a 02n-computable family of total functions whose rogers semilattice contains an ideal without minimal elements
45 53
Keywords:
n-computable numbering, 02n-computable family, computability relative to the oracle )1(0n, minimal numbering, Rogers semilattice, numerical equivalence, positive equivalence, ideal.Abstract
We study computable families of total functions of any level of the Kleene-Mostowski hierarchy above level 1 and try to find elementary properties of the Rogers semilattices that are different from the properties of the classical Rogers semilattices for families of computable functions. It is known that on first level of the arithmetical hierarchy the Rogers semilattice of any computable family of total functions contains no ideal without minimal elements, [1]. In this article we show an example how to build 02n-computable family of total functions whose Rogers semilattice contains an ideal without minimal elements, n.References
1. Ershov Yu.L. Theory of numberings. Nauka, Moscow, – 1977,- P416(in Russian).
2. Mal’tsev A.I. Algorithms and recursive functions. – M.: Nauka, – 1965. – P. 367 (in Russian).
3. Rogers H. Theory of recursive functions and effective computability. McGraw-Hill. – New York, 1967. – P. 482.
4. Goncharov S.S., Sorbi A. Generalized computable numerations and non-trivial Rogers semilattices. Algebra and logic, vol. 36, no. 6, –
1997. – P. 621-641.
5. Badaev S.A., Goncharov S.S. Rogers semilattices of families of arithmetic sets. Algebra and logic, vol. 40, no. 5, – 2001. – P.283-291.
6. Badaev S.A., Goncharov S.S., Sorbi A. Elementary theories for Rogers semilattices. Algebra and logic, vol. 44, no. 3, – 2005. – P.143- 147.
7. Badaev S.A. On minimal enumerations, Siberian Adv. Math., vol. 2, no. 1, – 1992. – P.1-30.
8. Badaev S.A., Goncharov S.S. On computable minimal enumerations. Alg., proc. third int. conf. algebra mem. M.I. Kargapolov, Walter de
Gruyter. – New-York, 1995. – P.21-32.
9. Badaev S.A. A problem of S.S. Goncharov. Siberian mathematical journal, vol. 32, no. 3, – 1991. – P.532-534.
10. Badaev S.A., Goncharov S.S. Theory of numberings: open problems. In Computability theory and its applications, Cont. math., vol. 257, –
2000. – P. 23-38.
2. Mal’tsev A.I. Algorithms and recursive functions. – M.: Nauka, – 1965. – P. 367 (in Russian).
3. Rogers H. Theory of recursive functions and effective computability. McGraw-Hill. – New York, 1967. – P. 482.
4. Goncharov S.S., Sorbi A. Generalized computable numerations and non-trivial Rogers semilattices. Algebra and logic, vol. 36, no. 6, –
1997. – P. 621-641.
5. Badaev S.A., Goncharov S.S. Rogers semilattices of families of arithmetic sets. Algebra and logic, vol. 40, no. 5, – 2001. – P.283-291.
6. Badaev S.A., Goncharov S.S., Sorbi A. Elementary theories for Rogers semilattices. Algebra and logic, vol. 44, no. 3, – 2005. – P.143- 147.
7. Badaev S.A. On minimal enumerations, Siberian Adv. Math., vol. 2, no. 1, – 1992. – P.1-30.
8. Badaev S.A., Goncharov S.S. On computable minimal enumerations. Alg., proc. third int. conf. algebra mem. M.I. Kargapolov, Walter de
Gruyter. – New-York, 1995. – P.21-32.
9. Badaev S.A. A problem of S.S. Goncharov. Siberian mathematical journal, vol. 32, no. 3, – 1991. – P.532-534.
10. Badaev S.A., Goncharov S.S. Theory of numberings: open problems. In Computability theory and its applications, Cont. math., vol. 257, –
2000. – P. 23-38.
Downloads
How to Cite
Issakhov, A. A. (2015). An example on existence of a 02n-computable family of total functions whose rogers semilattice contains an ideal without minimal elements. International Journal of Mathematics and Physics, 6(1), 30–32. Retrieved from https://ijmph.kaznu.kz/index.php/kaznu/article/view/114
Issue
Section
Astronomy and Space Research
