Degrees of Unsolvability 129 Proof. Each equivalence class [x] E is nonempty (because x [x] E ) and is a subset of U (because E U × U). The main thing that we must prove is that the collection of equivalence classes is disjoint, i.e., part (a) of the definition is met. So suppose that [x] E and [y] E have a common element t. Thus, xEt and yEt. But then xEy and by the lemma, [x] E = [y] E . U/E = {[x] E | x U} whose members are the equivalence classes. (The expression U/E is read "U modulo E.") This is a set of sets. We have the natural map (or canonical map) : U U/E defined by (x) = [x] E for x in U. Example 4 revisited: For congruence modulo 6 on the integers, the quotient set Z / consists of exactly six sets: For an equivalence relation E on a set U, we can define the quotient set