Degree Spectra of Relations on Boolean Algebras

by Rod G. Downey, Sergey S. Goncharov, and Denis R. Hirschfeldt



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