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
![](/img/style/loading.gif)