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



Sibirsk. Mat. Zh.:
Year:
Volume:
Issue:
Page:
Find






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


Sibirsk. Mat. Zh., 2017, Volume 58, Number 6, Pages 1236–1251 (Mi smj2934)  

Computability of distributive lattices

N. A. Bazhenovab, A. N. Frolovc, I. Sh. Kalimullinc, A. G. Melnikovd

a Sobolev Institute of Mathematics, Novosibirsk, Russia
b Novosibirsk State University, Novosibirsk, Russia
c Kazan (Volga Region) Federal University, Kazan, Russia
d The Institute of Natural and Mathematical Sciences, Massey University, Massey, New Zealand

Abstract: The class of (not necessarily distributive) countable lattices is HKSS-universal, and it is also known that the class of countable linear orders is not universal with respect to degree spectra neither to computable categoricity. We investigate the intermediate class of distributive lattices and construct a distributive lattice with degree spectrum $\{\mathbf d\colon\mathbf d\neq\mathbf0\}$. It is not known whether a linear order with this property exists. We show that there is a computably categorical distributive lattice that is not relatively $\Delta^0_2$-categorical. It is well known that no linear order can have this property. The question of the universality of countable distributive lattices remains open.

Keywords: distributive lattice, computable structure, degree spectrum, computable categoricity.

Funding Agency Grant Number
Russian Foundation for Basic Research 16-31-60058-мол_а_дк
16-31-60077-мол_а_дк
15-41-02507
Ministry of Education and Science of the Russian Federation 1.451.2016/1.4
Marsden Fund of New Zealand
Massey University Early Career Research Fund
N. A. Bazhenov was supported by the Russian Foundation for Basic Research (Grant 16-31-60058-mol_a_dk). A. N. Frolov was supported by the Russian Foundation for Basic Research (Grant 16-31-60077-mol_a_dk). I. Sh. Kalimullin was supported by the Russian Foundation for Basic Research (Grant 15-41-02507) and the Ministry of Education and Science of the Russian Federation (Grant 1.451.2016/1.4). A. G. Melnikov was partially supported by the Marsden Fund of New Zealand and the Massey University Early Career Research Fund.


DOI: https://doi.org/10.17377/smzh.2017.58.605

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

English version:
Siberian Mathematical Journal, 2017, 58:6, 959–970

Bibliographic databases:

Document Type: Article
UDC: 510.5+512.565.2
MSC: 35R30
Received: 27.11.2016

Citation: N. A. Bazhenov, A. N. Frolov, I. Sh. Kalimullin, A. G. Melnikov, “Computability of distributive lattices”, Sibirsk. Mat. Zh., 58:6 (2017), 1236–1251; Siberian Math. J., 58:6 (2017), 959–970

Citation in format AMSBIB
\Bibitem{BazFroKal17}
\by N.~A.~Bazhenov, A.~N.~Frolov, I.~Sh.~Kalimullin, A.~G.~Melnikov
\paper Computability of distributive lattices
\jour Sibirsk. Mat. Zh.
\yr 2017
\vol 58
\issue 6
\pages 1236--1251
\mathnet{http://mi.mathnet.ru/smj2934}
\crossref{https://doi.org/10.17377/smzh.2017.58.605}
\elib{http://elibrary.ru/item.asp?id=30556271}
\transl
\jour Siberian Math. J.
\yr 2017
\vol 58
\issue 6
\pages 959--970
\crossref{https://doi.org/10.1134/S0037446617060052}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000425153500005}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85042141013}


Linking options:
  • http://mi.mathnet.ru/eng/smj2934
  • http://mi.mathnet.ru/eng/smj/v58/i6/p1236

    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
  • Сибирский математический журнал Siberian Mathematical Journal
    Number of views:
    This page:65
    Full text:6
    References:15
    First page:9

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