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 $\alpha$, the \emph{$\Delta^0_{\alpha}$ dimension} of a computable structure $\mathcal{S}$ is the number of computable copies of $\mathcal{S}$, up to $\Delta^0_{\alpha}$ computable isomorphism. The results of Goncharov, Harizanov, Knight, McCoy, Miller, Solomon, and Hirschfeldt, Khoussainov, Shore, Slinko imply that for every computable successor ordinal $\alpha$ and every non-zero natural number $n$, there exists a computable non-distributive lattice with $\Delta^0_{\alpha}$ dimension $n$. In this paper, we prove that for every computable successor ordinal $\alpha \geq 4$ and every natural number $n>0$, there is a computable distributive lattice with $\Delta^0_{\alpha}$ dimension $n$. For a computable successor ordinal $\alpha \geq 2$, we build a computable distributive lattice $\mathcal{M}$ such that the categoricity spectrum of $\mathcal{M}$ is equal to the set of all PA degrees over $\emptyset^{(\alpha)}$. We also obtain similar results for Heyting algebras