Page 640 - Discrete Mathematics and Its Applications

9.6 Partial Orderings 619

Solution: Because a ≥ a for every integer a, ≥ is reflexive. If a ≥ b and b ≥ a, then a = b.
Hence, ≥ is antisymmetric. Finally, ≥ is transitive because a ≥ b and b ≥ c imply that a ≥ c.
It follows that ≥ is a partial ordering on the set of integers and (Z, ≥) is a poset. ▲
EXAMPLE 2 The divisibility relation | is a partial ordering on the set of positive integers, because it is
+
reflexive, antisymmetric, and transitive, as was shown in Section 9.1. We see that (Z , |)isa
poset. Recall that (Z denotes the set of positive integers.) ▲
+
EXAMPLE 3 Show that the inclusion relation ⊆ is a partial ordering on the power set of a set S.

Solution: Because A ⊆ A whenever A is a subset of S, ⊆ is reflexive. It is antisymmetric because
A ⊆ B and B ⊆ A imply that A = B. Finally, ⊆ is transitive, because A ⊆ B and B ⊆ C imply
that A ⊆ C. Hence, ⊆ is a partial ordering on P(S), and (P (S), ⊆) is a poset. ▲

Example 4 illustrates a relation that is not a partial ordering.
EXAMPLE 4 Let R be the relation on the set of people such that xRy if x and y are people and x is older
than y. Show that R is not a partial ordering.

Solution: Note that R is antisymmetric because if a person x is older than a person y, then y
is not older than x. That is, if xRy, then y R x. The relation R is transitive because if person x
is older than person y and y is older than person z, then x is older than z. That is, if xRy
and yRz, then xRz. However, R is not reflexive, because no person is older than himself or
herself. That is, x R x for all people x. It follows that R is not a partial ordering. ▲
In different posets different symbols such as ≤, ⊆, and |, are used for a partial ordering.
However, we need a symbol that we can use when we discuss the ordering relation in an
arbitrary poset. Customarily, the notation a b is used to denote that (a, b) ∈ R in an arbitrary
poset (S, R). This notation is used because the “less than or equal to” relation on the set of real
numbers is the most familiar example of a partial ordering and the symbol is similar to the ≤
symbol. (Note that the symbol is used to denote the relation in any poset, not just the “less
than or equals” relation.) The notation a ≺ b denotes that a b,but a = b. Also, we say “a is
less than b”or“b is greater than a”if a ≺ b.
When a and b are elements of the poset (S, ), it is not necessary that either a b
or b a. For instance, in (P (Z), ⊆), {1, 2} is not related to {1, 3}, and vice versa, because
+
neither set is contained within the other. Similarly, in (Z , |), 2 is not related to 3 and 3 is not
related to 2, because 2 | 3 and 3 | 2. This leads to Definition 2.

DEFINITION 2 The elements a and b of a poset (S, ) are called comparable if either a b or b a. When
a and b are elements of S such that neither a b nor b a, a and b are called incomparable.

EXAMPLE 5 In the poset (Z , |), are the integers 3 and 9 comparable? Are 5 and 7 comparable?
+
Solution: The integers 3 and 9 are comparable, because 3 | 9. The integers 5 and 7 are incom-
parable, because 5 | 7 and 7 | 5. ▲

The adjective “partial” is used to describe partial orderings because pairs of elements may
be incomparable. When every two elements in the set are comparable, the relation is called a
total ordering.

DEFINITION 3 If (S, ) is a poset and every two elements of S are comparable, S is called a totally ordered
or linearly ordered set, and is called a total order or a linear order. A totally ordered set
is also called a chain.