Discrete Mathematics for Computer Science

Ordering Relations 191

Ordering Relations

In this section, we discuss two very important classes of relations, the partial orderings and

the linear orderings. Partial orderings generalize the relation is a subset of (g), and linear

orderings generalize the relation less than (<).

3.8.1 Partial Orderings

A typical example of a partial order, other than IsASubsetOf is the relation IsADescen-

dantOf The fact that this latter relation is a partial order contributes to the difficulty in

completing a person's genealogy. One of the difficulties involved in tracing a genealogy is

that a line of descendants often dies out, and the search then has to find another branch of

the family. The end of a line of descendants will be special elements in a partial order.

Definition 1. Let R be a binary relation on a nonempty set X. R is a partial ordering if

R is a reflexive, transitive, antisymmetric relation.

The following are standard examples of partial orderings.

Example 1. If U is a set, then C is a partial ordering on the subsets of U. This was proved

in Example 6(b) in Section 3.4.2 and in Example 8(e) in Section 3.4.3.

Example 2. In Figure 3.11, there is a representation of the eight subsets of

U = {0, 1, 2}

Each subset is obviously a subset of itself, so the relation is reflexive. The lines going

upward indicate the rest of the subset relation. Since there is a line from (1} to (0, 1}, {1}

is shown to be a subset of (0, 11. Since there is a line from 0 to {1} and another from {1} to

(0, 11, 0 is shown to be a subset of {0, 1 }. (Thus, reflexivity, antisymmetry, and transitivity

are all assumed in the way the drawing is interpreted.)

10,1,21

10,11 10,21 11,21

Figure 3.11 Subsets of {0, 1, 2}.

Figure 3.12 pictures the eight subsets of (0, 1, 2, 31 having an odd number of elements.
These elements also form a partial order with respect to the relation _ .By the same
argument, D is also a partial ordering on any set of sets. You just need to turn the picture
upside down to reverse the direction-that is, {0, 1, 2) Q (01.