×

zbMATH — the first resource for mathematics

Degree spectra of relations on Boolean algebras. (Russian, English) Zbl 1034.03043
Algebra Logika 42, No. 2, 182-193 (2003); translation in Algebra Logic 42, No. 2, 105-111 (2003).
The main result reads as follows: Let \(R\) be a computable relation on a computable Boolean algebra \(B\). Then \(R\) is either definable by a quantifier-free formula with constants, or the set of Turing degrees of its isomorphic images in isomorphic computable copies of \(B\) is infinite.

MSC:
03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures
PDF BibTeX XML Cite