Section 5.1 Relations
351
b. If (S, r) is a finite, partially ordered set with the Hasse diagram shown, draw the diagram of the dual of
(S, r).
c. Let (S, r) be a totally ordered set and let X = 5(x, x) 0 x [ S6. Show that the setdifference r
−1
− X
equals the set r′.
41. A computer program is to be written that will generate a dictionary or the index for a book. We will
assume a maximum length of n characters per word. Thus, we are given a set S of words of length at most
n, and we want to produce a linear list of these words arranged in alphabetical order. There is a natural
total ordering d on alphabetic characters (a a b, b a c, etc.), and we will assume our words contain
only alphabetic characters. We want to define a total ordering d on S called a lexicographical ordering
that will arrange the members of S alphabetically. The idea is to compare two words X and Y character by
character, passing over equal characters. If at any point the X character alphabetically precedes the corresponding Y character, then X precedes Y; if all characters in X are equal to the corresponding Y characters
but we run out of characters in X before characters in Y, then X precedes Y. Otherwise, Y precedes X.
Formally, let X = (x 1 , x 2 , … , x j ) and Y = (y 1 , y 2 , … , y k ) be members of S with j ≤ k. Let b (for
blank) be a new symbol, and fill out X with k − j blanks on the right. X can now be written (x 1 , x 2 , …, x k ).
Let b precede any alphabetical character. Then X d Y if
x 1 ∙ y 1 and x 1 d y 1
or
x 1 = y 1 , x 2 = y 2 , …, x m = y m (m ≤ k)
x m+1 ∙ y m+1 and x m+1 d y m+1
Otherwise, Y d X .
Note that because the ordering d on alphabetical characters is a total ordering, if Y d X by “otherwise,” then there exists m ≤ k such that x 1 = y 1 , x 2 = y 2 ,…, x m = y m , x m+1 ∙ y m+1 and y m+1 d x m+1 .
Show that d on S as defined above is a total ordering.
42. Apply the total ordering described in Exercise 41 to the words boo, bug, be, bah, and bugg. Note why each
word precedes the next.
43. Exercise 41 discusses a total ordering on a set of words of length at most n that will produce a linear list
in alphabetical order. Suppose we want to generate a list of all the distinct words in a text (for example,
a compiler must create a symbol table of variable names). As in Exercise 41, we assume that the words
contain only alphabetical characters because there is a natural precedence relation already existing
(a a b, b a c, and so on). If numeric or special characters are involved, they must be assigned a
351
b. If (S, r) is a finite, partially ordered set with the Hasse diagram shown, draw the diagram of the dual of
(S, r).
c. Let (S, r) be a totally ordered set and let X = 5(x, x) 0 x [ S6. Show that the setdifference r
−1
− X
equals the set r′.
41. A computer program is to be written that will generate a dictionary or the index for a book. We will
assume a maximum length of n characters per word. Thus, we are given a set S of words of length at most
n, and we want to produce a linear list of these words arranged in alphabetical order. There is a natural
total ordering d on alphabetic characters (a a b, b a c, etc.), and we will assume our words contain
only alphabetic characters. We want to define a total ordering d on S called a lexicographical ordering
that will arrange the members of S alphabetically. The idea is to compare two words X and Y character by
character, passing over equal characters. If at any point the X character alphabetically precedes the corresponding Y character, then X precedes Y; if all characters in X are equal to the corresponding Y characters
but we run out of characters in X before characters in Y, then X precedes Y. Otherwise, Y precedes X.
Formally, let X = (x 1 , x 2 , … , x j ) and Y = (y 1 , y 2 , … , y k ) be members of S with j ≤ k. Let b (for
blank) be a new symbol, and fill out X with k − j blanks on the right. X can now be written (x 1 , x 2 , …, x k ).
Let b precede any alphabetical character. Then X d Y if
x 1 ∙ y 1 and x 1 d y 1
or
x 1 = y 1 , x 2 = y 2 , …, x m = y m (m ≤ k)
x m+1 ∙ y m+1 and x m+1 d y m+1
Otherwise, Y d X .
Note that because the ordering d on alphabetical characters is a total ordering, if Y d X by “otherwise,” then there exists m ≤ k such that x 1 = y 1 , x 2 = y 2 ,…, x m = y m , x m+1 ∙ y m+1 and y m+1 d x m+1 .
Show that d on S as defined above is a total ordering.
42. Apply the total ordering described in Exercise 41 to the words boo, bug, be, bah, and bugg. Note why each
word precedes the next.
43. Exercise 41 discusses a total ordering on a set of words of length at most n that will produce a linear list
in alphabetical order. Suppose we want to generate a list of all the distinct words in a text (for example,
a compiler must create a symbol table of variable names). As in Exercise 41, we assume that the words
contain only alphabetical characters because there is a natural precedence relation already existing
(a a b, b a c, and so on). If numeric or special characters are involved, they must be assigned a