Computable Heyting Algebras with Distinguished Atoms and Coatoms

The paper studies Heyting algebras within the framework of computable structure theory. We prove that the class K containing all Heyting algebras with distinguished atoms and coatoms is complete in the sense of the work of Hirschfeldt et al. (Ann Pure Appl Logic 115(1-3):71-113, 2002). This shows that the class K is rich from the computability-theoretic point of view: for example, every possible degree spectrum can be realized by a countable structure from K. In addition, there is no simple syntactic characterization of computably categorical members of K (i.e., structures from K possessing a unique computable copy, up to computable isomorphisms).