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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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

This article is cited in 9 scientific papers (total in 9 papers)

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
Received: 21.11.2000

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}


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

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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  mathnet  crossref  mathscinet  zmath  isi
    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  crossref  mathscinet  zmath  isi  scopus
    3. Harizanov V.S., Miller R.G., “Spectra of structures and relations”, Journal of Symbolic Logic, 72:1 (2007), 324–348  crossref  mathscinet  zmath  isi  scopus
    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  crossref  mathscinet  isi  scopus
    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  crossref  mathscinet  zmath  isi  scopus
    6. P. E. Alaev, “Computable ideals in $I$-algebras”, Algebra and Logic, 49:2 (2010), 103–114  mathnet  crossref  mathscinet  zmath  isi
    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  crossref  mathscinet  zmath  isi  scopus
    8. Csima B.F., Harizanov V.S., Miller R., Montalban A., “Computability of Fraisse Limits”, J Symbolic Logic, 76:1 (2011), 66–93  crossref  mathscinet  zmath  adsnasa  isi  elib  scopus
    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  mathscinet  isi
  • Алгебра и логика Algebra and Logic
    Number of views:
    This page:229
    Full text:63
    References:39
    First page:1

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2018