Effective categoricity for distributive lattices and Heyting algebras

Аннотация

We study complexity of isomorphisms between computable copies of lattices and Heyting algebras. For a computable ordinal α, the Δ_α⁰dimension of a computable structure S is the number of computable copies of S, up to Δ_α⁰ 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 Δ_α⁰ 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 Δ_α⁰ 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.