Subrecursive Equivalence Relations and (non-)Closure Under Lattice Operations
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-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 language | English |
---|---|
Title of host publication | Connecting with Computability - 17th Conference on Computability in Europe, CiE 2021, Proceedings |
Editors | Liesbeth De Mol, Andreas Weiermann, Florin Manea, David Fernández-Duque |
Publisher | Springer |
Publication date | 2021 |
Pages | 363-372 |
ISBN (Print) | 9783030800482 |
DOIs | |
Publication status | Published - 2021 |
Event | 17th Conference on Computability in Europe, CiE 2021 - Virtual, Online Duration: 5 Jul 2021 → 9 Jul 2021 |
Conference
Conference | 17th Conference on Computability in Europe, CiE 2021 |
---|---|
By | Virtual, Online |
Periode | 05/07/2021 → 09/07/2021 |
Series | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 12813 LNCS |
ISSN | 0302-9743 |
Bibliographical note
Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
- Equivalence relations, Lattice theory, Subrecursive sets
Research areas
ID: 282747243