×

Computable Boolean algebras. (English) Zbl 0974.03041

Feiner first proved that there are \(\Delta^0_2\) Boolean algebras that do not have computable copies. Feiner’s construction actually proves that there are \(\Delta^0_2\) Boolean algebras that have no copy which is \(\text{low}_n\) for \(n\in\omega\). In contrast with the situation for linear orderings, R. Downey and C. G. Jockusch [Proc. Am. Math. Soc. 122, 871-880 (1994; Zbl 0820.03019)] showed that every low Boolean algebra has a computable copy, and this result was later extended to \(\text{low}_2\) by J. J. Thurber [Proc. Am. Math. Soc. 123, 3859-3866 (1995; Zbl 0840.03024)]. The conjecture is that every \(\text{low}_n\) Boolean algebra is isomorphic to a computable one. The authors verify this conjecture for \(n\leq 4\). Whilst this might seem scant progress, in fact the proof is significantly more complex than either of the predecessors and crucially depends on a strong generalization of the Remmel-Vaught theorem on the atom ideal. This paper makes the general question look even more difficult than first supposed.

MSC:

03D45 Theory of numerations, effectively presented structures
Full Text: DOI

References:

[1] Proceedings of the American Mathematical Society 123 pp 3859–3866– (1995) · Zbl 1258.13016
[2] Archive for Mathematical Logic 33 pp 121–129– (1994)
[3] Proceedings of the American Mathematical Society 122 pp 871–880– (1994) · Zbl 0805.90016
[4] Handbook of Boolean algebras III
[5] Hierarchies of Boolean algebras 35 pp 365–373– (1970)
[6] Recursive Boolean algebras with recursive atoms 46 pp 595–615– (1981)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.