48 CHAPTER 3. SET THEORY

2. If x∼ y then y∼ x. (Symmetric)

3. If x∼ y and y∼ z, then x∼ z. (Transitive)

Definition 3.3.2 [x] denotes the set of all elements of S which are equivalent to xand [x] is called the equivalence class determined by x or just the equivalence class of x.

With the above definition one can prove the following simple theorem.

Theorem 3.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.

3.4 Hausdorff Maximal Theorem∗

The Hausdorff maximal theorem is equivalent to the axiom of choice. Hausdorff provedit in 1914. The useful direction is what I will prove below. It will not be used much inthe rest of the book which is mostly nineteenth century material. I am including it becauseit or something like it is either absolutely essential, as in the Hahn Banach theorem, orextremely useful to have.

Definition 3.4.1 For any set S,P (S) denotes the set of all subsets of S. It is some-times called the power set of S and is also sometimes denoted as 2S. A nonempty set F iscalled a partially ordered set if it has a partial order denoted by ≺. This means it satisfiesthe following. If x≺ y and y≺ z, then x≺ z. Also x≺ x. It is like ⊆ on the set of all subsetsof a given set. It is not the case that given two elements of F that they are related. In otherwords, you cannot conclude that either x≺ y or y≺ x. A chain, denoted by C ⊆F has theproperty that it is totally ordered meaning that if x,y ∈ C , either x≺ y or y≺ x. A maximalchain is a chain C which has the property that there is no strictly larger chain. In otherwords, if x ∈F\∪C , then C∪{x} is no longer a chain.

Here is the Hausdorff maximal theorem. The proof is a proof by contradiction. Weassume there is no maximal chain and then show that this cannot happen. The axiom ofchoice is used in choosing the xC right at the beginning of the argument. See Hewitt andStromberg [17] for more of this kind of thing.

Theorem 3.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