### 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 α, the relation of (formula presented) isomorphism for computable distributive lattices is (formula presented) complete. We obtain similar results for Heyting algebras, undirected graphs, and uniformly discrete metric spaces.

Original language | English |
---|---|

Title of host publication | Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings |

Editors | T. V. Gopal, Junzo Watada |

Publisher | Springer Verlag |

Pages | 28-41 |

Number of pages | 14 |

ISBN (Print) | 9783030148119 |

DOIs | |

Publication status | Published - Jan 1 2019 |

Event | 15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019 - Kitakyushu, Japan Duration: Apr 13 2019 → Apr 16 2019 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 11436 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019 |
---|---|

Country | Japan |

City | Kitakyushu |

Period | 4/13/19 → 4/16/19 |

### Fingerprint

### Keywords

- Computable categoricity
- Computable metric space
- Computable reducibility
- Distributive lattice
- Equivalence relation
- Heyting algebra

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings*(pp. 28-41). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11436 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-14812-6_3