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/

[1] Handbook of recursive mathematics, Stud. Logic Found. Math., 138–139, ed. Yu. L. Ershov et al, Elsevier Science B.V., Amsterdam, 1998

[2] R. I. Soare, Recursively enumerable sets and degrees, Perspect. Math. Logic, Springer-Verlag, Heidelberg, 1987 | MR

[3] W. Hodges, Model theory, Encycl. Math. Appl., 42, Cambridge University Press, Cambridge, 1993 | MR | Zbl

[4] S. S. Goncharov, Schetnye bulevy algebry i razreshimost, Sibirskaya shkola algebry i logiki, Nauchnaya kniga (NII MIOO NGU), Novosibirsk, 1996 | MR

[5] C. J. Ash, A. Nerode, “Intrinsically recursive relations”, Aspects of effective algebra, Proc. conf. (1979), ed. J. N. Crossley, Monash Univ., Clayton, Aust., 1981, 26–41 | MR | Zbl

[6] M. Moses, “Relations intrinsically recursive in linear orders”, Z. Math. Logik Grundlagen Math., 32:5 (1986), 467–472 | DOI | MR | Zbl

[7] V. S. Harizanov, Degree spectrum of a recursive relation on a recursive structure, PhD Thesis, University of Wisconsin, Madison, WI, 1987

[8] J. B. Remmel, “Recursive isomorphism types of recursive Boolean algebras”, J. Symb. Log., 46:3 (1981), 572–594 | DOI | MR | Zbl

[9] D. R. Hirschfeldt, B. Khoussainov, R. A. Shore, A. M. Slinko, “Degree spectra and computable dimension in algebraic structures”, Ann. Pure Appl. Logic, 115:1–3 (2002), 71–113 | DOI | MR | Zbl

[10] V. S. Harizanov, “The possible Turing degree of the nonzero member in a two element degree spectrum”, Ann. Pure Appl. Logic, 60:1 (1993), 1–30 | DOI | MR | Zbl

[11] D. R. Hirschfeldt, “Degree spectra of relations on computable structures in the presence of $\Delta^0_2$ isomorphisms”, J. Symb. Log., 67:2 (2002), 697–720 | DOI | MR | Zbl

[12] M. Moses, “Recursive linear orderings with recursive successivities”, Ann. Pure Appl. Logic, 27:3 (1984), 253–264 | DOI | MR | Zbl

[13] S. B. Cooper, L. Harrington, A. H. Lachlan, S. Lempp, R. I. Soare, “The d.r.e. degrees are not dense”, Ann. Pure Appl. Logic, 55:2 (1991), 125–151 | DOI | MR | Zbl

[14] R. G. Downey, M. F. Moses, “Recursive linear orders with incomplete successivities”, Trans. Am. Math. Soc., 326 (1991), 653–668 | DOI | MR | Zbl