Computability in the Lattice of Equivalence Relations
Jean-Yves Moyen, Jakob Grue Simonsen · Electronic Proceedings in Theoretical Computer Science · 2017
We investigate computability in the lattice of equivalence relations on the natural numbers. We mostly investigate whether the subsets of appropriately defined subrecursive equivalence relations -for example the set of all polynomial-time decidable equivalence relations- form sublattices of the lattice.