1. Fix some set X. In lecture, we remarked how C is ‘kind of like' ≤. It is actually possible
to take the analogy a little further, and talk about "upper bounds” and “lower bounds"
of collections of subsets of X.
Recall that the powerset P(X) is the set of all subsets of X. C = P(X) means that
CC X. Furthermore, a subset A C P(X) has elements of the form B E A, where
BC X. In other words, A is a collection of sets.
(a) Let C = P(X), and let A C P(X). We say C is an upper bound of A if B C C
for all BE A.
Given B₁, B₂ € P(X), show that B₁ U B₂ € P(X) is an upper bound of
{B1, B₂} C P(X).
(b) We say an upper bound S of A C P(X) is a least upper bound if for all upper
bounds C of A, SCC.
Given B₁, B₂ € P(X), show that if C is an upper bound of {B₁, B₂}, then
B₁ U B₂ C C. Use this with your result in (a) to show that B₁ U B2 is the unique
least upper bound of {B₁, B₂}.
(Hint: For the second part, first show that B₁UB₂ is a least upper bound. Then,
show that if S is another least upper bound, S = B₁ U B₂)
(c) Write down a corresponding definition for some C = P(X) to be a lower bound
of A C P(X). Use it to prove that B₁ ^ B₂ is a lower bound of {B₁, B₂}.
(d) Show that P(X) an analogue to the least upper bound property: every non-
empty collection A C P(X) has a least upper bound S.
You may find the following to be helpful: given a collection of sets A C P(X),
you can define a set which is the union over this collection,
UB:= = {x € X : x € B for some B € A} = P(X)
BEA