Computable Boolean algebras
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, \textit{R. Downey} and \textit{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 \textit{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.
- Recursive and r.e. quotient Boolean algebras
- Computability of distributive lattices
- Coding and definability in computable structures
- \(\Delta_{2}^{0}\)-categoricity in Boolean algebras and linear orderings
- Degree spectra of structures
- Computable presentability of countable linear orders
- Decomposability and computability
- Computable linear orders and the ershov hierarchy
- Limitwise monotonic spectra and their generalizations
- Algorithmic relationships of relations \(S_{\mathcal{L}}^n\) on linear orders
- Punctual copies of algebraic structures
- Atomless Boolean algebras computable in polynomial time
- 2011 North American Annual Meeting of the Association for Symbolic Logic, University of California at Berkeley, Berkeley, CA, USA, March 24--27, 2011
- Rice sequences of relations
- Some Questions in Computable Mathematics
- On the n-back-and-forth types of Boolean algebras
- \(\text{Low}_5\) Boolean subalgebras and computable copies
- Boolean algebra approximations
- 2004 Summer Meeting of the Association for Symbolic Logic
- On the triple jump of the set of atoms of a Boolean algebra
- Notes on the Jump of a Structure
- Depth zero Boolean algebras
- Computability on linear orderings enriched with predicates
- scientific article; zbMATH DE number 1534579 (Why is no real title available?)
- scientific article; zbMATH DE number 2154086 (Why is no real title available?)
- scientific article; zbMATH DE number 1421070 (Why is no real title available?)
- On ^0_2-categoricity of Boolean algebras
- 2006 Summer Meeting of the Association for Symbolic Logic: Logic Colloquium '06
- TURING DEGREE SPECTRA OF DIFFERENTIALLY CLOSED FIELDS
- Computability of Polish spaces up to homeomorphism
- On the effective universality of mereological theories
- Computable Stone spaces
- Computable Heyting algebras with distinguished atoms and coatoms
- Separating notions in effective topology
- COMPUTABLY COMPACT METRIC SPACES
- Cuts of linear orders
- On a computable presentation of low linear orderings
- A non-computable c.e. closed subset of \([0, 1]\)
- The coding theorems for linear orders
- Degree spectra of homeomorphism type of compact Polish spaces
- Optimal syntactic definitions of back-and-forth types
- Computably categorical Boolean algebras enriched by ideals and atoms
- New degree spectra of Polish spaces
This page was built for publication: Computable Boolean algebras
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2710598)
