1.4. THE HAUSDORFF MAXIMAL THEOREM 9

Theorem 1.3.3 Let ∼ be an equivalence relation defined on a set, S and let Hdenote the set of equivalence classes. Then if [x] and [y] are two of these equivalenceclasses, either x∼ y and [x] = [y] or it is not true that x∼ y and [x]∩ [y] = /0.

Proof: If x ∼ y, then if z ∈ [y] , you have x ∼ y and y ∼ z so x ∼ z which shows that[y]⊆ [x]. Similarly, [x]⊆ [y]. If it is not the case that x∼ y, then there can be no intersectionof [x] and [y] because if z were in this intersection, then x∼ z,z∼ y so x∼ y. ■

1.4 The Hausdorff Maximal TheoremThe Hausdorff maximal theorem or something like it is often very useful. I will use itwhenever convenient because its use typically makes a much longer and involved argumentshorter. However, sometimes its use is absolutely essential. First is the definition of whatis meant by a partial order.

Definition 1.4.1 A nonempty set F is called a partially ordered set if it has a partialorder denoted by ≺. This means it satisfies the following. If x ≺ y and y ≺ z, then x ≺ z.Also x≺ 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.

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 1.4.2 Let F be a nonempty partially ordered set with order≺. Then thereexists a maximal chain.

Proof: Suppose not. Then for C a chain, let θC denote C ∪{xC } . Thus for C a chain,θC is a larger chain 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 . ThusX contains {x0}. Call two chains comparable if one is a subset of the other. Also, if Sis a nonempty subset of F in which all chains are comparable, then ∪S is also a chain.From now on S will always refer to a nonempty set of chains in which any pair arecomparable. Then summarizing,

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.