Page 653 - Discrete Mathematics and Its Applications

632 9 / Relations

40. a) Show that there is exactly one greatest element of a ∗ 49. Show that the set of all partitions of a set S with the re-
poset, if such an element exists. lation P 1 P 2 if the partition P 1 is a refinement of the
b) Show that there is exactly one least element of a poset, partition P 2 is a lattice. (See the preamble to Exercise 49
if such an element exists. of Section 9.5.)
41. a) Show that there is exactly one maximal element in a 50. Show that every totally ordered set is a lattice.
poset with a greatest element.
51. Show that every finite lattice has a least element and a
b) Show that there is exactly one minimal element in a greatest element.
poset with a least element.
52. Give an example of an infinite lattice with
42. a) Show that the least upper bound of a set in a poset is
a) neither a least nor a greatest element.
unique if it exists.
b) Show that the greatest lower bound of a set in a poset b) a least but not a greatest element.
is unique if it exists. c) a greatest but not a least element.
43. Determine whether the posets with these Hasse diagrams d) both a least and a greatest element.
are lattices. 53. Verify that (Z × Z , ) is a well-ordered set, where
+
+
a) b) c) is lexicographic order, as claimed in Example 8.
g h i
54. Determine whether each of these posets is well-ordered.
f f g h
a) (S, ≤), where S ={10, 11, 12,...}
f g
d e d e b) (Q ∩[0, 1], ≤) (the set of rational numbers between
d e
b c b c 0 and 1 inclusive)
b c
a c) (S, ≤), where S is the set of positive rational numbers
a
a with denominators not exceeding 3
44. Determine whether these posets are lattices. d) (Z , ≥), where Z is the set of negative integers
−
−
a) ({1, 3, 6, 9, 12}, |) b) ({1, 5, 25, 125}, |)
A poset (R, ) is well-founded if there is no infinite de-
c) (Z, ≥) creasing sequence of elements in the poset, that is, elements
d) (P (S), ⊇), where P(S) is the power set of a set S x 1 ,x 2 ,...,x n such that ··· ≺ x n ≺ ··· ≺ x 2 ≺ x 1 . A poset
45. Show that every nonempty finite subset of a lattice has a (R, ) is dense if for all x ∈ S and y ∈ S with x ≺ y, there
least upper bound and a greatest lower bound. is an element z ∈ R such that x ≺ z ≺ y.
46. Show that if the poset (S, R) is a lattice then the dual 55. Show that the poset (Z, ), where x ≺ y if and only if
poset (S, R −1 ) is also a lattice. |x| < |y| is well-founded but is not a totally ordered set.
47. Inacompany,thelatticemodelofinformationflowisused 56. Show that a dense poset with at least two elements that
to control sensitive information with security classes rep- are comparable is not well-founded.
resented by ordered pairs (A, C). Here A is an authority
level, which may be nonproprietary (0), proprietary (1), 57. Show that the poset of rational numbers with the usual
restricted (2), or registered (3).A category C is a subset of “less than or equal to” relation, (Q, ≤), is a dense poset.
the set of all projects {Cheetah, Impala, Puma}. (Names ∗ 58. Show that the set of strings of lowercase English let-
of animals are often used as code names for projects in ters with lexicographic order is neither well-founded nor
companies.) dense.
a) Is information permitted to flow from (Proprietary,
{Cheetah, Puma}) into (Restricted, {Puma})? 59. Show that a poset is well-ordered if and only if it is totally
ordered and well-founded.
b) Is information permitted to flow from (Restricted,
{Cheetah}) into (Registered, {Cheetah, Impala})? 60. Show that a finite nonempty poset has a maximal element.
c) Into which classes is information from (Proprietary, 61. Find a compatible total order for the poset with the Hasse
{Cheetah, Puma}) permitted to flow? diagram shown in Exercise 32.
d) From which classes is information permitted to flow
into the security class (Restricted, {Impala, Puma})? 62. Find a compatible total order for the divisibility relation
on the set {1, 2, 3, 6, 8, 12, 24, 36}.
48. Show that the set S of security classes (A, C) is a lattice,
where A is a positive integer representing an authority 63. Find all compatible total orderings for the poset
class and C is a subset of a finite set of compartments, ({1, 2, 4, 5, 12, 20}, |} from Example 26.
with (A 1 ,C 1 ) (A 2 ,C 2 ) if and only if A 1 ≤ A 2 and 64. Find all compatible total orderings for the poset with the
C 1 ⊆ C 2 .[Hint:Firstshowthat(S, )isaposetandthen Hasse diagram in Exercise 27.
show that the least upper bound and greatest lower bound
of (A 1 ,C 1 ) and (A 2 ,C 2 ) are (max(A 1 ,A 2 ), C 1 ∪ C 2 ) 65. Find all possible orders for completing the tasks in the
and (min(A 1 ,A 2 ), C 1 ∩ C 2 ), respectively.] development project in Example 27.