352 ORDERED SETS AND LATTICES [CHAP. 14
14.3. Prerequisites in college is a familiar partial ordering of available classes. We writeA≺Bif courseA
is a prerequisite for courseB. LetCbe the ordered set consisting of the mathematics courses and their
prerequisites appearing in Fig. 14-10(a).(a) Draw the Hasse diagram for the partial orderingCof these classes.
(b) Find all minimal and maximal elements ofC.
(c) DoesChave a first element or a last element?Fig. 14-10(a) Math 101 must be on the bottom of the diagram since it is the only course with no prerequisites. Since Math 201
and Math 250 only require Math 101, we have Math 101/Math 201and Math 101/Math 250; hence draw a
line slanting upward from Math 101 to Math 201 and one from Math 101 to Math 250. Continuing this process,
we obtain the Hasse diagram in Fig. 14-10(b).
(b) No element strictly precedes Math 101 so Math 101 is a minimal element ofC. No element strictly succeeds
Math 341 or Math 500, so each is a maximal element ofC.
(c) Math 101 is a first element ofCsince it precedes every other element ofC. However,Chas no last element.
Although Math 341 and Math 500 are maximal elements, neither is a last element since neither precedes the other.PRODUCT SETS AND ORDER
14.4. SupposeN^2 =N×Nis given the product order (Section 14.2) whereNhas the usual order≤.
Insert the correct symbol,≺,.,or‖(not comparable), between each of the following pairs of elements of
N×N:
(a) (5, 7) ___ (7, 1); (c) (5, 5) ___ (4, 8); (e) (7, 9) ___ (4, 1);
(b) (4, 6) ___ (4, 2); (d) (1, 3) ___ (1, 7); (f) (7, 9) ___ (8, 2).
Here(a, b)≺(a′,b′)ifa<a′andb≤b′or ifa≤a′andb<b′. Thus:
(a)‖since 5<7 but 7> 1 .(c)‖since 5>4 and 5< 8 .(e).since 7>4 and 9> 1.
(b).since 4=4 and 6> 2 .(d)≺since 1=1 and 3< 7 .(f)‖since 7<8 and 9> 2.14.5. Repeat Problem 14.4 using the lexicographical ordering ofN^2 =N×N.
Here(a, b)≺(a′,b′)ifa<a′or ifa=a′butb<b′. Thus:
(a)≺since 5<7. (c).since 5>4. (e).since 7>4.
(b).since 4=4 and 6>2. (d)≺since 1=1 but 3<7. (f)≺since 7<8.14.6. Consider the English alphabetA={a,b,c,...,y,z}with the usual (alphabetical) order. (Recall thatA∗
consisting of all words inA.) Consider the following list of words inA∗:
went, forget, to, medicine, me, toast, melt, for, we, arm(a) Sort the list of words using the short-lex (free semigroup) order.