Discrete Mathematics for Computer Science

Ordering Relations 193

8 12

(^4 6 10) \
2 3' 5 7 11

Figure 3.14 Divides for {0, 1,2,..., 121.

Example 6. Let X be a collection of finite sets taken from some universal set U. Let

R = {(U, V) :U, V e X and I U I < V ii

Then, R is reflexive and transitive, but it is not antisymmetric.

Solution. Observe that if U = {0, 1, 21, then

1 (0, 1)}1 R 1(1, 2}1

and

1{1, 211 R 1{0, 1}1

but

{0, 1} # {1,21

Therefore, R need not be antisymmetric. U

Example 7. Let X be a collection of finite sets. Let

R = {(U, V) :U, V E X and (I U IV I or U = V)}

The relation R with X = P (Q0, 1, 2)) is shown in Figure 3.15. The lines between levels in
the figure represent the fact that the two sets are related. R is a partial ordering.

(0, 1,2)

(0, 1) 10, 2) f1, 21

101 (21

Figure 3.15 RonP({0, 1,21).