×

zbMATH — the first resource for mathematics

On maximal subalgebras of the algebras of unary recursive functions. (Russian, English) Zbl 1374.03027
Diskretn. Anal. Issled. Oper. 23, No. 3, 81-92 (2016); translation in J. Appl. Ind. Math. 10, No. 3, 380-385 (2016).
Summary: Under consideration are 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 \(\mathcal{E}^2\) of the Grzegorczyk hierarchy.

MSC:
03D20 Recursive functions and relations, subrecursive hierarchies
03D55 Hierarchies of computability and definability
08A30 Subalgebras, congruence relations
08A60 Unary algebras
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Berezin, S. A., An algebra of unate primitive recursive functions with iteration operation of general form, Kibernet., 3, 12-19, (1976)
[2] Berezin, S. A., Maximal subalgebras of recursive function algebras, Kibernet., 6, 123-125, (1978) · Zbl 0437.03017
[3] Gavrilov, G. P.; Lyapunov, A. A. (ed.), On functional completeness in a countable-valued logic, (1965), Moscow
[4] Grzegorczyk, A., Some classes of recursive functions, (1970) · Zbl 0224.02029
[5] Koz’minykh, V. V., On primitive recursive functions of a single argument, Algebra Logika, 7, 75-90, (1968)
[6] Marchenkov, S. S., A method for constructing maximal subalgebras of algebras of general recursive functions, Algebra Logika, 17, 581-595, (1978) · Zbl 0431.03029
[7] Marchenkov, S. S.; Yablonskii, S. V. (ed.), On cardinality of the set of precomplete classes in someclasses of a countable-valued logic, (1981), Moscow
[8] S. S. Marchenkov, Elementary Recursive Functions (MTsNMO, Moscow, 2003) [in Russian].
[9] S. S. Marchenkov, Function Systems with Superposition Operation (Fizmatlit, Moscow, 2004) [in Russian]. · Zbl 1143.03012
[10] Mikheev, V. L., Class of algebras of primitive recursive functions, Mat. Zametki, 14, 143-156, (1973)
[11] Ritchie, R. W., Classes of predictably computable functions, Trans. Amer. Math. Soc., 106, 139-173, (1963) · Zbl 0107.01001
[12] Rozinas, M. G., An algebra ofmany-placed primitive recursive functions, Uchen. Zapiski Ivanovsk. Gos. Pedagog. Inst., 117, 95-111, (1972)
[13] Sokolov, V. A., Maximal subalgebras of the algebra of all partially recursive functions, Kibernet., 1, 70-73, (1972)
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.