3.5. EXERCISES 51

13. If S = {1, · · · ,n}, show P (S) has exactly 2n elements in it. Hint: You might try afew cases first.

14. Let S denote the set of all sequences which have either 0 or 1 in every entry. Youhave seen sequences in calculus. They will be discussed more formally later. Showthat the set of all such sequences cannot be countable. Hint: Such a sequence can bethought of as an ordered list a1a2a3 · · · where each ai is either 0 or 1. Suppose youcould list them all as follows.

a1 = a11a12a13 · · ·a2 = a21a22a23 · · ·a3 = a31a32a33 · · ·

...

Then consider the sequence a11a22a33 · · · . Obtain a sequence which can’t be in thelist by considering the sequence b1b2b3 · · · where bk is obtained by changing akk.Explain why this sequence can’t be any of the ones which are listed.

15. Show that the collection of sequences a1a2 · · ·an such that each ak is either 0 or 1such that ak = 0 for all k larger than n is countable. Now show that the collection ofsequences consisting of either 0 or 1 such that ak is 0 for all k larger than some n isalso countable. However, the set of all sequences of 0 and 1 is not countable.

16. Let S be the set of sequences of 0 or 1. Show there exists a mapping θ : [0,1]→Swhich is onto. Explain why this requires [0,1] to be uncountable.

17. Prove Theorem 3.3.3, the theorem about partitioning using an equivalence relationinto equivalence classes.

18. Let S be a set and consider a function f which maps P (S) to P (S) which satisfiesthe following. If A⊆ B, then f (A)⊆ f (B). Then there exists A such that f (A) = A.Hint: You might consider the following subset of P (S) .

C ≡ {B ∈P (S) : B⊆ f (B)}

Then consider A ≡ ∪C . Argue A is the “largest” set in C which implies A cannotbe a proper subset of f (A). This is a case of the Tarski fixed point theorem. If X isa subset of P (S) such that if F ⊆ X , then ∪F ∈ X and if f is increasing as aboveand f (x) ∈ X for all x ∈ X , then the same result follows.

19. Another formulation of the Hausdorff maximal theorem is Zorn’s lemma. This saysthat if you have a nonempty partially ordered set and every chain has an upper bound,then there exists a maximal element, one which has no element of the partial orderwhich is larger. Show these two formulations are equivalent and each is equivalentto the axiom of choice.

20. A nonempty set X is well ordered if there exists an order ≤ which is a total order ofthe elements of X and in addition has the property that every nonempty subset of Xhas a smallest element. Zermelo showed that for every nonempty set X , there exists≤ which makes X a well ordered set. To prove Zermelo’s theorem, let F = {S⊆ X :there exists a well order for S}. Let S1 ≺ S2 if S1 ⊆ S2 and there exists a well order