Section 5.1 Relations
353
until finally
when
in
course
human
events
of
the
By traversing the nodes of this graph in the proper order (described by always processing the left nodes
below a node first, then the node, then the right nodes below it), an alphabetical listing “course, events,
human, in, of, the, when” is produced.
a. This type of graph is called a tree. (Unlabeled nodes and arcs to unlabeled nodes usually are not
shown.) Turned upside down, the graph can be viewed as the Hasse diagram of a partial ordering d.
What would be the least element? Would there be a greatest element? Which of the following ordered
pairs would belong to d: (in, of), (the, of), (in, events), (course, of)?
Here the tree structure contains more information than the partial ordering, because we are interested in not only whether a word w 1 precedes a word w 2 in the partial ordering sense but also whether
w 2 is to the left or right of w 1 .
b. Build a binary search tree for the phrase “Old King Cole was a merry old soul.” Eliminate unlabeled nodes. Considering the upside-down graph as the Hasse diagram of a partial ordering, name the
maximal elements.
44. The alphabetical ordering defined in Exercise 41 can be applied to words of any finite length. If we define
A* to be the set of all finite-length “words” (strings of characters, not necessarily meaningful) from the
English alphabet, then the alphabetical ordering on A* has all words composed only of the letter A preceding all other words. Thus, all the words in the infinite list
a, aa, aaa, aaaa, …
precede words such as “b” or “aaaaaaab.” Therefore this list does not enumerate A*, because we can
never count up to any words with any characters other than a. However, the set A* is denumerable. Write
a partial enumeration of A* by ordering words by length (all words of length 1 precede all words of length
2, and so on) and then alphabetically ordering words of the same length.
45. a. For the equivalence relation r = 5(a, a), (b, b), (c, c), (a, c), (c, a)6, what is the set [a]? Does it have
any other names?
b. For the equivalence relation r = 5(1, 1), (2, 2), (1, 2), (2, 1), (1, 3), (3, 1), (3, 2), (2, 3), (3, 3), (4, 4),
(5, 5), (4, 5), (5, 4)6 what is the set [3]? What is the set [4]?
46. Prove that for any positive integer n, congruence modulo n is an equivalence relation on the set Z.
47. For the equivalence relation of congruence modulo 2 on the set Z, what is the set [1]?
48. For the equivalence relation of congruence modulo 5 on the set Z, what is the set [−3]?
49. Assume that x ≡ y (mod n) and z ≡ w (mod n) for some positive integer n. Prove that
a. x + z ≡ y + w (mod n)
b. x − z ≡ y − w (mod n)
c. x # z ≡ y # w (mod n)
d. x
s
≡ y
s
(mod n) for s ≥ 1, n ≥ 2
353
until finally
when
in
course
human
events
of
the
By traversing the nodes of this graph in the proper order (described by always processing the left nodes
below a node first, then the node, then the right nodes below it), an alphabetical listing “course, events,
human, in, of, the, when” is produced.
a. This type of graph is called a tree. (Unlabeled nodes and arcs to unlabeled nodes usually are not
shown.) Turned upside down, the graph can be viewed as the Hasse diagram of a partial ordering d.
What would be the least element? Would there be a greatest element? Which of the following ordered
pairs would belong to d: (in, of), (the, of), (in, events), (course, of)?
Here the tree structure contains more information than the partial ordering, because we are interested in not only whether a word w 1 precedes a word w 2 in the partial ordering sense but also whether
w 2 is to the left or right of w 1 .
b. Build a binary search tree for the phrase “Old King Cole was a merry old soul.” Eliminate unlabeled nodes. Considering the upside-down graph as the Hasse diagram of a partial ordering, name the
maximal elements.
44. The alphabetical ordering defined in Exercise 41 can be applied to words of any finite length. If we define
A* to be the set of all finite-length “words” (strings of characters, not necessarily meaningful) from the
English alphabet, then the alphabetical ordering on A* has all words composed only of the letter A preceding all other words. Thus, all the words in the infinite list
a, aa, aaa, aaaa, …
precede words such as “b” or “aaaaaaab.” Therefore this list does not enumerate A*, because we can
never count up to any words with any characters other than a. However, the set A* is denumerable. Write
a partial enumeration of A* by ordering words by length (all words of length 1 precede all words of length
2, and so on) and then alphabetically ordering words of the same length.
45. a. For the equivalence relation r = 5(a, a), (b, b), (c, c), (a, c), (c, a)6, what is the set [a]? Does it have
any other names?
b. For the equivalence relation r = 5(1, 1), (2, 2), (1, 2), (2, 1), (1, 3), (3, 1), (3, 2), (2, 3), (3, 3), (4, 4),
(5, 5), (4, 5), (5, 4)6 what is the set [3]? What is the set [4]?
46. Prove that for any positive integer n, congruence modulo n is an equivalence relation on the set Z.
47. For the equivalence relation of congruence modulo 2 on the set Z, what is the set [1]?
48. For the equivalence relation of congruence modulo 5 on the set Z, what is the set [−3]?
49. Assume that x ≡ y (mod n) and z ≡ w (mod n) for some positive integer n. Prove that
a. x + z ≡ y + w (mod n)
b. x − z ≡ y − w (mod n)
c. x # z ≡ y # w (mod n)
d. x
s
≡ y
s
(mod n) for s ≥ 1, n ≥ 2