Discrete Mathematical Structures by Pearson

Ordered Sets and Lattices 8-13

8.7 DUAL OF A POSET

Let R be a partial order relation on a set A and let R

−1

be the inverse relation of R, then R

−1

is also

a partial order relation, defined by a R

−1

b if and only if b R a, for a, b ∈ A.

THEOREM 8.2 If (A, R) is a poset, then (A, R

−1

) is also a poset.

Proof:

(1) R

−1

is reflexive

Since R is reflexive, a R a, ∀a ⇒ a R

−1

a by dual property.

(2) R

−1

is antisymmetric

Let a R

−1

b and b R

−1

a, then we have to prove that a = b.

Now,

a R

−1

b ⇒ b R a and b R

−1

a ⇒ a R b.

But R is antisymmetric, a R b, b R a ⇒ a = b.

Thus, a R

−1

b and b R

−1

a ⇒ a = b, and hence R

−1

is antisymmetric.

(4) R

−1

is transitive

Let a R

−1

b and b R

−1

c

Now,

a R

−1

b ⇒ b R a, b R

−1

c ⇒ c R b

Further, c R b and b R a ⇒ c R a ⇒ a R

−1