Mathematics for Computer Science

Chapter 9 Directed graphs & Partial Orders248

So

1! f 1 g

3! f1;3g

4! f1;4g

6! f1;3;6g

8! f1;4;8g

12! f1;3;4;6;12g

So, the fact that 3 j 12 corresponds to the fact thatf1;3gf1;3;4;6;12g.

In this way we have completely captured the weak partial orderby the subset

relation on the corresponding sets. Formally, we have

Lemma 9.7.2.Letbe a weak partial order on a set,A. Thenis isomorphic to

the subset relation,, on the collection of inverse images under therelation of

elementsa 2 A.

We leave the proof to Problem 9.14. Essentially the same construction shows

that strict partial orders can be represented by sets under the proper subset relation,

. To summarize

Theorem 9.7.3.Every weak partial order,, is isomorphic to the subset relation,

, on a collection of sets.

Every strict partial order,, is isomorphic to the proper subset relation,, on a

collection of sets.

9.8 Path-Total Orders

The familiar order relations on numbers have an important additional property:

given two different numbers, one will be bigger than the other. Partial orders with

this property are said to bepath-total orders.^7

Definition 9.8.1.LetRbe a binary relation on a set,A, and leta;bbe elements of

A. Thenaandbarecomparablewith respect toRiffŒa R b ORb R aç. A partial

(^7) Path-total partial orders are conventionally just called “total.” But this terminology conflicts with
the definition of “total relation,” and it regularly confuses students. So we chose the terminology
“path-total” to avoid the confusion.
Being a path-total partial order is a much stronger condition than being a partial order that is a
total relation. For example, any weak partial order such asis a total relation but generally won’t be
path-total.