Effective categoricity for distributive lattices and Heyting algebras

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)600-614
Number of pages15
JournalLobachevskii Journal of Mathematics
Volume38
Issue number4
DOIs
Publication statusPublished - 1 Jul 2017

Keywords

  • categoricity spectrum
  • computable categoricity
  • computable dimension
  • degree of categoricity
  • Distributive lattice
  • Heyting algebra
  • FIELDS
  • STABILITY
  • COMPUTABLE CATEGORICITY
  • DEGREE SPECTRA
  • RECURSIVE STRUCTURES
  • DIMENSIONS
  • SYSTEMS
  • MODEL-THEORY
  • AUTOSTABILITY

Fingerprint

Dive into the research topics of 'Effective categoricity for distributive lattices and Heyting algebras'. Together they form a unique fingerprint.

Cite this