About Journal 
Editorial Board
Publishing Ethics
Author Guide 
Submission
Prepare Your Manuscript
Peer review
Archive
Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
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
Received 3 December 2015
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.
