TY - JOUR

T1 - Computability of Distributive Lattices

AU - Bazhenov, N. A.

AU - Frolov, A. N.

AU - Kalimullin, I. Sh

AU - Melnikov, A. G.

PY - 2017/11/1

Y1 - 2017/11/1

N2 - 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 {d: d ≠ 0}. 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 Δ2 0-categorical. It is well known that no linear order can have this property. The question of the universality of countable distributive lattices remains open.

AB - 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 {d: d ≠ 0}. 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 Δ2 0-categorical. It is well known that no linear order can have this property. The question of the universality of countable distributive lattices remains open.

KW - computable categoricity

KW - computable structure

KW - degree spectrum

KW - distributive lattice

KW - EFFECTIVE CATEGORICITY

KW - DEGREE SPECTRA

UR - http://www.scopus.com/inward/record.url?scp=85042141013&partnerID=8YFLogxK

U2 - 10.1134/S0037446617060052

DO - 10.1134/S0037446617060052

M3 - Article

AN - SCOPUS:85042141013

VL - 58

SP - 959

EP - 970

JO - Siberian Mathematical Journal

JF - Siberian Mathematical Journal

SN - 0037-4466

IS - 6

ER -