3.5. EXERCISES 49

3. If C ∈X then θC ∈X .

4. If S ⊆X then ∪S ∈X .

A subset Y of X will be called a “tower” if Y satisfies 1.) - 4.). Let Y0 be theintersection of all towers. Then Y0 is also a tower, the smallest one. Then the next claimmight seem to be so because if not, Y0 would not be the smallest tower.

Claim 1: If C0 ∈ Y0 is comparable to every chain C ∈ Y0, then if C0 ⊊ C , it must bethe case that θC0 ⊆ C . In other words, xC0 ∈ ∪C . The symbol ⊊ indicates proper subset.

This is done by considering a set B ⊆ Y0 consisting of D which acts like C in theabove and showing that it actually equals Y0 because it is a tower.

Proof of Claim 1: Consider B ≡{D ∈ Y0 : D ⊆ C0 or xC0 ∈ ∪D

}. Let Y1 ≡Y0∩B.

I want to argue that Y1 is a tower. By definition all chains of Y1 contain x0 in their unions.If D ∈ Y1, is θD ∈ Y1? If S ⊆ Y , is ∪S ∈ Y1? Is {x0} ∈B?{x0} cannot properly contain C0 since x0 ∈ ∪C0. Therefore, C0 ⊇ {x0} so {x0} ∈B.If S ⊆ Y1, and D ≡ ∪S , is D ∈ Y1? Since Y0 is a tower, D is comparable to C0.

If D ⊆ C0, then D is in B. Otherwise D ⊋ C0 and in this case, why is D in B? Why isxC0 ∈ ∪D? The chains of S are in B so one of them, called C̃ must properly contain C0

and so xC0 ∈ ∪C̃ ⊆ ∪D . Therefore, D ∈B∩Y0 = Y1. 4.) holds. Two cases remain, toshow that Y1 satisfies 3.).

case 1: D ⊋ C0. Then by definition of B, xC0 ∈ ∪D and so xC0 ∈ ∪θD so θD ∈ Y1.case 2: D ⊆ C0. θD ∈ Y0 so θD is comparable to C0. First suppose θD ⊋ C0. Thus

D ⊆ C0 ⊊ D ∪{xD} . If x ∈ C0 and x is not in D then D ∪{x} ⊆ C0 ⊊ D ∪{xD}. Thisis impossible. Consider x. Thus in this case that θD ⊋ C0, D = C0. It follows thatxD = xC0 ∈ ∪θC0 = ∪θD and so θD ∈ Y1. The other case is that θD ⊆ C0 so θD ∈Bby definition. This shows 3.) so Y1 is a tower and must equal Y0.

Claim 2: Any two chains in Y0 are comparable.Proof of Claim 2: Let Y1 consist of all chains of Y0 which are comparable to every

chain of Y0. {x0} is in Y1 by definition. All chains of Y0 have x0 in their union. IfS ⊆Y1, is ∪S ∈Y1? Given D ∈Y0 either every chain of S is contained in D or at leastone contains D . Either way D is comparable to ∪S so ∪S ∈ Y1. It remains to show 3.).Let C ∈ Y1 and D ∈ Y0. Since C is comparable to all chains in Y0, it follows from Claim1 either C ⊊ D when xC ∈ ∪D and θC ⊆ D or C ⊇ D when θC ⊇ D . Hence Y1 = Y0because Y0 is as small as possible.

Since every pair of chains in Y0 are comparable and Y0 is a tower, it follows that∪Y0 ∈ Y0 so ∪Y0 is a chain. However, θ ∪Y0 is a chain which properly contains ∪Y0and since Y0 is a tower, θ ∪Y0 ∈ Y0. Thus ∪(θ ∪Y0) ⊋ ∪(∪Y0) ⊇ ∪(θ ∪Y0) which isa contradiction. Therefore, for some chain C it is impossible to obtain the xC describedabove and so, this C is a maximal chain.

3.5 Exercises1. The Barber of Seville is a man and he shaves exactly those men who do not shave

themselves. Who shaves the Barber?

2. Do you believe each person who has ever lived on this earth has the right to dowhatever he or she wants? (Note the use of the universal quantifier with no set insight.) If you believe this, do you really believe what you say you believe? What ofthose people who want to deprive others their right to do what they want? (This is