Equivalence Relations
187
D
C S
i
H
P
a
II e
a
I
a
b
d
o
ii
r
e
n
t
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 SameSuit. 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 i
2
i
I _ _ I--I
I- I
I I
I
4
4
__ 4
t
4.
51 1
~
5
T
5
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
J
A I
J
it K
K
K
K+_
-
_
.t
_
-I
_
[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