236 RELATIONS: EQUIVALENCE RELATIONS AND PARTIAL ORDERINGS Chapter 7
(b) Recall the relation R,, from Example 6, Article 7.1. Two subsets
of a finite set X are related by R17 if and only if they have the same
number of elements. R,, is an equivalence relation on A = 9(X).
(c) Define a relation R2, on the set S of all students in Math 197
in the fall semester by R2, = ((x, y)lx and y achieve the same numerical
grade on Test # 1). R2, is an equivalence relation on S. ClWe now proceed to the formal definition of equivalence relation on a set
A. Our definition uses terminology introduced in Definition 3, Article 7.1.
DEFINITION 1
Let A be a set and E a relation on A. We say that E is an equivalence relation
on A if and only if E is reflexive on A, symmetric, and transitive. (RST)The most basic example of an equivalence relation on any set A is equal-
it^; that is, E = ((x, y) 1 x = y), also denoted I, = ((x, x) 1 x E A). To show
that equality is an equivalence relation, we note that the reflexive property
requires simply that every element of A equal itself, a true statement. Sym-
metry states that if x = y, then y = x for any x, y E A, again true. Transi-
tivity means that if x = y and y = z, then x = z for any elements x, y, and
z of A, which is also true.
At the other extreme, the whole cartesian product A x A is an equiva-
lence relation on any set A (verify!). It is not a very useful one, however,
since any two elements of A are related by it; certainly we will not often
want to view all elements of a set A as indistinguishable from one another!
Returning to Example 1 and considering, for instance, part (b), we note
that R17 is reflexive, since every subset of X surely has the same number
of elements as itself. It is symmetric since if X and Y have the same number
of elements, so do Y and X. It is transitive since if X and Y have the same
number of elements, as do Y and Z, then certainly X and Z have the same
number of elements. You should carry out similar verifications for parts
(a) and (c).
For examples of relations that are not equivalence relations, you may
refer to many of the examples R, through R2, in Article 7.1. Among these,
only R,, R,, R, ,, R14, R1 ,, R19, R,,, R2,, and R2, are equivalence relations.
A relation fails to be an equivalence relation as soon as it fails to possess
one of the three defining properties. The relation < on Z (i-e., the example
z) is reflexive on Z and transitive, but it is not symmetric (verify!), and
so is not an equivalence relation on Z.
EXAMPLE 2 Show that the relation E on A = R - (0) defined by E =
((x, y) 1 xy > 0} is an equivalence relation on A, whereas the relation N =
{(x, y) 1 xy < 0} satisfies only symmetry.