EN|RU
English version:
Journal of Applied and Industrial Mathematics, 2016, 10:3, 380-385

Volume 23, No 3, 2016, P. 81-92

UDC 519.716
S. S. Marchenkov
On maximal subalgebras of the algebras of unary recursive functions

Abstract:
We consider the algebras of unary functions with supports in countable primitively recursively closed classes and composition operation. Each algebra of this type is proved to have continuum many maximal subalgebras including the set of all unary functions of the class $\mathscr{E}^{2}$ of the Grzegorczyk hierarchy.
Bibliogr. 13.

Keywords: maximal subalgebra, unary recursive function.

DOI: 10.17377/daio.2016.23.518

Sergei S. Marchenkov 1
1. Moscow State University,
1 Leninskie gory, 119991 Moscow, Russia
e-mail: ssmarchen@yandex.ru

Revised 26 April 2016

# References

[1] S. A. Berezin, An algebra of unate primitive recursive functions with iteration operation of general form, Kibern., No. 3, 12–19, 1976. Translated in Cybern., 12, No. 3, 346–353, 1976.

[2] S. A. Berezin, Maximal subalgebras of recursive function algebras, Kibern., No. 6, 123–125, 1978. Translated in Cybern., 14, No. 6, 935–938, 1978.

[3] G. P. Gavrilov, On functional completeness in a countable-valued logic, in A. A. Lyapunov, ed., Problemy kibernetiki (Problems of Cybernetics), Vol. 15, pp. 5–64, Nauka, Moscow, 1965.

[4] A. Grzegorczyk, Some classes of recursive functions, in Rozprawy Matematyczne (Mathematical Apparatus), Vol. 4, Pol. Tow. Mat., Warsaw, 1953. Translated in Problemy matematicheskoi logiki (Problems of Mathematical Logic), pp. 9–49, Mir, Moscow, 1970.

[5] V. V. Koz’minykh, On primitive recursive functions of a single argument, Algebra Logika, 7, No. 1, 75–90, 1968. Translated in Algebra Logic, 7, No. 1, 44–53, 1968.

[6] S. S. Marchenkov, A method for constructing maximal subalgebras of algebras of general recursive functions, Algebra Logika, 17, No. 5, 581–595, 1978. Translated in Algebra Logic, 17, No. 5, 383–392, 1978.

[7] S. S. Marchenkov, On cardinality of the set of precomplete classes in some classes of a countable-valued logic, in S. V. Yablonskii, ed., Problemy kibernetiki (Problems of Cybernetics), Vol. 38, pp. 109–116, Nauka, Moscow, 1981.

[8] S. S. Marchenkov, Elementarnye rekursivnye funktsii (Elementary Recursive Functions), MTsNMO, Moscow, 2003.

[9] S. S. Marchenkov, Funktsional’nye sistemy s operatsiei superpozitsii (Functional Systems with Superposition Operation), FIZMATLIT, Moscow, 2004.

[10] V. L. Mikheev, Class of algebras of primitive recursive functions, Mat. Zametki, 14, No. 1, 143–156, 1973. Translated in Math. Notes Acad. Sci. USSR, 14, No. 1, 638–645, 1981.

[11] R. W. Ritchie, Classes of predictably computable functions, Trans. Amer. Math. Soc., 106, No. 1, 139–173, 1963. Translated in Problemy matematicheskoi logiki (Problems of Mathematical Logic), pp. 50–93, Mir, Moscow, 1970.

[12] M. G. Rozinas, An algebra of many-placed primitive recursive functions, in Uchenye zapiski Ivanovskogo gosudarstvennogo pedagogicheskogo instituta (Scientific Notes of Ivanovo State Pedagogical Institute), Vol. 117, pp. 95–111, ISPI, Ivanovo, 1972.

[13] V. A. Sokolov, Maximal subalgebras of the algebra of all partially recursive functions, Kibern., No. 1, 70–73, 1972. Translated in Cybern., 8, No. 1, 76–79, 1972.
© Sobolev Institute of Mathematics, 2015