Effective categoricity for distributive lattices and Heyting algebras
- Авторы: Bazhenov N.1,2
-
Учреждения:
- Sobolev Institute of Mathematics
- Novosibirsk State University
- Выпуск: Том 38, № 4 (2017)
- Страницы: 600-614
- Раздел: Article
- URL: https://journals.rcsi.science/1995-0802/article/view/199557
- DOI: https://doi.org/10.1134/S1995080217040035
- ID: 199557
Цитировать
Аннотация
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.
Об авторах
N. Bazhenov
Sobolev Institute of Mathematics; Novosibirsk State University
Автор, ответственный за переписку.
Email: bazhenov@math.nsc.ru
Россия, pr. Akademika Koptyuga 4, Novosibirsk, 630090; ul. Pirogova 2, Novosibirsk, 630090