Abstract:

This paper contributes to the research program of Khoussainov and Kowalski who started systematic investigations of the following problem: how does expanding the language of Boolean algebras affect their computability-theoretic properties. Following the approach of Hirschfeldt, Khoussainov, Shore, and Slinko, we prove that the class of Boolean algebras with distinguished subalgebras and atoms is complete with respect to degree spectra of nontrivial structures, effective dimensions, expansion by constants, and degree spectra of relations.