CHAP. 14] ORDERED SETS AND LATTICES 351
SolvedProblems
ORDERED SETS AND SUBSETS
14.1. LetN={ 1 , 2 , 3 ,...}be ordered by divisibility. State whether each of the following subsets ofNare
linearly (totally) ordered.(a){ 24 , 2 , 6 }; (c)N={ 1 , 2 , 3 ...}; (e){ 7 };
(b){ 3 , 15 , 5 }; (d){ 2 , 8 , 32 , 4 }; (f ){ 15 , 5 , 30 }.(a) Since 2 divides 6 which divides 24, the set is linearly ordered.
(b) Since 3 and 5 are not comparable, the set is not linearly ordered.
(c) Since 2 and 3 are not comparable, the set is not linearly ordered.
(d) This set is linearly ordered since 2≺ 4 ≺ 8 ≺32.
(e) Any set consisting of one element is linearly ordered.
(f) Since 5 divides 15 which divides 30, the set is linearly ordered.14.2. LetA={ 1 , 2 , 3 , 4 , 5 }be ordered by the Hasse diagram in Fig. 14-9(a).(a) Insert the correct symbol,≺,.,or‖(not comparable), between each pair of elements:
(i)1 ___ 5;(ii)2 ___ 3;(iii)4 ___ 1;(iv)3 ___ 4.
(b) Find all minimal and maximal elements ofA.
(c) DoesAhave a first element or a last element?
(d) LetL(A)denote the collection of all linearly ordered subsets ofAwith 2 or more elements, and let
L(A)be ordered by set inclusion. Draw the Hasse diagram ofL(A).Fig. 14-9(a) (i) Since there is a “path” (edges slanting upward) from 5 to 3 to 1, 5 precedes 1; hence 1.5.
(ii) There is no path from 2 to 3, or vice versa; hence 2‖3.
(iii) There is a path from 4 to 2 to 1; hence 4≺1.
(iv) Neither 3≺4 nor 4≺3; hence 3‖4.
(b) No element strictly precedes 4 or 5, so 4 and 5 are minimal elements ofA. No element strictly succeeds 1, so 1
is a maximal element ofA.
(c) A has no first element. Although 4 and 5 are minimal elements ofA, neither precedes the other. However, 1 is a
last element ofAsince 1 succeeds every element ofA.
(d) The elements ofL(A)are as follows:{ 1 , 2 , 4 }, { 1 , 2 , 5 }, { 1 , 3 , 5 }, { 1 , 2 }, { 1 , 4 }, { 1 , 3 ), { 1 , 5 }, { 2 , 4 }, { 2 , 5 }, { 3 , 5 }(Note{ 2 , 5 }and{ 3 , 4 }arenotlinearly ordered.) The diagram ofL(A)appears in Fig. 14-9(b).