CHAPTER 2. SET THEORY Theorem 66 Let f: A-B and g: B-C be surjections. Their composi tion go f is a surjection Exercise 2.4.4 Prove Theorem 66. Answer: We must show that for g o f A-C given by(go f)(a)=gf(a)), it is the case that Vc E C, there erists E A such that(go f)(a)=c. To see this, letcE C. Since g is a surjection, 3b∈ B such that g(b)=c. Similarly, since f is a surjection,丑a∈Asch that f(a)=b Then(go f(a=g(f(a))=g(b)=c 2.5 Finite and Infinite sets The purpose of this section is to compare sizes of sets with respect to the number of elements they contain. Take two sets A=(1, 2, 3) and B ta,b, c, d]. The number of elements of the set A(also called the cardinality of A, denoted card(A)) is three and of the set B is four. In this case we say that the set b is bigger than the set a It is hard, however, to apply this same concept in comparing, for instance he set of all natural numbers n with the set of all integers z. both are infinite. Is the"infinity"that represents card(N)smaller than the"infinity that represents card(z)? One might think the statement was true because there are integers that are not real numbers(.g.-1,-2 We wil show however that this statement is false. but first we have to introduce a different concept of the size of a set known as countability and uncountablity To illustrate it, one of the authors placed a set of 3 coins in front of his 3 year old daughter and asked her "Is that collection of coins countable? " She proceeded to pick up the first coin with her right hand, put it in her left hand, and said'1', pick up the second coin, put it in her left hand, and said 2, and pick up the final coin, put it in her left hand, and said 3. Thus, she out the set of coins into a one-to-one assignment with the first three natural numbers. We will now make use of one-to-one assignments between elements of two sets Definition 67 Two sets A and b are equivalent if there is a bijection Definition 68 An initial segment(or section)ofn is the set en=i N:i≤m}
34 CHAPTER 2. SET THEORY Theorem 66 Let f : A → B and g : B → C be surjections. Their composition g ◦ f is a surjection. Exercise 2.4.4 Prove Theorem 66. Answer: We must show that for g ◦ f : A → C given by (g ◦ f) (a) = g(f(a)),it is the case that ∀c ∈ C, there exists a ∈ A such that (g ◦ f) (a) = c. To see this, let c ∈ C. Since g is a surjection, ∃b ∈ B such that g(b) = c. Similarly, since f is a surjection, ∃a ∈ A such that f(a) = b. Then (g ◦ f) (a) = g(f(a)) = g(b) = c. 2.5 Finite and Infinite Sets The purpose of this section is to compare sizes of sets with respect to the number of elements they contain. Take two sets A = {1, 2, 3} and B = {a, b, c, d}. The number of elements of the set A (also called the cardinality of A, denoted card(A)) is three and of the set B is four. In this case we say that the set B is bigger than the set A. It is hard, however, to apply this same concept in comparing, for instance, the set of all natural numbers N with the set of all integers Z. Both are infinite. Is the îinfinityî that represents card(N) smaller than the îinfinityî that represents card(Z)? One might think the statement was true because there are integers that are not real numbers (e.g. −1, −2, −3, ...). We will show however that this statement is false, but first we have to introduce a different concept of the size of a set known as countability and uncountablity. To illustrate it, one of the authors placed a set of 3 coins in front of his 3 year old daughter and asked her ìIs that collection of coins countable?î. She proceeded to pick up the first coin with her right hand, put it in her left hand, and said ë1í, pick up the second coin, put it in her left hand, and said ë2í, and pick up the final coin, put it in her left hand, and said ë3í. Thus, she put the set of coins into a one-to-one assignment with the first three natural numbers. We will now make use of one-to-one assignments between elements of two sets. Definition 67 Two sets A and B are equivalent if there is a bijection f : A → B. Definition 68 An initial segment (or section) of N is the set ™n = {i ∈ N : i ≤ n}
2.5. FINITE AND INFINITE SETS Definition 69 A set A is finite if it is empty or there exists a bijection f: A-On for some n EN. In the former case a has zero elements and in the latter case a has n element Lemma 70 Let b be a proper subset of a finite set A. There does not exist a bijection f:A→B Proof. ( Sketch) Since A is finite, 3f: A-On. If B is a proper subset of A then it contains m n elements. But there cannot be a bijection between n and m elements.■ Exercise 2.5.1 Prove lemma 70 more formally. See lemma 6.1 in Munkres Lemma 70 says that a proper subset of a finite set cannot be equivalent with the whole set. This is quite clear. But is it true for any set? Let's Ⅳ={1,2,3,4,…} and a proper subset N{1}={2,3,4,…}.We can construct a one-to-one assignment from N onto N 1(i.e. 1-2, 2-3,. Thus, in this case, it is possible for a set to be equivalent with its proper subset. Given Lemma 70, we must conclude the following Theorem 71 n is not finite Proof. By contradiction. Suppose N is finite. Thenf: N-NI defined by f(n)=n+ l is a bijection of N with a proper subset of itself. This contradicts Lemma 70. Definition 72 A set A is infinite if it is not finite. It is countably infi- mite if there exists a bijection f: N-A Thus, N is countably infinite since f can be taken to be the identit function(which is a bijection) Definition 73 A set is countable if it is finite or countably infinite. A set that is not countable is uncountable Next we examine whether the set of integers. Z. is countable. That is are N and Z equivalent? This isn't apparent since N=(1, 2, . has one end of the set that goes to infinity, while Z= ,-2,, 0, 1, 2,. has two ends of the set that go to infinity. But it is possible to reorganize Z in a way that looks like n since we can simply construct Z=10, 1,-1, 2, 2,. One can think of this set as being constructed from two rows 0, 1, 2, and (,. by alternating between the first and second rows. This is ormalized in the next example
2.5. FINITE AND INFINITE SETS 35 Definition 69 A set A is finite if it is empty or there exists a bijection f : A → ™n for some n ∈ N. In the former case A has zero elements and in the latter case A has n elements. Lemma 70 Let B be a proper subset of a finite set A. There does not exist a bijection f : A → B. Proof. (Sketch) Since A is finite, ∃f : A → ™n. If B is a proper subset of A, then it contains m<n elements. But there cannot be a bijection between n and m elements. Exercise 2.5.1 Prove lemma 70 more formally. See lemma 6.1 in Munkres. Lemma 70 says that a proper subset of a finite set cannot be equivalent with the whole set. This is quite clear. But is it true for any set? Letís consider N = {1, 2, 3, 4, ...} and a proper subset N\{1} = {2, 3, 4, ...}. We can construct a one-to-one assignment from N onto N\{1} (i.e. 1 → 2, 2 → 3, ...). Thus, in this case, it is possible for a set to be equivalent with its proper subset. Given Lemma 70, we must conclude the following. Theorem 71 N is not finite. Proof. By contradiction. Suppose N is finite. Then .f : N → N\{1} defined by f(n) = n + 1 is a bijection of N with a proper subset of itself. This contradicts Lemma 70. Definition 72 A set A is infinite if it is not finite. It is countably infi- nite if there exists a bijection f : N → A. Thus, N is countably infinite since f can be taken to be the identity function (which is a bijection). Definition 73 A set is countable if it is finite or countably infinite. A set that is not countable is uncountable. Next we examine whether the set of integers, Z, is countable. That is, are N and Z equivalent? This isnít apparent since N = {1, 2, ...} has one end of the set that goes to infinity, while Z = {..., −2, −1, 0, 1, 2, ...} has two ends of the set that go to infinity. But it is possible to reorganize Z in a way that looks like N since we can simply construct Z = {0, 1, −1, 2, −2, ...}. One can think of this set as being constructed from two rows {0, 1, 2, ...} and {−1, −2, ...} by alternating between the first and second rows. This is formalized in the next example
CHAPTER 2. SET THEORY Example 74 The set of integers, Z, is countably infinite. The function f:z→ n defined by if 2>0 -2z+1ifz≤0 is a bijection. Exercise 2.5.2 Prove that a finite union of countable sets is countable Next we examine whether N XNNN. As in the preceding example where we had two rows, we can think about enumerating the set n x N in Figure 2.5.1. As in the preceding example, each row has infinitely many elements but now there are an infinite number of rows. yet all of the elements of this infinite matrix"can be enumerated if we start from(1, 1)and then continue by following the arrows. This enumeration provides us with the desired bijection as shown next Example 75 The cartesian product N xn is countably infinite. First, let the bijection g:N×N→A, there ACN× n consists of pairs(x,y)for which y < a, be given by g(a, y)=(a+y-1, y). Net construct a bijection h: A-N given by h(a, y)=2(r-1)x+y Then the composition f= hog is the desired bijection set A. The next theorem accomplishes this proving coun We can actually weaken the condition for proving countability of a give Theorem 76 Let A be a non-empty set. The following statements are equi- alent:(i) There is a surjection f: N-A.(ii) There is an injection g:A- n.(iii) A is countable Proof.(Sketch)(i=(ii). Given f, define g: A by g(a)= snakes element of f-(a). Since f is a surjection, the inverse image f-Ra)is non-empty so that g is well defined. g is an injection since if a+ a, the sets f-Ha) and f-al are disjoint(recall Exercise 2.4.3), so their smallest elements are distinct proving 9: A-+Nis an injection (i)→(i). Since g:A→R(g) is a surjection by definition,g:A→R(g) is a bijection. Since R(gcN, A must be countable (i)→(i). By definition.■
36 CHAPTER 2. SET THEORY Example 74 The set of integers, Z, is countably infinite. The function f : Z → N defined by f(z) = ½ 2z if z > 0 −2z + 1 if z ≤ 0 is a bijection. Exercise 2.5.2 Prove that a finite union of countable sets is countable. Next we examine whether N × N ∼ N. As in the preceding example where we had two rows, we can think about enumerating the set N × N in Figure 2.5.1. As in the preceding example, each row has infinitely many elements but now there are an infinite number of rows. Yet all of the elements of this îinfinite matrixî can be enumerated if we start from (1, 1) and then continue by following the arrows. This enumeration provides us with the desired bijection as shown next. Example 75 The cartesian product N × N is countably infinite. First, let the bijection g : N × N →A, where A ⊂ N × N consists of pairs (x, y) for which y ≤ x, be given by g(x, y)=(x + y − 1, y). Next construct a bijection h : A → N given by h(x, y) = 1 2 (x − 1)x + y. Then the composition f = h ◦ g is the desired bijection. We can actually weaken the condition for proving countability of a given set A. The next theorem accomplishes this. Theorem 76 Let A be a non-empty set. The following statements are equivalent: (i) There is a surjection f : N →A. (ii) There is an injection g : A → N. (iii) A is countable. Proof. (Sketch) (i)⇒(ii). Given f, define g : A → N by g(a) =smallest element of f −1({a}). Since f is a surjection, the inverse image f −1({a}) is non-empty so that g is well defined. g is an injection since if a 6= a0 , the sets f −1({a}) and f −1({a0 }) are disjoint (recall Exercise 2.4.3), so their smallest elements are distinct proving g : A → N is an injection. (ii)⇒(iii). Since g : A → R(g) is a surjection by definition, g : A → R(g) is a bijection. Since R(g) ⊂ N, A must be countable. (iii)⇒(i). By definition
2.5. FINITE AND INFINITE SETS Exercise 2.5. 3 Finish parts(ii) =(iii) and(iii=(i)of the proof of Theorem 76. See Munkres 7.1 (USES WELL ORDERING) Example 77 The set of positive rationals, Q++, is countably infinite. Define a surjection g:N×N→Q++b9(n,m)=m. Since n× n is countable ( Example75), there is a surjection h:N→N×N. Then f=goh:N→Q++ is a surjection(Theorem 66)so by Theorem 76, Q++ is countable The intuition for the preceding example follows simply from Figure 2.5.1 you replace the " "with"/". That is, replace(1, 1)with the rational 1 (1, 2)with the rational 2,(3, 2)with the rational 2, etc Theorem 78 A countable union of countable sets is countable Proof. Let Ai, iE A be an indexed family of countable sets where A is countable. Because each Ai is countable, for each i we can choose a surjection f i: N+A. Similarly, we can choose a surjection g: N-2. Define h N×N→U∈ a Ai by h(n,m)=fo(m), which is a surjection. Since n×N is in bijective correspondence with N(recall Example 75), the countability of the union follows from theorem 76. The next theorem provides an alternative proof of example 75 Theorem 79 A finite product of countable sets is countable Proof. Let A and b be two non-empty countable sets. Choose surjective functions g:N→ A and h:N→B. Then the function f:N×N→A×B defined by f(n, m)=(g(n), h(m)) is surjective. By Theorem 76, A X B countable. Proceed by induction for any finite product. E While it's tempting to think that this result could be extended to show that a countable product of countable sets is countable, the next Theorem hows this is false. Furthermore, it gives us our first example of an uncount able set Theorem 80 Let X= 0, 1. The set of all functions x: N-X, denoted Xu, is uncountable 10 10 An alternative statement of the theorem is that the set of all infinite sequences of X
2.5. FINITE AND INFINITE SETS 37 Exercise 2.5.3 Finish parts (ii)⇒(iii) and (iii)⇒(i) of the proof of Theorem 76. See Munkres 7.1 (USES WELL ORDERING). Example 77 The set of positive rationals, Q++, is countably infinite. Define a surjection g : N × N → Q++ by g(n, m) = m n . Since N × N is countable (Example 75), there is a surjection h : N → N × N. Then f = g◦h : N → Q++ is a surjection (Theorem 66) so by Theorem 76, Q++ is countable. The intuition for the preceding example follows simply from Figure 2.5.1 if you replace the î,î with î/î. That is, replace (1, 1) with the rational 1 1 , (1, 2) with the rational 1 2 , (3, 2) with the rational 3 2 , etc. Theorem 78 A countable union of countable sets is countable. Proof. Let {Ai, i ∈ Λ} be an indexed family of countable sets where Λ is countable. Because each Ai is countable, for each i we can choose a surjection fi : N →Ai. Similarly, we can choose a surjection g : N → §. Define h : N × N → ∪i∈Λ Ai by h(n, m) = fg(n)(m), which is a surjection. Since N × N is in bijective correspondence with N (recall Example 75), the countability of the union follows from Theorem 76. The next theorem provides an alternative proof of example 75. Theorem 79 A finite product of countable sets is countable. Proof. Let A and B be two non-empty, countable sets. Choose surjective functions g : N → A and h : N → B. Then the function f : N × N →A × B defined by f(n, m)=(g(n), h(m)) is surjective. By Theorem 76, A × B is countable. Proceed by induction for any finite product. While itís tempting to think that this result could be extended to show that a countable product of countable sets is countable, the next Theorem shows this is false. Furthermore, it gives us our first example of an uncountable set. Theorem 80 Let X = {0, 1}. The set of all functions x : N →X, denoted Xω, is uncountable.10 10An alternative statement of the theorem is that the set of all infinite sequences of X is uncountable
CHAPTER 2. SET THEORY Proof. We show that any function g: N-X is not a surjection. Let wher either o or 1. define a y=(h,y,…,yn,…) of X by letting 0 if 1 if 0 y∈ differ in at least one coordinate, namely the n th. Thus g is not a surjection The diagonal argument used above(See Figure 2.5.2 will be useful to establish the uncountability of the reals, which we save until Chapter 3 Exercise 2.5.4 Consider the following game known as "matching pennies You(a) and I (B) each hold a penny. We simaltaneously reveal either heads”(H)or“ tails”(r) to each other. If both faces match(a.e.both heads or both tails you receive a penny, otherwise I get the penny. The ac- tion sets for each player are SA=SB=(, T]. Now suppose we decide to play this ge ane eve ry day for the indefinite (infinite) future(we're opti mistic about medical technologg ). Before you begin, you should think: of all the different combinations of actions you may employ in the infinitely re- peated game. For instance, you may alternate H and T starting with h in the first round. Prove that although the number of actions you play in the infinitely repeated game is countable and the set of actions Sa is finite, the set of possible combinations of actions(SA×SA×…) is uncountable 2.6 Algebras of Sets An algebra is just a collection of sets (which could be infinite) that is closed under(finite) union and complementation. It is used extensively in proba y a Definition 81 A collection A of subsets of x is called an algebra of sets if(i)A∈AifA∈Aand(i)AUB∈AifA,B∈A Note that0,X∈ A since, for instance,A∈A→A∈Aby(i)and A∪A°=X∈Aby(i). It also follows from De Morgan,s laws that A∩B∈AifA,B∈A. The defi xtends t unions two at a time
38 CHAPTER 2. SET THEORY Proof. We show that any function g : N →Xω is not a surjection. Let g(n)=(xn1, xn2, ..., xnm, ...) where each xij is either 0 or 1. Define a point y = (y1, y2, ..., yn, ...) of Xω by letting yn = ½ 0 if xnn = 1 1 if xnn = 0 . Now y ∈ Xω and y is not in the image of g. That is, given n, g(n) and y differ in at least one coordinate, namely the nth. Thus g is not a surjection. The diagonal argument used above (See Figure 2.5.2) will be useful to establish the uncountability of the reals, which we save until Chapter 3. Exercise 2.5.4 Consider the following game known as ìmatching penniesî. You (A) and I (B) each hold a penny. We simultaneously reveal either ìheadsî (H) or ìtailsî (T) to each other. If both faces match (i.e. both heads or both tails) you receive a penny, otherwise I get the penny. The action sets for each player are SA = SB = {H, T}. Now suppose we decide to play this game every day for the indefinite (infinite) future (weíre optimistic about medical technology). Before you begin, you should think of all the different combinations of actions you may employ in the infinitely repeated game. For instance, you may alternate H and T starting with H in the first round. Prove that although the number of actions you play in the infinitely repeated game is countable and the set of actions SA is finite, the set of possible combinations of actions (SA × SA × ...) is uncountable. 2.6 Algebras of Sets An algebra is just a collection of sets (which could be infinite) that is closed under (finite) union and complementation. It is used extensively in probability and measure theory. Definition 81 A collection A of subsets of X is called an algebra of sets if (i) Ac ∈ A if A ∈ A and (ii) A ∪ B ∈ A if A, B ∈ A. Note that ∅, X ∈ A since, for instance, A ∈ A ⇒ Ac ∈ A by (i) and then A ∪ Ac = X ∈ A by (ii). It also follows from De Morganís laws that (iii) A∩B ∈ A if A, B ∈ A. The definition extends to larger collections (just take unions two at a time)