Appendix B

The Hausdorff Maximal TheoremFirst is the definition of what is meant by a partial order.

Definition B.0.1 A nonempty set F is called a partially ordered set if it has a partial orderdenoted by ≺. This means it satisfies the following. If x ≺ y and y ≺ z, then x ≺ z. Alsox ≺ x. It is like ⊆ on the set of all subsets of a given set. It is not the case that given twoelements of F that they are related. In other words, you cannot conclude that either x≺ yor y ≺ x. A chain, denoted by C ⊆F has the property that it is totally ordered meaningthat if x,y ∈ C , either x≺ y or y≺ x. A maximal chain is a chain C which has the propertythat there is no strictly larger chain. In other words, if x ∈ F\∪C , then C∪{x} is nolonger a chain so x fails to be related to something in C .

Here is the Hausdorff maximal theorem. The proof is a proof by contradiction. Weassume there is no maximal chain and then show this cannot happen. The axiom of choiceis used in choosing the xC right at the beginning of the argument.

Theorem B.0.2 Let F be a nonempty partially ordered set with order≺. Then there existsa maximal chain.

Proof: For C a chain, let θC denote C ∪{xC } . Thus for C a chain, θC is a largerchain which has exactly one more element of F . Since F ̸= /0, pick x0 ∈ F . Note that{x0} is a chain. Let X be the set of all chains C such that x0 ∈ ∪C . Thus X contains{x0}. Call two chains comparable if one is a subset of the other. Also, if S is a nonemptysubset of F in which all chains are comparable, then ∪S is also a chain. From now on Swill always refer to a nonempty set of chains in which any pair are comparable. Thensummarizing,

1. x0 ∈ ∪C for all C ∈X .

2. {x0} ∈X

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

503