Equivalence Relations 187
D
C P S a i II He
a I a
b d e o n ii rt
s s d s
S
I I
Figure 3.9 Equivalence classes of SameSuit (dashed lines) and SameColor (solid lines).
In the previous example, SameSuit refines SameColor. Also, SameSuit refines Same-
Suit. Now, consider the relation SameValue, which is defined as consisting of all pairs of
cards with the same value. The equivalence class of the 2 of Diamonds is
12 of Diamonds, 2 of Clubs, 2 of Hearts, 2 of Spades)
This equivalence relation is shown in Figure 3.10 as a set of disjoint equivalence classes.
Clubs Diamonds Hearts Spades
I z I z•z I I .II I
2 2 2 i i
I _ _ I--I I- I I I I
4 4 __ 4 t 4.
51 ~ 1 5 5 T
I __ I I_ I: I_ II I /
6 6 I 6 I 6 I 6
I K i • K [ +1K i ir
[17 7 7 417
S S Sit SameValue
[t ___ 9 9 i 9 1
FT 1u 10 1a 10 1uit 10 1
1±J iJ A J I J
it K - K .t K -I K+
[1A jIA A A
SameSuit
Figure 3.10 Equivalence classes SameSuit (vertical) and Same Value (horizontal).
The equivalence relation of the 2 of Diamonds under SameValue is not a subset of the
equivalence class of the 2 of Diamonds under SameSuit. Hence, SameValue does not refine
SameSuit. Also, SameSuit does not refine SameValue.
Theorem 4. Let R, and R 2 be equivalence relations on the same set X. R1 refines R 2 if
and only if each equivalence class of R 2 is a union of equivalence classes of R 1.
Proof This proof is left as an exercise for the reader. U
