Discrete Mathematics for Computer Science

192 CHAPTER 3 Relations

{0,1,2} {0,1,31 10,2,31 {1,2,31

{0} {1} {2) (3)

Figure 3.12 Odd subsets of {0, 1, 2, 3}.

Example 3.

(a) The relation < is a partial ordering on N. This follows from Example 6(a) in Section

3.4.2 and Example 8(c) in Section 3.4.3. By the same argument, > is a partial ordering

on N.

(b) The relation < is not a partial ordering, since it is transitive and antisymmetric but is

not reflexive. In fact, it is irreflexive. Irreflexive relations whose reflexive closures are

partial orderings are called strict partial orderings. So, < is a strict partial ordering.

(c) On any set X, the relation = is a partial ordering. This result follows from Example

4(a) in section 3.4.2 and Example 8(a) in Section 3.4.3. U

Example 4. Figure 3.13 shows a subset of the family tree given in Figure 3.2.

Elaine Maude

George Elizabeth

Figure 3.13 Subset of family tree.

Let R be the reflexive closure of the relation "ancestor of" as defined by this subset of the

family tree. Then, R is a partial ordering. The elements of the partial order are

{(Elaine, George), (Maude, Elizabeth), (Elaine, Elaine), (George, George),

(Maude, Maude), (Elizabeth, Elizabeth)) U

Example 5.

(a) Let

R={(x,y) :x,yENand y >xandy-xiseven)

Then, R is a partial ordering on N. (See Exercise 5 in Section 3.9.)

(b) Let I denote the relation divides on N. That is, x I y if, for some z e N, y = x • z.

Then, the relation I is a partial ordering on N.

As another, less familiar example of a partial order, we use the relation divides on the

set

{0, 1, 2, 3 ... , 11, 12}

to define a partial order by the relation x I y if and only if y = k • x for some integer k.

Figure 3.14 shows how these elements are related by I.