Degree Spectra of Relations on Boolean Algebras

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

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.