zbMATH — the first resource for mathematics

Recursive isomorphism types of recursive Boolean algebras. (English) Zbl 0543.03031
A Boolean algebra is said to be recursive if its universe is a recursive set of natural numbers and its join, meet, and complementation operations are partial recursive functions. It is easily seen that the set of atoms of a recursive Boolean algebra is co-r.e. as a set of natural numbers. In the paper under review, the recursion-theoretic properties of the set of atoms (and the ideal it generates) are investigated for the class of recursive Boolean algebras isomorphic to any given recursive Boolean algebra. A sample result (Theorem 2.3) is that every recursive Boolean algebra with infinitely many atoms is isomorphic to a recursive Boolean algebra in which the set of atoms is immune. In fact, by Theorem 2.10 the result just mentioned holds with ”hyperimmune and Turing complete” in place of ”immune”. In the other direction it is shown in Theorem 3.1 that there is exactly one possible isomorphism type for recursive Boolean algebras with a cohesive set of atoms. The results developed yield a new proof of the result of P. La Roche and S. S. Goncharov that a recursive Boolean algebra has the property that its (classical) isomorphism type consists of a single recursive isomorphism type if and only if the Boolean algebra has only finitely many atoms. The proofs involve finite injury priority arguments combined with algebraic information developed in the paper. \(\{\) According to the author, he has shown since the submission of this paper that every recursive Boolean algebra is isomorphic to a recursive Boolean algebra in which the set of atoms is Turing incomplete. Erratum: In Theorem 1.1, the Boolean algebras \({\mathcal B}_ 1\) and \({\mathcal B}_ 2\) should be assumed to have only finitely many atoms.\(\}\)

03D45 Theory of numerations, effectively presented structures
06E99 Boolean algebras (Boolean rings)
03D50 Recursive equivalence types of sets and structures, isols
PDF BibTeX Cite
Full Text: DOI
[1] Boolean algebras (1964)
[2] Combinatorial functors (1969)
[3] Theory of recursive functions and effective computability (1967) · Zbl 0183.01401
[4] Recursive Boolean algebras with recursive atoms 46 pp 595– (1981) · Zbl 0543.03032
[5] Annals of Mathematical Logic 14 pp 75– (1978)
[6] DOI: 10.1002/malq.19660120125 · Zbl 0181.30504
[7] DOI: 10.2140/pjm.1978.76.169 · Zbl 0393.03033
[8] Fundament a Mathe-maticae 59 pp 109– (1966)
[9] Notices of the American Mathematical Society 24 pp A– (1977)
[10] DOI: 10.1007/BF02219296 · Zbl 0288.02022
[11] Sibirskiǐ Matematičeskiǐ Žurnal 16 pp 264– (1975)
[12] Algebra i Logika 12 pp 31– (1973)
[13] DOI: 10.1002/malq.19770231902 · Zbl 0374.02028
[14] University of California Publications in Mathematics 3 (1960)
[15] DOI: 10.2307/1970393 · Zbl 0135.00702
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.