Subrecursive Equivalence Relations and (non-)Closure Under Lattice Operations

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

The set of equivalence relations on any non-empty set is equipped with a natural order that makes it a complete lattice. The lattice structure only depends on the cardinality of the set, and thus the study of the lattice structure on any countably infinite set is (up to order-isomorphism) the same as studying the lattice of equivalence relations on the set of natural numbers. We investigate closure under the meet and join operations in the lattice of equivalence relations on the set of natural numbers. Among other results, we show that no set of co-r.e. equivalence relations that contains all logspace-decidable equivalence relations is a lattice.

Original languageEnglish
Title of host publicationConnecting with Computability - 17th Conference on Computability in Europe, CiE 2021, Proceedings
EditorsLiesbeth De Mol, Andreas Weiermann, Florin Manea, David Fernández-Duque
PublisherSpringer
Publication date2021
Pages363-372
ISBN (Print)9783030800482
DOIs
Publication statusPublished - 2021
Event17th Conference on Computability in Europe, CiE 2021 - Virtual, Online
Duration: 5 Jul 20219 Jul 2021

Conference

Conference17th Conference on Computability in Europe, CiE 2021
ByVirtual, Online
Periode05/07/202109/07/2021
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12813 LNCS
ISSN0302-9743

Bibliographical note

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

    Research areas

  • Equivalence relations, Lattice theory, Subrecursive sets

ID: 282747243