Kurt Gödel Research Center

2011 seminar talk: Computably enumerable and co-computably enumerable equivalence structures

Talk held by Valentina Harizanov (George Washington University, Washington, D.C., USA) at the KGRC seminar on 2011-11-24.

Abstract

We investigate computability theoretic properties of computably enumerable and co-computably enumerable equivalence structures and their isomorphisms. While every computably enumerable equivalence structure with infinitely many infinite classes is isomorphic to a computable structure, there are computably enumerable equivalence structures that are not isomorphic to computable ones. We show that if two isomorphic computably enumerable equivalence structures have only finitely many infinite classes or have finite upper bound on the size of their finite classes, then they are limit computably isomorphic. On the other hand, we prove that even simple co-computably enumerable equivalence structures do not have to be limit computably isomorphic to computable structures.

This is joint work with D. Cenzer and J. Remmel.