Degree Spectra of Relations on Boolean Algebras
Status: published in Algebra
and Logic 42 (2003) 105 - 111.
Availability: journal
version and preprint
Abstract. We show that every computable relation on a
computable Boolean algebra B is either definable by a
quantifier-free formula with constants from B (in which case it
is obviously intrinsically computable) or has infinite degree
spectrum.
drh@math.uchicago.edu