Computably Enumerable Equivalence Relations
colorful horizontal rule

Su Gao and Peter Gerdes

Abstract

We study computably enumerable equivalence relations (ceers) on N and unravel a rich structural theory for a strong notion of reducibility among ceers.

Table of Contents

  1. Introduction
  2. Indices for Ceers
  3. Computable Equivalence Relations and Partial Classifiability
  4. Finite Dimensional Ceers
  5. FC Relations and CC Relations
  6. Bounded Relations
  7. The Saturation Jump Operator
  8. The Halting Jump Operator
  9. Incomparability between the Jump Operators
  10. Open Problems
    References
This paper was published in Studia Logica 67 (2001), no. 1, 27-59.

Back to Su Gao's Homepage