9.10. Equivalence Relations 341
Definition 9.9.1.The product,R 1 R 2 , of relationsR 1 andR 2 is defined to be
the relation with
domain.R 1 R 2 / WWD domain.R 1 /domain.R 2 /;
codomain.R 1 R 2 / WWD codomain.R 1 /codomain.R 2 /;
.a 1 ;a 2 /.R 1 R 2 /.b 1 ;b 2 / iff Œa 1 R 1 b 1 anda 2 R 2 b 2 ç:
It follows directly from the definitions that products preserve the properties of
transitivity, reflexivity, irreflexivity, and antisymmetry (see Problem 9.41). IfR 1
andR 2 both have one of these properties, then so doesR 1 R 2. This implies that
ifR 1 andR 2 are both partial orders, then so isR 1 R 2.
Example9.9.2. Define a relation,Y, on age-height pairs of being youngerand
shorter. This is the relation on the set of pairs.y;h/whereyis a nonnegative
integer 2400 that we interpret as an age in months, andhis a nonnegative integer
120 describing height in inches. We defineYby the rule
.y 1 ;h 1 /Y .y 2 ;h 2 / iff y 1 y 2 ANDh 1 h 2 :
That is,Y is the product of the-relation on ages and the-relation on heights.
Since both ages and heights are ordered numerically, the age-height relationYis
a partial order. Now suppose we have a class of 101 students. Then we can apply
Dilworth’s lemma 9.5.12 to conclude that there is a chain of 11 students—that is,
11 students who get taller as they get older–or an antichain of 11 students—that is,
11 students who get taller as they get younger, which makes for an amusing in-class
demo.
On the other hand, the property of being a linear order is not preserved. For
example, the age-height relationYis the product of two linear orders, but it is not
linear: the age 240 months, height 68 inches pair, (240,68), and the pair (228,72)
are incomparable underY.
9.10 Equivalence Relations
Definition 9.10.1.A relation is anequivalence relationif it is reflexive, symmetric,
and transitive.
Congruence modulonis an important example of an equivalence relation:
It is reflexive becausexx .modn/.
