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).