Page 643 - Discrete Mathematics and Its Applications

622 9 / Relations

EXAMPLE 10 Note that (1, 2, 3, 5) ≺ (1, 2, 4, 3), because the entries in the first two positions of these 4-tuples
agree, but in the third position the entry in the first 4-tuple, 3, is less than that in the second
4-tuple, 4. (Here the ordering on 4-tuples is the lexicographic ordering that comes from the
usual “less than or equals” relation on the set of integers.) ▲

We can now define lexicographic ordering of strings. Consider the strings a 1 a 2 ...a m and
b 1 b 2 ...b n on a partially ordered set S. Suppose these strings are not equal. Let t be the minimum
of m and n. The definition of lexicographic ordering is that the string a 1 a 2 ...a m is less than
b 1 b 2 ...b n if and only if
(a 1 ,a 2 ,..., a t ) ≺ (b 1 ,b 2 ,..., b t ), or
(a 1 ,a 2 ,..., a t ) = (b 1 ,b 2 ,..., b t ) and m<n,

t
where ≺ in this inequality represents the lexicographic ordering of S . In other words, to de-
termine the ordering of two different strings, the longer string is truncated to the length of the
shorter string, namely, to t = min(m, n) terms. Then the t-tuples made up of the first t terms of
t
each string are compared using the lexicographic ordering on S . One string is less than another
string if the t-tuple corresponding to the first string is less than the t-tuple of the second string,
or if these two t-tuples are the same, but the second string is longer. The verification that this is
a partial ordering is left as Exercise 38 for the reader.
EXAMPLE 11 Consider the set of strings of lowercase English letters. Using the ordering of letters in the
alphabet, a lexicographic ordering on the set of strings can be constructed. A string is less than
a second string if the letter in the first string in the first position where the strings differ comes
before the letter in the second string in this position, or if the first string and the second string
agree in all positions, but the second string has more letters. This ordering is the same as that
used in dictionaries. For example,
discreet ≺ discrete,

because these strings differ first in the seventh position, and e ≺ t. Also,
discreet ≺ discreetness,

because the first eight letters agree, but the second string is longer. Furthermore,
discrete ≺ discretion,

because

discrete ≺ discreti.
▲
Hasse Diagrams

Many edges in the directed graph for a finite poset do not have to be shown because they must be
present. For instance, consider the directed graph for the partial ordering {(a, b) | a ≤ b} on the
set {1, 2, 3, 4}, shown in Figure 2(a). Because this relation is a partial ordering, it is reflexive,
and its directed graph has loops at all vertices. Consequently, we do not have to show these loops
because they must be present; in Figure 2(b) loops are not shown. Because a partial ordering is
transitive, we do not have to show those edges that must be present because of transitivity. For
example, in Figure 2(c) the edges (1, 3), (1, 4), and (2, 4) are not shown because they must be
present. If we assume that all edges are pointed “upward” (as they are drawn in the figure), we
do not have to show the directions of the edges; Figure 2(c) does not show directions.
In general, we can represent a finite poset (S, ) using this procedure: Start with the
directed graph for this relation. Because a partial ordering is reflexive, a loop (a, a) is present at
every vertex a. Remove these loops. Next, remove all edges that must be in the partial ordering
because of the presence of other edges and transitivity. That is, remove all edges (x, y) for
which there is an element z ∈ S such that x ≺ z and z ≺ x. Finally, arrange each edge so that