zbMATH — the first resource for mathematics

Universal recursively enumerable Boolean algebras. (English. Russian original) Zbl 0552.03026
Sib. Math. J. 24, 852-858 (1983); translation from Sib. Mat. Zh. 24, No. 6(142), 36-43 (1983).
Let \({\mathfrak K}\) be a class of r.e. Boolean algebras. A r.e. Boolean algebra \({\mathfrak A}_{\nu}\) is called universal in the class \({\mathfrak K}\), if \({\mathfrak A}_{\nu}\in {\mathfrak K}\) and for each r.e. Boolean algebra \({\mathfrak B}_{\mu}\in {\mathfrak K}\) there exists a r.e. Boolean algebra \({\mathfrak C}_{\pi}\) such that \({\mathfrak B}_{\mu}\times {\mathfrak C}_{\pi}\) and \({\mathfrak A}_{\nu}\) are recursively isomorphic. Let B denote the class of atomless r.e. Boolean algebras, A be the class of atomic r.e. Boolean algebras and \(A_ r\) be the class of atomic recursive Boolean algebras. The author studies the question of existence of universal r.e. Boolean algebras for the classes B, A, \(A_ r\) and proves the following theorems: Theorem 1. There is no universal r.e. Boolean algebra in the class B of atomless r.e. Boolean algebras. Theorem 2. For each atomic r.e. Boolean algebra (\({\mathfrak A},\mu)\) there exists a recursive atomic Boolean algebra which is not a direct summand in (\({\mathfrak A},\mu)\). Corollary 1. The class \(A_ r\) has no universal recursive Boolean algebra. Corollary 2. The class A has no universal r.e. Boolean algebra.
03D45 Theory of numerations, effectively presented structures
06E99 Boolean algebras (Boolean rings)
Full Text: DOI
[1] Yu. L. Ershov, Theory of Numerations [in Russian], 3, Novosibirsk Univ. Press (1974).
[2] R. Sikorski, Boolean Algebras [Russian translation], Mir, Moscow (1970).
[3] H. Rogers, The Theory of Recursive Functions and Effective Computability [Russian translation], Mir, Moscow (1972).
[4] M. G. Peretyat’kin, ?Strongly constructive models and numerations of the Boolean algebra of recursive sets,? Algebra Logika,10, No. 5, 535-557 (1971).
[5] S. S. Goncharov, ?Some properties of constructivizations of Boolean algebras,? Sib. Mat. Zh.,16, No. 2, 264-278 (1975).
[6] S. S. Goncharov, ?Nonautoequivalent constructivizations of atomic Boolean algebras,? Mat. Zametki,19, No. 6, 853-858 (1976).
[7] A. T. Nurtazin, ?Computable classes and algebraic criteria of autostability,? Candidate’s Dissertation, Mathematics Institute, Siberian Branch, Academy of Sciences of the USSR, Novosibirsk (1974).
[8] W. Hanf, ?Characterization of B?2?,? Preprint, University of Hawaii, Honolulu (1979).
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.