RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
 General information Latest issue Archive Impact factor Subscription Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Algebra Logika: Year: Volume: Issue: Page: Find

 Algebra Logika, 2003, Volume 42, Number 2, Pages 182–193 (Mi al24)

Degree Spectra of Relations on Boolean Algebras

S. S. Goncharova, R. Downeyb, D. Hirschfeldtc

a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
b Victoria University of Wellington, School of Mathematics, Statistics and Computer Science
c University of Chicago

Abstract: 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.

Full text: PDF file (180 kB)
References: PDF file   HTML file

English version:
Algebra and Logic, 2003, 42:2, 105–111

Bibliographic databases:

UDC: 510.5+512.563

Citation: S. S. Goncharov, R. Downey, D. Hirschfeldt, “Degree Spectra of Relations on Boolean Algebras”, Algebra Logika, 42:2 (2003), 182–193; Algebra and Logic, 42:2 (2003), 105–111

Citation in format AMSBIB
\Bibitem{GonDowHir03} \by S.~S.~Goncharov, R.~Downey, D.~Hirschfeldt \paper Degree Spectra of Relations on Boolean Algebras \jour Algebra Logika \yr 2003 \vol 42 \issue 2 \pages 182--193 \mathnet{http://mi.mathnet.ru/al24} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=2003628} \zmath{https://zbmath.org/?q=an:1034.03043} \transl \jour Algebra and Logic \yr 2003 \vol 42 \issue 2 \pages 105--111 \crossref{https://doi.org/10.1023/A:1023350306979} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-23844505474} 

• http://mi.mathnet.ru/eng/al24
• http://mi.mathnet.ru/eng/al/v42/i2/p182

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. P. M. Semukhin, “The degree spectra of definable relations on Boolean algebras”, Siberian Math. J., 46:4 (2005), 740–750
2. Chisholm J., Chubb J., Harizanov V.S., Hirschfeldt D.R., Jockusch Carl G. Jr., Mcnicholl T., Pingrey S., “Pi(0)(1) classes and strong degree spectra of relations”, Journal of Symbolic Logic, 72:3 (2007), 1003–1018
3. Harizanov V.S., Miller R.G., “Spectra of structures and relations”, Journal of Symbolic Logic, 72:1 (2007), 324–348
4. Cenzer D., Harizanov V., Marker D., Wood C., “Special Issue: The workshop on Model Theory and Computable Model Theory, 2007 Preface”, Archive For Mathematical Logic, 48:1 (2009), 1–6
5. Chubb J., Frolov A., Harizanov V., “Degree spectra of the successor relation of computable linear orderings”, Archive For Mathematical Logic, 48:1 (2009), 7–13
6. P. E. Alaev, “Computable ideals in $I$-algebras”, Algebra and Logic, 49:2 (2010), 103–114
7. Downey R., Lempp S., Wu G., “On the Complexity of the Successivity Relation in Computable Linear Orderings”, Journal of Mathematical Logic, 10:1–2 (2010), 83–99
8. Csima B.F., Harizanov V.S., Miller R., Montalban A., “Computability of Fraisse Limits”, J Symbolic Logic, 76:1 (2011), 66–93
9. Fokina E.B. Harizanov V. Melnikov A., “Computable Model Theory”, Turing'S Legacy: Developments From Turing'S Ideas in Logic, Lecture Notes in Logic, 42, ed. Downey R., Cambridge Univ Press, 2014, 124–194
•  Number of views: This page: 238 Full text: 63 References: 39 First page: 1