Effective categoricity for distributive lattices and Heyting algebras
- Authors: Bazhenov N.A.1,2
-
Affiliations:
- Sobolev Institute of Mathematics
- Novosibirsk State University
- Issue: Vol 38, No 4 (2017)
- Pages: 600-614
- Section: Article
- URL: https://journals.rcsi.science/1995-0802/article/view/199557
- DOI: https://doi.org/10.1134/S1995080217040035
- ID: 199557
Cite item
Abstract
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.
About the authors
N. A. Bazhenov
Sobolev Institute of Mathematics; Novosibirsk State University
Author for correspondence.
Email: bazhenov@math.nsc.ru
Russian Federation, pr. Akademika Koptyuga 4, Novosibirsk, 630090; ul. Pirogova 2, Novosibirsk, 630090