Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
Effective categoricity for distributive lattices and Heyting algebras. / Bazhenov, N. A.
в: Lobachevskii Journal of Mathematics, Том 38, № 4, 01.07.2017, стр. 600-614.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - Effective categoricity for distributive lattices and Heyting algebras
AU - Bazhenov, N. A.
PY - 2017/7/1
Y1 - 2017/7/1
N2 - We study complexity of isomorphisms between computable copies of lattices and Heyting algebras. For a computable ordinal α, the Δα 0dimension of a computable structure S is the number of computable copies of S, up to Δα 0 computable isomorphism. The results of Goncharov, Harizanov, Knight, McCoy, Miller, Solomon, and Hirschfeldt, Khoussainov, Shore, Slinko imply that for every computable successor ordinal α and every non-zero natural number n, there exists a computable non-distributive lattice with Δα 0 dimension n. In this paper, we prove that for every computable successor ordinal α ≥ 4 and every natural number n > 0, there is a computable distributive lattice with Δα 0 dimension n. For a computable successor ordinal α ≥ 2, we build a computable distributive lattice M such that the categoricity spectrum of M is equal to the set of all PA degrees over Ø(α). We also obtain similar results for Heyting algebras.
AB - We study complexity of isomorphisms between computable copies of lattices and Heyting algebras. For a computable ordinal α, the Δα 0dimension of a computable structure S is the number of computable copies of S, up to Δα 0 computable isomorphism. The results of Goncharov, Harizanov, Knight, McCoy, Miller, Solomon, and Hirschfeldt, Khoussainov, Shore, Slinko imply that for every computable successor ordinal α and every non-zero natural number n, there exists a computable non-distributive lattice with Δα 0 dimension n. In this paper, we prove that for every computable successor ordinal α ≥ 4 and every natural number n > 0, there is a computable distributive lattice with Δα 0 dimension n. For a computable successor ordinal α ≥ 2, we build a computable distributive lattice M such that the categoricity spectrum of M is equal to the set of all PA degrees over Ø(α). We also obtain similar results for Heyting algebras.
KW - categoricity spectrum
KW - computable categoricity
KW - computable dimension
KW - degree of categoricity
KW - Distributive lattice
KW - Heyting algebra
KW - FIELDS
KW - STABILITY
KW - COMPUTABLE CATEGORICITY
KW - DEGREE SPECTRA
KW - RECURSIVE STRUCTURES
KW - DIMENSIONS
KW - SYSTEMS
KW - MODEL-THEORY
KW - AUTOSTABILITY
UR - http://www.scopus.com/inward/record.url?scp=85024493948&partnerID=8YFLogxK
U2 - 10.1134/S1995080217040035
DO - 10.1134/S1995080217040035
M3 - Article
AN - SCOPUS:85024493948
VL - 38
SP - 600
EP - 614
JO - Lobachevskii Journal of Mathematics
JF - Lobachevskii Journal of Mathematics
SN - 1995-0802
IS - 4
ER -
ID: 10071517