338
Relations, Functions, and Matrices
Two elements of S may be unrelated in a partial ordering of S. In Example 10,
516 and 526 are unrelated; so are 2 and 3, and 12 and 18 in Practice 9. In Figure 5.3,
f is not related to any other element. A partial ordering in which every element of
the set is related to every other element is called a total ordering, or chain. The
Hasse diagram for a total ordering on a four-element set looks like Figure 5.4.
The relation ≤ on N is a total ordering, although we can’t draw a Hasse diagram
because N is an infinite set.
Figure 5.4
…
…
Again, let (S, d) be a partially ordered set. If there is a y [ S with y d x for
all x [ S, then y is a least element of the partially ordered set. A least element,
if it exists, is unique. To show its uniqueness, assume that y and z are both least
elements. Then y d z because y is least and z d y because z is least; by antisymmetry, y = z. An element y [ S is minimal if there is no x [ S with x a y
. In the Hasse diagram, a least element is below all others, while a minimal
element has no elements below it. Similar definitions apply for greatest element
and maximal elements.
PRaCtiCe 10 Define greatest element and maximal element in a partially ordered set (S, d).
■
example 11
In the partially ordered set of Practice 9, 1 is both least and minimal; 12 and 18 are
both maximal, but there is no greatest element.
A least element is always minimal and a greatest element is always maximal,
but the converses are not true (see Example 11). In a totally ordered set, however,
a minimal element is the least element and a maximal element is the greatest
element.
PRaCtiCe 11 Draw the Hasse diagram for a partially ordered set with four elements in which there are
two minimal elements but no least element, two maximal elements but no greatest element,
and each element is related to exactly two other elements.
■
Partial orderings satisfy the properties of reflexivity, antisymmetry, and transitivity. Another type of binary relation, which we study next, satisfies a different
set of properties.
Relations, Functions, and Matrices
Two elements of S may be unrelated in a partial ordering of S. In Example 10,
516 and 526 are unrelated; so are 2 and 3, and 12 and 18 in Practice 9. In Figure 5.3,
f is not related to any other element. A partial ordering in which every element of
the set is related to every other element is called a total ordering, or chain. The
Hasse diagram for a total ordering on a four-element set looks like Figure 5.4.
The relation ≤ on N is a total ordering, although we can’t draw a Hasse diagram
because N is an infinite set.
Figure 5.4
…
…
Again, let (S, d) be a partially ordered set. If there is a y [ S with y d x for
all x [ S, then y is a least element of the partially ordered set. A least element,
if it exists, is unique. To show its uniqueness, assume that y and z are both least
elements. Then y d z because y is least and z d y because z is least; by antisymmetry, y = z. An element y [ S is minimal if there is no x [ S with x a y
. In the Hasse diagram, a least element is below all others, while a minimal
element has no elements below it. Similar definitions apply for greatest element
and maximal elements.
PRaCtiCe 10 Define greatest element and maximal element in a partially ordered set (S, d).
■
example 11
In the partially ordered set of Practice 9, 1 is both least and minimal; 12 and 18 are
both maximal, but there is no greatest element.
A least element is always minimal and a greatest element is always maximal,
but the converses are not true (see Example 11). In a totally ordered set, however,
a minimal element is the least element and a maximal element is the greatest
element.
PRaCtiCe 11 Draw the Hasse diagram for a partially ordered set with four elements in which there are
two minimal elements but no least element, two maximal elements but no greatest element,
and each element is related to exactly two other elements.
■
Partial orderings satisfy the properties of reflexivity, antisymmetry, and transitivity. Another type of binary relation, which we study next, satisfies a different
set of properties.