ON ISOMORPHISM CLASSES OF COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS

摘要

We examine how degrees of computably enumerable equivalence relations (ceers) under computable reduction break down into isomorphism classes. Two ceers are isomorphic if there is a computable permutation of omega which reduces one to the other. As a method of focusing on nontrivial differences in isomorphism classes, we give special attention to weakly precomplete ceers. For any degree, we consider the number of isomorphism types contained in the degree and the number of isomorphism types of weakly precomplete ceers contained in the degree. We show that the number of isomorphism types must be 1 or omega, and it is 1 if and only if the ceer is self-full and has no computable classes. On the other hand, we show that the number of isomorphism types of weakly precomplete ceers contained in the degree can be any member of [0, omega]. In fact, for any n is an element of [0, omega], there is a degree d and weakly precomplete ceers E-1, ..., E-n in d so that any ceer R in d is isomorphic to E-i circle plus D for some i <= n and D a ceer with domain either finite or omega comprised of finitely many computable classes. Thus, up to a trivial equivalence, the degree d splits into exactly n classes.