# Computable Isomorphisms of Distributive Lattices

Nikolay Bazhenov, Manat Mustafa, Mars Yamaleev

Research output: Chapter in Book/Report/Conference proceedingConference contribution

### Abstract

A standard tool for the classifying computability-theoretic complexity of equivalence relations is provided by computable reducibility. This gives rise to a rich degree-structure which has been extensively studied in the literature. In this paper, we show that equivalence relations, which are complete for computable reducibility in various levels of the hyperarithmetical hierarchy, arise in a natural way in computable structure theory. We prove that for any computable successor ordinal $\alpha$, the relation of $\Delta^0_{\alpha}$ isomorphism for computable distributive lattices is $\Sigma^0_{\alpha+2}$ complete. We obtain similar results for Heyting algebras, undirected graphs, and uniformly discrete metric spaces.
Language English Lecture Notes in Computer Science TAMC 2019 : Theory and Applications of Models of Computation Springer 1 13 11436 Published - Apr 13 2019

### Publication series

Name Lecture Notes in Computer Science

### Fingerprint

Distributive Lattice
Reducibility
Equivalence relation
Isomorphism
Computable Structure
Heyting Algebra
Computability
Undirected Graph
Metric space
Hierarchy
Standards

### Cite this

Bazhenov, N., Mustafa, M., & Yamaleev, M. (2019). Computable Isomorphisms of Distributive Lattices. In Lecture Notes in Computer Science: TAMC 2019 : Theory and Applications of Models of Computation (Vol. 11436 , pp. 1). (Lecture Notes in Computer Science). Springer.

Computable Isomorphisms of Distributive Lattices. / Bazhenov, Nikolay; Mustafa, Manat; Yamaleev, Mars.

Lecture Notes in Computer Science: TAMC 2019 : Theory and Applications of Models of Computation. Vol. 11436 Springer, 2019. p. 1 (Lecture Notes in Computer Science).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Bazhenov, N, Mustafa, M & Yamaleev, M 2019, Computable Isomorphisms of Distributive Lattices. in Lecture Notes in Computer Science: TAMC 2019 : Theory and Applications of Models of Computation. vol. 11436 , Lecture Notes in Computer Science, Springer, pp. 1.
Bazhenov N, Mustafa M, Yamaleev M. Computable Isomorphisms of Distributive Lattices. In Lecture Notes in Computer Science: TAMC 2019 : Theory and Applications of Models of Computation. Vol. 11436 . Springer. 2019. p. 1. (Lecture Notes in Computer Science).
Bazhenov, Nikolay ; Mustafa, Manat ; Yamaleev, Mars. / Computable Isomorphisms of Distributive Lattices. Lecture Notes in Computer Science: TAMC 2019 : Theory and Applications of Models of Computation. Vol. 11436 Springer, 2019. pp. 1 (Lecture Notes in Computer Science).
@inproceedings{aba442452b2146fe9a991a8d8fb579e9,
title = "Computable Isomorphisms of Distributive Lattices",
abstract = "A standard tool for the classifying computability-theoretic complexity of equivalence relations is provided by computable reducibility. This gives rise to a rich degree-structure which has been extensively studied in the literature. In this paper, we show that equivalence relations, which are complete for computable reducibility in various levels of the hyperarithmetical hierarchy, arise in a natural way in computable structure theory. We prove that for any computable successor ordinal $\alpha$, the relation of $\Delta^0_{\alpha}$ isomorphism for computable distributive lattices is $\Sigma^0_{\alpha+2}$ complete. We obtain similar results for Heyting algebras, undirected graphs, and uniformly discrete metric spaces.",
author = "Nikolay Bazhenov and Manat Mustafa and Mars Yamaleev",
year = "2019",
month = "4",
day = "13",
language = "English",
volume = "11436",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "1",
booktitle = "Lecture Notes in Computer Science",

}

TY - GEN

T1 - Computable Isomorphisms of Distributive Lattices

AU - Bazhenov, Nikolay

AU - Mustafa, Manat

AU - Yamaleev, Mars

PY - 2019/4/13

Y1 - 2019/4/13

N2 - A standard tool for the classifying computability-theoretic complexity of equivalence relations is provided by computable reducibility. This gives rise to a rich degree-structure which has been extensively studied in the literature. In this paper, we show that equivalence relations, which are complete for computable reducibility in various levels of the hyperarithmetical hierarchy, arise in a natural way in computable structure theory. We prove that for any computable successor ordinal $\alpha$, the relation of $\Delta^0_{\alpha}$ isomorphism for computable distributive lattices is $\Sigma^0_{\alpha+2}$ complete. We obtain similar results for Heyting algebras, undirected graphs, and uniformly discrete metric spaces.

AB - A standard tool for the classifying computability-theoretic complexity of equivalence relations is provided by computable reducibility. This gives rise to a rich degree-structure which has been extensively studied in the literature. In this paper, we show that equivalence relations, which are complete for computable reducibility in various levels of the hyperarithmetical hierarchy, arise in a natural way in computable structure theory. We prove that for any computable successor ordinal $\alpha$, the relation of $\Delta^0_{\alpha}$ isomorphism for computable distributive lattices is $\Sigma^0_{\alpha+2}$ complete. We obtain similar results for Heyting algebras, undirected graphs, and uniformly discrete metric spaces.

M3 - Conference contribution

VL - 11436

T3 - Lecture Notes in Computer Science

SP - 1

BT - Lecture Notes in Computer Science

PB - Springer

ER -