×

Computability of distributive lattices. (English. Russian original) Zbl 1469.03121

Sib. Math. J. 58, No. 6, 959-970 (2017); translation from Sib. Mat. Zh. 58, No. 6, 1236-1251 (2017).
Summary: 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}: \mathbf{d}\neq \mathbf{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 \(\Delta_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.

MSC:

03D45 Theory of numerations, effectively presented structures
03C57 Computable structure theory, computable model theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Knight J. F. and Stob M., “Computable Boolean algebras,” J. Symb. Log., vol. 65, no. 4, 1605-1623 (2000). · Zbl 0974.03041 · doi:10.2307/2695066
[2] Melnikov A. G., “New degree spectra of abelian groups,” Notre Dame J. Form. Log., vol. 58, no. 4, 507-525 (2017). · Zbl 1423.03152 · doi:10.1215/00294527-2017-0006
[3] Hirschfeldt D. R., Khoussainov B., Shore R. A., and Slinko A. M., “Degree spectra and computable dimensions in algebraic structures,” Ann. Pure Appl. Logic, vol. 115, no. 1-3, 71-113 (2002). · Zbl 1016.03034 · doi:10.1016/S0168-0072(01)00087-2
[4] Fokina, E. B.; Friedman, S.-D., Equivalence relations on classes of computable structures, 198-207 (2009), Berlin · Zbl 1268.03039 · doi:10.1007/978-3-642-03073-4_21
[5] Harrison-Trainor M., Melnikov A., Miller R., and Montalbán A., “Computable functors and effective interpretability,” J. Symb. Log., vol. 82, no. 1, 77-97 (2017). · Zbl 1390.03034 · doi:10.1017/jsl.2016.12
[6] Montalbán, A., Computability theoretic classifications for classes of structures (2014) · Zbl 1373.03069
[7] Downey, R. G., Computability theory and linear orderings (1998), Amsterdam · Zbl 0941.03045
[8] Frolov A., Harizanov V., Kalimullin I., Kudinov O., and Miller R., “Spectra of highn and non-lown degrees,” J. Log. Comput., vol. 22, no. 4, 755-777 (2012). · Zbl 1260.03068 · doi:10.1093/logcom/exq041
[9] Richter L. J., “Degrees of structures,” J. Symb. Log., vol. 46, no. 4, 723-731 (1981). · Zbl 0512.03024 · doi:10.2307/2273222
[10] Miller R., “The Δ20-spectrum of a linear order,” J. Symb. Log., vol. 66, no. 2, 470-486 (2001). · Zbl 0992.03050 · doi:10.2307/2695025
[11] Goncharov S. S. and Dzgoev V. D., “Autostability of models,” Algebra and Logic, vol. 19, no. 1, 28-37 (1980). · Zbl 0468.03023 · doi:10.1007/BF01669102
[12] Remmel J. B., “Recursively categorical linear orderings,” Proc. Amer. Math. Soc., vol. 83, no. 2, 387-391 (1981). · Zbl 0493.03022 · doi:10.1090/S0002-9939-1981-0624937-1
[13] Ash C. J., “Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees,” Trans. Amer. Math. Soc., vol. 298, no. 2, 497-514 (1986). · Zbl 0631.03017 · doi:10.1090/S0002-9947-1986-0860377-7
[14] McCoy C. F. D., “Δ20-Categoricity in Boolean algebras and linear orderings,” Ann. Pure Appl. Logic, vol. 119, no. 1-3, 85-120 (2003). · Zbl 1016.03036 · doi:10.1016/S0168-0072(02)00035-0
[15] McCoy Ch. F. D., “Partial results in Δ30-categoricity in linear orderings and Boolean algebras,” Algebra and Logic, vol. 41, no. 5, 295-305 (2002). · Zbl 1008.03023 · doi:10.1023/A:1020927703492
[16] Frolov A. N., “Effective categoricity of computable linear orderings,” Algebra and Logic, vol. 54, no. 5, 415-417 (2015). · Zbl 1361.03044 · doi:10.1007/s10469-015-9362-5
[17] Selivanov V. L., “Algorithmic complexity of algebraic systems,” Math. Notes, vol. 44, no. 6, 944-950 (1988). · Zbl 0675.03026 · doi:10.1007/BF01158034
[18] Turlington A., Computability of Heyting Algebras and Distributive Lattices, Ph. D. Thesis, Univ. of Connecticut (2010).
[19] Bazhenov N. A., “Effective categoricity for distributive lattices and Heyting algebras,” Lobachevskii J. Math., vol. 38, no. 4, 600-614 (2017). · Zbl 1420.03070 · doi:10.1134/S1995080217040035
[20] Wehner S., “Enumerations, countable structures and Turing degrees,” Proc. Amer. Math. Soc., vol. 126, no. 7, 2131-2139 (1998). · Zbl 0906.03044 · doi:10.1090/S0002-9939-98-04314-7
[21] Knight J. F., “Degrees coded in jumps of orderings,” J. Symb. Log., vol. 51, no. 4, 1034-1042 (1986). · Zbl 0633.03038 · doi:10.2307/2273915
[22] Slaman T. A., “Relative to any nonrecursive set,” Proc. Amer. Math. Soc., vol. 126, no. 7, 2117-2122 (1998). · Zbl 0894.03017 · doi:10.1090/S0002-9939-98-04307-X
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.