9.9. Product Orders 249
order for which every two different elements are comparable is called apath-total
order.
So<andare path-total orders onR. On the other hand, the subset relation is
notpath-total, since, for example, any two different finite sets of the same size will
be incomparable under. The prerequisite relation on Course 6 required subjects
is also not path-total because, for example, neither 8.01 nor 6.042 is a prerequisite
of the other.
The name path-total is based on the following
Lemma 9.8.2.For any finite, nonempty set of vertices from a path-total digraph,
there is a directed path going through exactly these vertices. In fact, if the digraph
is a DAG, the directed path is unique.
Lemma 9.8.2 is easy to prove by induction on the size of the set of vertices. The
proof is given in Problem 9.3.
9.9 Product Orders
Taking the product of two relations is a useful way to construct new relations from
old ones.
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 ç:
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 which 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.
It follows directly from the definitions that products preserve the properties of
transitivity, reflexivity, irreflexivity, and antisymmetry, as shown in Problem 9.23.
