Standard

Effective categoricity for distributive lattices and Heyting algebras. / Bazhenov, N. A.

In: Lobachevskii Journal of Mathematics, Vol. 38, No. 4, 01.07.2017, p. 600-614.

Research output: Contribution to journal › Article › peer-review

Harvard

Bazhenov, NA 2017, 'Effective categoricity for distributive lattices and Heyting algebras', Lobachevskii Journal of Mathematics, vol. 38, no. 4, pp. 600-614. https://doi.org/10.1134/S1995080217040035

APA

Bazhenov, N. A. (2017). Effective categoricity for distributive lattices and Heyting algebras. Lobachevskii Journal of Mathematics, 38(4), 600-614. https://doi.org/10.1134/S1995080217040035

Vancouver

Bazhenov NA. Effective categoricity for distributive lattices and Heyting algebras. Lobachevskii Journal of Mathematics. 2017 Jul 1;38(4):600-614. doi: 10.1134/S1995080217040035

Author

Bazhenov, N. A. / Effective categoricity for distributive lattices and Heyting algebras. In: Lobachevskii Journal of Mathematics. 2017 ; Vol. 38, No. 4. pp. 600-614.

BibTeX

@article{b3310bd59b4c4ecabb75e0365cfd184f,
title = "Effective categoricity for distributive lattices and Heyting algebras",
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 {\O}(α). We also obtain similar results for Heyting algebras.",
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",
author = "Bazhenov, {N. A.}",
year = "2017",
month = jul,
day = "1",
doi = "10.1134/S1995080217040035",
language = "English",
volume = "38",
pages = "600--614",
journal = "Lobachevskii Journal of Mathematics",
issn = "1995-0802",
publisher = "Maik Nauka Publishing / Springer SBM",
number = "4",

}

RIS

TY - JOUR

T1 - Effective categoricity for distributive lattices and Heyting algebras

AU - Bazhenov, N. A.

PY - 2017/7/1

Y1 - 2017/7/1

N2 - 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.

AB - 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.

KW - categoricity spectrum

KW - computable categoricity

KW - computable dimension

KW - degree of categoricity

KW - Distributive lattice

KW - Heyting algebra

KW - FIELDS

KW - STABILITY

KW - COMPUTABLE CATEGORICITY

KW - DEGREE SPECTRA

KW - RECURSIVE STRUCTURES

KW - DIMENSIONS

KW - SYSTEMS

KW - MODEL-THEORY

KW - AUTOSTABILITY

UR - http://www.scopus.com/inward/record.url?scp=85024493948&partnerID=8YFLogxK

U2 - 10.1134/S1995080217040035

DO - 10.1134/S1995080217040035

M3 - Article

AN - SCOPUS:85024493948

VL - 38

SP - 600

EP - 614

JO - Lobachevskii Journal of Mathematics

JF - Lobachevskii Journal of Mathematics

SN - 1995-0802

IS - 4

ER -

ID: 10071517