How to approximate fuzzy sets: mind-changes and the Ershov Hierarchy.

Computability theorists have introduced multiple hierarchies to measure the complexity of sets of natural numbers. The Kleene Hierarchy classifies sets according to the first-order complexity of their defining formulas. The Ershov Hierarchy classifies limit computable sets with respect to the number of mistakes that are needed to approximate them.

Classifying equivalence relations in the Ershov hierarchy.

Computably enumerable equivalence relations (ceers) received a lot of attention in the literature. The standard tool to classify ceers is provided by the computable reducibility . This gives rise to a rich degree structure.