Geodesic
Degree Spectra of Relations on Boolean Algebras
Algebra i logika, Tome 42 (2003) no. 2, pp. 182-193

Voir la notice de l'article provenant de la source Math-Net.Ru

We show that every computable relation on a computable Boolean algebra $\mathfrak B$ is either definable by a quantifier-free formula with constants from $\mathfrak B$ (in which case it is obviously intrinsically computable) or has infinite degree spectrum.
Keywords: computable Boolean algebra, computable relation, intrinsically computable relation. 
@article{AL_2003_42_2_a2,
     author = {S. S. Goncharov and R. Downey and D. Hirschfeldt},
     title = {Degree {Spectra} of {Relations} on {Boolean} {Algebras}},
     journal = {Algebra i logika},
     pages = {182--193},
     publisher = {mathdoc},
     volume = {42},
     number = {2},
     year = {2003},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2003_42_2_a2/}
}
TY  - JOUR
AU  - S. S. Goncharov
AU  - R. Downey
AU  - D. Hirschfeldt
TI  - Degree Spectra of Relations on Boolean Algebras
JO  - Algebra i logika
PY  - 2003
SP  - 182
EP  - 193
VL  - 42
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2003_42_2_a2/
LA  - ru
ID  - AL_2003_42_2_a2
ER  - 
%0 Journal Article
%A S. S. Goncharov
%A R. Downey
%A D. Hirschfeldt
%T Degree Spectra of Relations on Boolean Algebras
%J Algebra i logika
%D 2003
%P 182-193
%V 42
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2003_42_2_a2/
%G ru
%F AL_2003_42_2_a2
S. S. Goncharov; R. Downey; D. Hirschfeldt. Degree Spectra of Relations on Boolean Algebras. Algebra i logika, Tome 42 (2003) no. 2, pp. 182-193. http://geodesic.mathdoc.fr/item/AL_2003_42_2_a2/