Degree Spectra of Relations on Boolean Algebras
Status: published in Algebra and Logic, vol. 42 (2003), pp. 105 -
111.
Availability: DVI, PostScript, and PDF
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