Cardinality Notes (MA 1201) - PDF

Cardinality MA 1201 Shibananda Biswas IISER Kolkata January 09, 2024 1 References Books A Foundation Course in Mathematics by Ajit Kumar, S. Kumaresan and B. K. Sharma Analysis - I by T. Tao Schaum’s Outline Of Set Theory and Related Topics by S. Lip...

Cardinality MA 1201 Shibananda Biswas IISER Kolkata January 09, 2024 1 References Books A Foundation Course in Mathematics by Ajit Kumar, S. Kumaresan and B. K. Sharma Analysis - I by T. Tao Schaum’s Outline Of Set Theory and Related Topics by S. Lipschutz Introduction to real analysis by S. K. Mapa Proof from the book by Martin Aigner , Gunter M. Ziegler, et al. 2 Notations Usual notations N: Natural numbers, {1, 2, 3,... , } Z: Integers Q: Rational numbers R: Real numbers C: Complex numbers Given a set A, let P(A) denotes its power set. When A contains n many elements, then P(A) contains 2n many elements. 3 Usual notations N: Natural numbers, {1, 2, 3,... , } Z: Integers Q: Rational numbers R: Real numbers C: Complex numbers Given a set A, let P(A) denotes its power set. When A contains n many elements, then P(A) contains 2n many elements. 3 Finite set Natural intuitions Finite set: One can count and finish counting! We say the set contains those many elements! A natural question: When two sets have same number of elements? For finite set, the answer could be found by simply counting the number of elements. All the sets below {a, b, c, d}, {2, 3, 5, 7}, {x, y, z, t} have 4 elements. 4 Natural intuitions Finite set: One can count and finish counting! We say the set contains those many elements! A natural question: When two sets have same number of elements? For finite set, the answer could be found by simply counting the number of elements. All the sets below {a, b, c, d}, {2, 3, 5, 7}, {x, y, z, t} have 4 elements. 4 Natural intuitions Finite set: One can count and finish counting! We say the set contains those many elements! A natural question: When two sets have same number of elements? For finite set, the answer could be found by simply counting the number of elements. All the sets below {a, b, c, d}, {2, 3, 5, 7}, {x, y, z, t} have 4 elements. 4 Alternate way However, it is not always necessary to know the number of elements in two sets to know that they have same number of elements! Suppose a number of people board a bus. When we will say that the number of people is the same as the number of seats in the bus? Let all the people sit down. If everyone finds a seat and no seat remains empty, then and only then two sets have same number of elements - basically 1 − 1, onto correspondence from people to seat. 5 Alternate way However, it is not always necessary to know the number of elements in two sets to know that they have same number of elements! Suppose a number of people board a bus. When we will say that the number of people is the same as the number of seats in the bus? Let all the people sit down. If everyone finds a seat and no seat remains empty, then and only then two sets have same number of elements - basically 1 − 1, onto correspondence from people to seat. 5 Alternate way However, it is not always necessary to know the number of elements in two sets to know that they have same number of elements! Suppose a number of people board a bus. When we will say that the number of people is the same as the number of seats in the bus? Let all the people sit down. If everyone finds a seat and no seat remains empty, then and only then two sets have same number of elements - basically 1 − 1, onto correspondence from people to seat. 5 Nothing new In fact, we learnt to count object by forming an 1 − 1 correspondence between objects and fingers or the lines on the finger. If one asks the question: How many days are there until Saturday? The response is often to actually pair the remaining days with one’s finger. Mathematically, we make a 1 − 1, onto correspondence with the set of objects to In := {1, 2,... , n}. This lead us to the following definition. 6 Nothing new In fact, we learnt to count object by forming an 1 − 1 correspondence between objects and fingers or the lines on the finger. If one asks the question: How many days are there until Saturday? The response is often to actually pair the remaining days with one’s finger. Mathematically, we make a 1 − 1, onto correspondence with the set of objects to In := {1, 2,... , n}. This lead us to the following definition. 6 Nothing new In fact, we learnt to count object by forming an 1 − 1 correspondence between objects and fingers or the lines on the finger. If one asks the question: How many days are there until Saturday? The response is often to actually pair the remaining days with one’s finger. Mathematically, we make a 1 − 1, onto correspondence with the set of objects to In := {1, 2,... , n}. This lead us to the following definition. 6 Same cardinality Definition. Two sets A and B are said to have same cardinality (that is, same no of elements or same size) if ∃ a function f : A → B which is bijective, that is, both 1 − 1 and onto. Exc. Let X be a set and A, B ⊆ X. Let A ∼ B if and only if A and B have same cardinality. Show that ∼ is an equivalence relation on P(X). Why suddenly we put the sets inside a set X - to avoid a logical fallacy. Russell’s paradox A barber in a city shaves only those who do not shave themselves. The questions is whether the barber shaves himself or not! 7 Same cardinality Definition. Two sets A and B are said to have same cardinality (that is, same no of elements or same size) if ∃ a function f : A → B which is bijective, that is, both 1 − 1 and onto. Exc. Let X be a set and A, B ⊆ X. Let A ∼ B if and only if A and B have same cardinality. Show that ∼ is an equivalence relation on P(X). Why suddenly we put the sets inside a set X - to avoid a logical fallacy. Russell’s paradox A barber in a city shaves only those who do not shave themselves. The questions is whether the barber shaves himself or not! 7 Same cardinality Definition. Two sets A and B are said to have same cardinality (that is, same no of elements or same size) if ∃ a function f : A → B which is bijective, that is, both 1 − 1 and onto. Exc. Let X be a set and A, B ⊆ X. Let A ∼ B if and only if A and B have same cardinality. Show that ∼ is an equivalence relation on P(X). Why suddenly we put the sets inside a set X - to avoid a logical fallacy. Russell’s paradox A barber in a city shaves only those who do not shave themselves. The questions is whether the barber shaves himself or not! 7 Same cardinality Definition. Two sets A and B are said to have same cardinality (that is, same no of elements or same size) if ∃ a function f : A → B which is bijective, that is, both 1 − 1 and onto. Exc. Let X be a set and A, B ⊆ X. Let A ∼ B if and only if A and B have same cardinality. Show that ∼ is an equivalence relation on P(X). Why suddenly we put the sets inside a set X - to avoid a logical fallacy. Russell’s paradox A barber in a city shaves only those who do not shave themselves. The questions is whether the barber shaves himself or not! 7 Same cardinality Definition. Two sets A and B are said to have same cardinality (that is, same no of elements or same size) if ∃ a function f : A → B which is bijective, that is, both 1 − 1 and onto. Exc. Let X be a set and A, B ⊆ X. Let A ∼ B if and only if A and B have same cardinality. Show that ∼ is an equivalence relation on P(X). Why suddenly we put the sets inside a set X - to avoid a logical fallacy. Russell’s paradox A barber in a city shaves only those who do not shave themselves. The questions is whether the barber shaves himself or not! 7 Finite set and cardinal number Definition. A set A is said to be finite if A is either ∅ or ∃ n ∈ N and a bijection f : In → A (or equivalently, ∃ a bijection g : A → In ). In this case, we say A has cardinality n. We say cardinality is 0 if A is an empty set. Though the earlier exercise allows us to define cardinality, there might be one problem with this definition: a set might have two different cardinalities!!! (well-definedness) BUT, this is not possible! 8 Finite set and cardinal number Definition. A set A is said to be finite if A is either ∅ or ∃ n ∈ N and a bijection f : In → A (or equivalently, ∃ a bijection g : A → In ). In this case, we say A has cardinality n. We say cardinality is 0 if A is an empty set. Though the earlier exercise allows us to define cardinality, there might be one problem with this definition: a set might have two different cardinalities!!! (well-definedness) BUT, this is not possible! 8 Finite set and cardinal number Definition. A set A is said to be finite if A is either ∅ or ∃ n ∈ N and a bijection f : In → A (or equivalently, ∃ a bijection g : A → In ). In this case, we say A has cardinality n. We say cardinality is 0 if A is an empty set. Though the earlier exercise allows us to define cardinality, there might be one problem with this definition: a set might have two different cardinalities!!! (well-definedness) BUT, this is not possible! 8 A Lemma Lemma Suppose n ∈ N and A has cardinality n. Then A is non-empty, and if a is an element of A, then the set A \ {a} has cardinality n − 1. Proof. A is non-empty as there is no bijection (function) from a non-empty set to an empty set. Let g : A → In be a bijection. As g(a) ∈ N and g is 1 − 1, the either g(x) < g(a) or g(x) > g(a). Define h : A \ {a} → In−1 by ( g(x), if g(x) < g(a), h(x) = g(x) − 1, if g(x) > g(a). 9 A Lemma Lemma Suppose n ∈ N and A has cardinality n. Then A is non-empty, and if a is an element of A, then the set A \ {a} has cardinality n − 1. Proof. A is non-empty as there is no bijection (function) from a non-empty set to an empty set. Let g : A → In be a bijection. As g(a) ∈ N and g is 1 − 1, the either g(x) < g(a) or g(x) > g(a). Define h : A \ {a} → In−1 by ( g(x), if g(x) < g(a), h(x) = g(x) − 1, if g(x) > g(a). 9 Proof ctd. Note h is 1 − 1 as if h(y) = h(z) = i, then for i < g(a), g(y) = g(z) gives y = z and if i ≥ g(a) (this case may not appear as well), g(y) − 1 = g(z) − 1 gives y = z. h is onto since for i < g(a), h−1 (i) = x if g(x) = i and for i ≥ g(a), h−1 (i) = x if g(x) = i + 1. 10 Proof ctd. Note h is 1 − 1 as if h(y) = h(z) = i, then for i < g(a), g(y) = g(z) gives y = z and if i ≥ g(a) (this case may not appear as well), g(y) − 1 = g(z) − 1 gives y = z. h is onto since for i < g(a), h−1 (i) = x if g(x) = i and for i ≥ g(a), h−1 (i) = x if g(x) = i + 1. 10 Uniqueness of cardinality Proposition Let A be a set with cardinality n. Then A can not have any other cardinality, that is, if there is another bijection between Im and A, then m = n. Proof. Induction on n. Suppose n = 1. If there exist a bijection from Im for some m, then there is a bijection f from Im to In. So if m > 1, f (1) = f (m) = 1 contradicts that f is 1 − 1. Hence m = 1. Induction hypothesis: the statement is true for n = k. Let n = k + 1. Suppose it has cardinality m as well. Then A is non-empty and for a ∈ A, the set A \ {a} has cardinality k and m − 1. By induction hyothesis, k = m − 1 and hence, we are done. 11 Uniqueness of cardinality Proposition Let A be a set with cardinality n. Then A can not have any other cardinality, that is, if there is another bijection between Im and A, then m = n. Proof. Induction on n. Suppose n = 1. If there exist a bijection from Im for some m, then there is a bijection f from Im to In. So if m > 1, f (1) = f (m) = 1 contradicts that f is 1 − 1. Hence m = 1. Induction hypothesis: the statement is true for n = k. Let n = k + 1. Suppose it has cardinality m as well. Then A is non-empty and for a ∈ A, the set A \ {a} has cardinality k and m − 1. By induction hyothesis, k = m − 1 and hence, we are done. 11 Uniqueness of cardinality Proposition Let A be a set with cardinality n. Then A can not have any other cardinality, that is, if there is another bijection between Im and A, then m = n. Proof. Induction on n. Suppose n = 1. If there exist a bijection from Im for some m, then there is a bijection f from Im to In. So if m > 1, f (1) = f (m) = 1 contradicts that f is 1 − 1. Hence m = 1. Induction hypothesis: the statement is true for n = k. Let n = k + 1. Suppose it has cardinality m as well. Then A is non-empty and for a ∈ A, the set A \ {a} has cardinality k and m − 1. By induction hyothesis, k = m − 1 and hence, we are done. 11 Well Ordering Principle in N Theorem Every non-empty subset of N has a least element. Proof. Let A ⊆ N be a non-empty subset. Proof by contradiction. Suppose A doesn’t have a least element. Consider S = N \ A. We shall show S = N. We will use induction. 1 ∈ S, otherwise A has a least element. Induction hypothesis: {1,... , k} ⊆ S k + 1 ∈ S. By induction, S = N contradiction to the fact that A is non-empty. 12 Well Ordering Principle in N Theorem Every non-empty subset of N has a least element. Proof. Let A ⊆ N be a non-empty subset. Proof by contradiction. Suppose A doesn’t have a least element. Consider S = N \ A. We shall show S = N. We will use induction. 1 ∈ S, otherwise A has a least element. Induction hypothesis: {1,... , k} ⊆ S k + 1 ∈ S. By induction, S = N contradiction to the fact that A is non-empty. 12 Well Ordering Principle in N Theorem Every non-empty subset of N has a least element. Proof. Let A ⊆ N be a non-empty subset. Proof by contradiction. Suppose A doesn’t have a least element. Consider S = N \ A. We shall show S = N. We will use induction. 1 ∈ S, otherwise A has a least element. Induction hypothesis: {1,... , k} ⊆ S k + 1 ∈ S. By induction, S = N contradiction to the fact that A is non-empty. 12 Well Ordering Principle in N Theorem Every non-empty subset of N has a least element. Proof. Let A ⊆ N be a non-empty subset. Proof by contradiction. Suppose A doesn’t have a least element. Consider S = N \ A. We shall show S = N. We will use induction. 1 ∈ S, otherwise A has a least element. Induction hypothesis: {1,... , k} ⊆ S k + 1 ∈ S. By induction, S = N contradiction to the fact that A is non-empty. 12 Well Ordering Principle in N Theorem Every non-empty subset of N has a least element. Proof. Let A ⊆ N be a non-empty subset. Proof by contradiction. Suppose A doesn’t have a least element. Consider S = N \ A. We shall show S = N. We will use induction. 1 ∈ S, otherwise A has a least element. Induction hypothesis: {1,... , k} ⊆ S k + 1 ∈ S. By induction, S = N contradiction to the fact that A is non-empty. 12 Well Ordering Principle in N Theorem Every non-empty subset of N has a least element. Proof. Let A ⊆ N be a non-empty subset. Proof by contradiction. Suppose A doesn’t have a least element. Consider S = N \ A. We shall show S = N. We will use induction. 1 ∈ S, otherwise A has a least element. Induction hypothesis: {1,... , k} ⊆ S k + 1 ∈ S. By induction, S = N contradiction to the fact that A is non-empty. 12 Well Ordering Principle in N Theorem Every non-empty subset of N has a least element. Proof. Let A ⊆ N be a non-empty subset. Proof by contradiction. Suppose A doesn’t have a least element. Consider S = N \ A. We shall show S = N. We will use induction. 1 ∈ S, otherwise A has a least element. Induction hypothesis: {1,... , k} ⊆ S k + 1 ∈ S. By induction, S = N contradiction to the fact that A is non-empty. 12 Well Ordering Principle in N Theorem Every non-empty subset of N has a least element. Proof. Let A ⊆ N be a non-empty subset. Proof by contradiction. Suppose A doesn’t have a least element. Consider S = N \ A. We shall show S = N. We will use induction. 1 ∈ S, otherwise A has a least element. Induction hypothesis: {1,... , k} ⊆ S k + 1 ∈ S. By induction, S = N contradiction to the fact that A is non-empty. 12 Well Ordering Principle in N Theorem Every non-empty subset of N has a least element. Proof. Let A ⊆ N be a non-empty subset. Proof by contradiction. Suppose A doesn’t have a least element. Consider S = N \ A. We shall show S = N. We will use induction. 1 ∈ S, otherwise A has a least element. Induction hypothesis: {1,... , k} ⊆ S k + 1 ∈ S. By induction, S = N contradiction to the fact that A is non-empty. 12 Well Ordering Principle in N Theorem Every non-empty subset of N has a least element. Proof. Let A ⊆ N be a non-empty subset. Proof by contradiction. Suppose A doesn’t have a least element. Consider S = N \ A. We shall show S = N. We will use induction. 1 ∈ S, otherwise A has a least element. Induction hypothesis: {1,... , k} ⊆ S k + 1 ∈ S. By induction, S = N contradiction to the fact that A is non-empty. 12 Interesting Proposition Let us denote cardinality of a set A by |A|. Proposition If f : A → Im is 1 − 1, then A is finite and |A| ≤ m. Proof. By well ordering principle, let m1 := min f (a). a∈A Clearly, m1 ≥ 1. Then consider m2 := min f (A) \ {m1 } = min{y : y ∈ f (A) such that y ̸= m1 }. Since f is 1 − 1, we have m2 ≥ 2. 13 Interesting Proposition Let us denote cardinality of a set A by |A|. Proposition If f : A → Im is 1 − 1, then A is finite and |A| ≤ m. Proof. By well ordering principle, let m1 := min f (a). a∈A Clearly, m1 ≥ 1. Then consider m2 := min f (A) \ {m1 } = min{y : y ∈ f (A) such that y ̸= m1 }. Since f is 1 − 1, we have m2 ≥ 2. 13 Interesting Proposition Let us denote cardinality of a set A by |A|. Proposition If f : A → Im is 1 − 1, then A is finite and |A| ≤ m. Proof. By well ordering principle, let m1 := min f (a). a∈A Clearly, m1 ≥ 1. Then consider m2 := min f (A) \ {m1 } = min{y : y ∈ f (A) such that y ̸= m1 }. Since f is 1 − 1, we have m2 ≥ 2. 13 Interesting Proposition Let us denote cardinality of a set A by |A|. Proposition If f : A → Im is 1 − 1, then A is finite and |A| ≤ m. Proof. By well ordering principle, let m1 := min f (a). a∈A Clearly, m1 ≥ 1. Then consider m2 := min f (A) \ {m1 } = min{y : y ∈ f (A) such that y ̸= m1 }. Since f is 1 − 1, we have m2 ≥ 2. 13 Interesting Proposition Let us denote cardinality of a set A by |A|. Proposition If f : A → Im is 1 − 1, then A is finite and |A| ≤ m. Proof. By well ordering principle, let m1 := min f (a). a∈A Clearly, m1 ≥ 1. Then consider m2 := min f (A) \ {m1 } = min{y : y ∈ f (A) such that y ̸= m1 }. Since f is 1 − 1, we have m2 ≥ 2. 13 Interesting Proposition Let us denote cardinality of a set A by |A|. Proposition If f : A → Im is 1 − 1, then A is finite and |A| ≤ m. Proof. By well ordering principle, let m1 := min f (a). a∈A Clearly, m1 ≥ 1. Then consider m2 := min f (A) \ {m1 } = min{y : y ∈ f (A) such that y ̸= m1 }. Since f is 1 − 1, we have m2 ≥ 2. 13 Interesting Proposition Let us denote cardinality of a set A by |A|. Proposition If f : A → Im is 1 − 1, then A is finite and |A| ≤ m. Proof. By well ordering principle, let m1 := min f (a). a∈A Clearly, m1 ≥ 1. Then consider m2 := min f (A) \ {m1 } = min{y : y ∈ f (A) such that y ̸= m1 }. Since f is 1 − 1, we have m2 ≥ 2. 13 Proof continued So at k-th step, we have mk ≥ k such that mk := min f (A) \ {m1 ,... , mk−1 }. We claim that ∃ ℓ such that f (A) = {m1 ,... , mℓ } with ℓ ≤ m. Otherwise, if ℓ > m, then mℓ ≥ ℓ > m contradicts mℓ ∈ Im. Define g : A → Iℓ by g(a) = i if f (a) = mi. Clearly, g is a bijection and hence A is a finite set with |A| ≤ m. Corollary If there exists a 1 − 1 map f : In → Im , then n ≤ m, that is, if n > m, then there is no 1 − 1 map from In into Im 14 Proof continued So at k-th step, we have mk ≥ k such that mk := min f (A) \ {m1 ,... , mk−1 }. We claim that ∃ ℓ such that f (A) = {m1 ,... , mℓ } with ℓ ≤ m. Otherwise, if ℓ > m, then mℓ ≥ ℓ > m contradicts mℓ ∈ Im. Define g : A → Iℓ by g(a) = i if f (a) = mi. Clearly, g is a bijection and hence A is a finite set with |A| ≤ m. Corollary If there exists a 1 − 1 map f : In → Im , then n ≤ m, that is, if n > m, then there is no 1 − 1 map from In into Im 14 Proof continued So at k-th step, we have mk ≥ k such that mk := min f (A) \ {m1 ,... , mk−1 }. We claim that ∃ ℓ such that f (A) = {m1 ,... , mℓ } with ℓ ≤ m. Otherwise, if ℓ > m, then mℓ ≥ ℓ > m contradicts mℓ ∈ Im. Define g : A → Iℓ by g(a) = i if f (a) = mi. Clearly, g is a bijection and hence A is a finite set with |A| ≤ m. Corollary If there exists a 1 − 1 map f : In → Im , then n ≤ m, that is, if n > m, then there is no 1 − 1 map from In into Im 14 Proof continued So at k-th step, we have mk ≥ k such that mk := min f (A) \ {m1 ,... , mk−1 }. We claim that ∃ ℓ such that f (A) = {m1 ,... , mℓ } with ℓ ≤ m. Otherwise, if ℓ > m, then mℓ ≥ ℓ > m contradicts mℓ ∈ Im. Define g : A → Iℓ by g(a) = i if f (a) = mi. Clearly, g is a bijection and hence A is a finite set with |A| ≤ m. Corollary If there exists a 1 − 1 map f : In → Im , then n ≤ m, that is, if n > m, then there is no 1 − 1 map from In into Im 14 Proof continued So at k-th step, we have mk ≥ k such that mk := min f (A) \ {m1 ,... , mk−1 }. We claim that ∃ ℓ such that f (A) = {m1 ,... , mℓ } with ℓ ≤ m. Otherwise, if ℓ > m, then mℓ ≥ ℓ > m contradicts mℓ ∈ Im. Define g : A → Iℓ by g(a) = i if f (a) = mi. Clearly, g is a bijection and hence A is a finite set with |A| ≤ m. Corollary If there exists a 1 − 1 map f : In → Im , then n ≤ m, that is, if n > m, then there is no 1 − 1 map from In into Im 14 Proof continued So at k-th step, we have mk ≥ k such that mk := min f (A) \ {m1 ,... , mk−1 }. We claim that ∃ ℓ such that f (A) = {m1 ,... , mℓ } with ℓ ≤ m. Otherwise, if ℓ > m, then mℓ ≥ ℓ > m contradicts mℓ ∈ Im. Define g : A → Iℓ by g(a) = i if f (a) = mi. Clearly, g is a bijection and hence A is a finite set with |A| ≤ m. Corollary If there exists a 1 − 1 map f : In → Im , then n ≤ m, that is, if n > m, then there is no 1 − 1 map from In into Im 14 The proposition on onto Proposition If f : In → A is onto, then A is finite and |A| ≤ n. Proof. Define g : A → In by setting g(a) = min f −1 (a) = min x. x∈In :f (x)=a Then g is 1 − 1 map as g(a1 ) = g(a2 ) implies a1 = f (x) = a2 , and we are done by the previous proposition. Note that in the proof above it is not neccessary to choose the minimum, you can choose exactly one from the pre-image set f −1 (a) for each a ∈ A. Corollary If there exists a onto map f : In → Im , then m ≤ n, that is, if m > n, then there is no onto map from In to Im. 15 The proposition on onto Proposition If f : In → A is onto, then A is finite and |A| ≤ n. Proof. Define g : A → In by setting g(a) = min f −1 (a) = min x. x∈In :f (x)=a Then g is 1 − 1 map as g(a1 ) = g(a2 ) implies a1 = f (x) = a2 , and we are done by the previous proposition. Note that in the proof above it is not neccessary to choose the minimum, you can choose exactly one from the pre-image set f −1 (a) for each a ∈ A. Corollary If there exists a onto map f : In → Im , then m ≤ n, that is, if m > n, then there is no onto map from In to Im. 15 The proposition on onto Proposition If f : In → A is onto, then A is finite and |A| ≤ n. Proof. Define g : A → In by setting g(a) = min f −1 (a) = min x. x∈In :f (x)=a Then g is 1 − 1 map as g(a1 ) = g(a2 ) implies a1 = f (x) = a2 , and we are done by the previous proposition. Note that in the proof above it is not neccessary to choose the minimum, you can choose exactly one from the pre-image set f −1 (a) for each a ∈ A. Corollary If there exists a onto map f : In → Im , then m ≤ n, that is, if m > n, then there is no onto map from In to Im. 15 The proposition on onto Proposition If f : In → A is onto, then A is finite and |A| ≤ n. Proof. Define g : A → In by setting g(a) = min f −1 (a) = min x. x∈In :f (x)=a Then g is 1 − 1 map as g(a1 ) = g(a2 ) implies a1 = f (x) = a2 , and we are done by the previous proposition. Note that in the proof above it is not neccessary to choose the minimum, you can choose exactly one from the pre-image set f −1 (a) for each a ∈ A. Corollary If there exists a onto map f : In → Im , then m ≤ n, that is, if m > n, then there is no onto map from In to Im. 15 The proposition on onto Proposition If f : In → A is onto, then A is finite and |A| ≤ n. Proof. Define g : A → In by setting g(a) = min f −1 (a) = min x. x∈In :f (x)=a Then g is 1 − 1 map as g(a1 ) = g(a2 ) implies a1 = f (x) = a2 , and we are done by the previous proposition. Note that in the proof above it is not neccessary to choose the minimum, you can choose exactly one from the pre-image set f −1 (a) for each a ∈ A. Corollary If there exists a onto map f : In → Im , then m ≤ n, that is, if m > n, then there is no onto map from In to Im. 15 The proposition on onto Proposition If f : In → A is onto, then A is finite and |A| ≤ n. Proof. Define g : A → In by setting g(a) = min f −1 (a) = min x. x∈In :f (x)=a Then g is 1 − 1 map as g(a1 ) = g(a2 ) implies a1 = f (x) = a2 , and we are done by the previous proposition. Note that in the proof above it is not neccessary to choose the minimum, you can choose exactly one from the pre-image set f −1 (a) for each a ∈ A. Corollary If there exists a onto map f : In → Im , then m ≤ n, that is, if m > n, then there is no onto map from In to Im. 15 Cardinal arithmetic Exc. If A is a finite set and B ⊆ A, then B is finite and |B| ≤ |A|. Hint. Consider the inclusion map of B tp A and compose it with the bijec- tion of A to In. Exc. If A is a finite set and B is a proper subset of A, then |B| < |A|. Hint. ∃ a ∈ A such that B ⊆ A \ {a}. Exc. If A is a finite set, then |A ∪ {a}| = |A| + 1. Exc. If A, B are finite sets, then |A ∪ B| = |A| + |B| − |A ∩ B|. 16 Cardinal arithmetic Exc. If A is a finite set and B ⊆ A, then B is finite and |B| ≤ |A|. Hint. Consider the inclusion map of B tp A and compose it with the bijec- tion of A to In. Exc. If A is a finite set and B is a proper subset of A, then |B| < |A|. Hint. ∃ a ∈ A such that B ⊆ A \ {a}. Exc. If A is a finite set, then |A ∪ {a}| = |A| + 1. Exc. If A, B are finite sets, then |A ∪ B| = |A| + |B| − |A ∩ B|. 16 Cardinal arithmetic Exc. If A is a finite set and B ⊆ A, then B is finite and |B| ≤ |A|. Hint. Consider the inclusion map of B tp A and compose it with the bijec- tion of A to In. Exc. If A is a finite set and B is a proper subset of A, then |B| < |A|. Hint. ∃ a ∈ A such that B ⊆ A \ {a}. Exc. If A is a finite set, then |A ∪ {a}| = |A| + 1. Exc. If A, B are finite sets, then |A ∪ B| = |A| + |B| − |A ∩ B|. 16 Infinite set Infinite set Definition. A set is infinite if it is not finite. Now - an example of an infinite set. Theorem N is infinite. Proof. Proof by contradiction. Suppose ∃ a bijection from f : In → N for some n ∈ N. Let M := max{f (1),... , f (n)}. But then the natural number M + 1 ∈ / f (In ) contradicting that f is a bijection. Theorem The set of prime numbers is infinite. 17 Infinite set Definition. A set is infinite if it is not finite. Now - an example of an infinite set. Theorem N is infinite. Proof. Proof by contradiction. Suppose ∃ a bijection from f : In → N for some n ∈ N. Let M := max{f (1),... , f (n)}. But then the natural number M + 1 ∈ / f (In ) contradicting that f is a bijection. Theorem The set of prime numbers is infinite. 17 Infinite set Definition. A set is infinite if it is not finite. Now - an example of an infinite set. Theorem N is infinite. Proof. Proof by contradiction. Suppose ∃ a bijection from f : In → N for some n ∈ N. Let M := max{f (1),... , f (n)}. But then the natural number M + 1 ∈ / f (In ) contradicting that f is a bijection. Theorem The set of prime numbers is infinite. 17 Infinite set Definition. A set is infinite if it is not finite. Now - an example of an infinite set. Theorem N is infinite. Proof. Proof by contradiction. Suppose ∃ a bijection from f : In → N for some n ∈ N. Let M := max{f (1),... , f (n)}. But then the natural number M + 1 ∈ / f (In ) contradicting that f is a bijection. Theorem The set of prime numbers is infinite. 17 Infinite set Definition. A set is infinite if it is not finite. Now - an example of an infinite set. Theorem N is infinite. Proof. Proof by contradiction. Suppose ∃ a bijection from f : In → N for some n ∈ N. Let M := max{f (1),... , f (n)}. But then the natural number M + 1 ∈ / f (In ) contradicting that f is a bijection. Theorem The set of prime numbers is infinite. 17 Infinite set Definition. A set is infinite if it is not finite. Now - an example of an infinite set. Theorem N is infinite. Proof. Proof by contradiction. Suppose ∃ a bijection from f : In → N for some n ∈ N. Let M := max{f (1),... , f (n)}. But then the natural number M + 1 ∈ / f (In ) contradicting that f is a bijection. Theorem The set of prime numbers is infinite. 17 The first type of infinity Theorem A set A is an infinite set if and only if ∃ a 1 − 1 map f : N → A. Proof. (Only if) If A is an infinite set, then there exist a 1 − 1 map f : N → A. Choose an element from A, name it a1 and define f (1) = a1. Choose ak ∈ A \ {a1 ,... , ak−1 } (we can do so as A is infinite) and define f (k) = ak. (If) Suppose A is not infinite, then f (N) ⊆ A is finite. Since f : N → f (N) is a bijection, we have N finite - a contradiction. 18 The first type of infinity Theorem A set A is an infinite set if and only if ∃ a 1 − 1 map f : N → A. Proof. (Only if) If A is an infinite set, then there exist a 1 − 1 map f : N → A. Choose an element from A, name it a1 and define f (1) = a1. Choose ak ∈ A \ {a1 ,... , ak−1 } (we can do so as A is infinite) and define f (k) = ak. (If) Suppose A is not infinite, then f (N) ⊆ A is finite. Since f : N → f (N) is a bijection, we have N finite - a contradiction. 18 The first type of infinity Theorem A set A is an infinite set if and only if ∃ a 1 − 1 map f : N → A. Proof. (Only if) If A is an infinite set, then there exist a 1 − 1 map f : N → A. Choose an element from A, name it a1 and define f (1) = a1. Choose ak ∈ A \ {a1 ,... , ak−1 } (we can do so as A is infinite) and define f (k) = ak. (If) Suppose A is not infinite, then f (N) ⊆ A is finite. Since f : N → f (N) is a bijection, we have N finite - a contradiction. 18 The first type of infinity Theorem A set A is an infinite set if and only if ∃ a 1 − 1 map f : N → A. Proof. (Only if) If A is an infinite set, then there exist a 1 − 1 map f : N → A. Choose an element from A, name it a1 and define f (1) = a1. Choose ak ∈ A \ {a1 ,... , ak−1 } (we can do so as A is infinite) and define f (k) = ak. (If) Suppose A is not infinite, then f (N) ⊆ A is finite. Since f : N → f (N) is a bijection, we have N finite - a contradiction. 18 The first type of infinity Theorem A set A is an infinite set if and only if ∃ a 1 − 1 map f : N → A. Proof. (Only if) If A is an infinite set, then there exist a 1 − 1 map f : N → A. Choose an element from A, name it a1 and define f (1) = a1. Choose ak ∈ A \ {a1 ,... , ak−1 } (we can do so as A is infinite) and define f (k) = ak. (If) Suppose A is not infinite, then f (N) ⊆ A is finite. Since f : N → f (N) is a bijection, we have N finite - a contradiction. 18 The first type of infinity Theorem A set A is an infinite set if and only if ∃ a 1 − 1 map f : N → A. Proof. (Only if) If A is an infinite set, then there exist a 1 − 1 map f : N → A. Choose an element from A, name it a1 and define f (1) = a1. Choose ak ∈ A \ {a1 ,... , ak−1 } (we can do so as A is infinite) and define f (k) = ak. (If) Suppose A is not infinite, then f (N) ⊆ A is finite. Since f : N → f (N) is a bijection, we have N finite - a contradiction. 18 The first type of infinity Theorem A set A is an infinite set if and only if ∃ a 1 − 1 map f : N → A. Proof. (Only if) If A is an infinite set, then there exist a 1 − 1 map f : N → A. Choose an element from A, name it a1 and define f (1) = a1. Choose ak ∈ A \ {a1 ,... , ak−1 } (we can do so as A is infinite) and define f (k) = ak. (If) Suppose A is not infinite, then f (N) ⊆ A is finite. Since f : N → f (N) is a bijection, we have N finite - a contradiction. 18 Countable set Definition. A set A is said to be countably infinite or just countable if it has same cardinality with N, that is, ∃ a bijection between N and A. A set is called atmost countable if it is finite or countable. An infinite set is called uncountable if it is not countable. The previous Theorem says that every infinite set contains a countable subset. 19 Countable set Definition. A set A is said to be countably infinite or just countable if it has same cardinality with N, that is, ∃ a bijection between N and A. A set is called atmost countable if it is finite or countable. An infinite set is called uncountable if it is not countable. The previous Theorem says that every infinite set contains a countable subset. 19 Countable set Definition. A set A is said to be countably infinite or just countable if it has same cardinality with N, that is, ∃ a bijection between N and A. A set is called atmost countable if it is finite or countable. An infinite set is called uncountable if it is not countable. The previous Theorem says that every infinite set contains a countable subset. 19 Countable set Definition. A set A is said to be countably infinite or just countable if it has same cardinality with N, that is, ∃ a bijection between N and A. A set is called atmost countable if it is finite or countable. An infinite set is called uncountable if it is not countable. The previous Theorem says that every infinite set contains a countable subset. 19 Examples of countable sets Obviously, N is countable. N \ {1} is countable as f : N → N \ {1} given by f (n) = n + 1 is a bijection - example of first departure from finite set - a proper subset having the same cardinality with the set itself. 2N - the set of even numbers - countable: f : N → 2N given by f (n) = 2n is a bijection. 20 Examples of countable sets Obviously, N is countable. N \ {1} is countable as f : N → N \ {1} given by f (n) = n + 1 is a bijection - example of first departure from finite set - a proper subset having the same cardinality with the set itself. 2N - the set of even numbers - countable: f : N → 2N given by f (n) = 2n is a bijection. 20 Examples of countable sets Obviously, N is countable. N \ {1} is countable as f : N → N \ {1} given by f (n) = n + 1 is a bijection - example of first departure from finite set - a proper subset having the same cardinality with the set itself. 2N - the set of even numbers - countable: f : N → 2N given by f (n) = 2n is a bijection. 20 Examples of countable sets Obviously, N is countable. N \ {1} is countable as f : N → N \ {1} given by f (n) = n + 1 is a bijection - example of first departure from finite set - a proper subset having the same cardinality with the set itself. 2N - the set of even numbers - countable: f : N → 2N given by f (n) = 2n is a bijection. 20 First observation Theorem A set is infinite if and only if it has a proper subset with same cardinality to itself. Proof. Note if a set is finite then it can not have same cardinality with any of its proper subset. So contrapositively, we have the if part. (Only if) Let A be an infinite set. We have already seen that ∃ a 1 − 1 map from f : N → A. Let f (n) = an. Define g : A → A \ {a1 } by ( x, if x ∈ A \ {a1 , a2 ,... , an...}, g(x) = an+1 , if x = an for some n ∈ N. g is a bijection. 21 First observation Theorem A set is infinite if and only if it has a proper subset with same cardinality to itself. Proof. Note if a set is finite then it can not have same cardinality with any of its proper subset. So contrapositively, we have the if part. (Only if) Let A be an infinite set. We have already seen that ∃ a 1 − 1 map from f : N → A. Let f (n) = an. Define g : A → A \ {a1 } by ( x, if x ∈ A \ {a1 , a2 ,... , an...}, g(x) = an+1 , if x = an for some n ∈ N. g is a bijection. 21 First observation Theorem A set is infinite if and only if it has a proper subset with same cardinality to itself. Proof. Note if a set is finite then it can not have same cardinality with any of its proper subset. So contrapositively, we have the if part. (Only if) Let A be an infinite set. We have already seen that ∃ a 1 − 1 map from f : N → A. Let f (n) = an. Define g : A → A \ {a1 } by ( x, if x ∈ A \ {a1 , a2 ,... , an...}, g(x) = an+1 , if x = an for some n ∈ N. g is a bijection. 21 First observation Theorem A set is infinite if and only if it has a proper subset with same cardinality to itself. Proof. Note if a set is finite then it can not have same cardinality with any of its proper subset. So contrapositively, we have the if part. (Only if) Let A be an infinite set. We have already seen that ∃ a 1 − 1 map from f : N → A. Let f (n) = an. Define g : A → A \ {a1 } by ( x, if x ∈ A \ {a1 , a2 ,... , an...}, g(x) = an+1 , if x = an for some n ∈ N. g is a bijection. 21 First observation Theorem A set is infinite if and only if it has a proper subset with same cardinality to itself. Proof. Note if a set is finite then it can not have same cardinality with any of its proper subset. So contrapositively, we have the if part. (Only if) Let A be an infinite set. We have already seen that ∃ a 1 − 1 map from f : N → A. Let f (n) = an. Define g : A → A \ {a1 } by ( x, if x ∈ A \ {a1 , a2 ,... , an...}, g(x) = an+1 , if x = an for some n ∈ N. g is a bijection. 21 First observation Theorem A set is infinite if and only if it has a proper subset with same cardinality to itself. Proof. Note if a set is finite then it can not have same cardinality with any of its proper subset. So contrapositively, we have the if part. (Only if) Let A be an infinite set. We have already seen that ∃ a 1 − 1 map from f : N → A. Let f (n) = an. Define g : A → A \ {a1 } by ( x, if x ∈ A \ {a1 , a2 ,... , an...}, g(x) = an+1 , if x = an for some n ∈ N. g is a bijection. 21 First observation Theorem A set is infinite if and only if it has a proper subset with same cardinality to itself. Proof. Note if a set is finite then it can not have same cardinality with any of its proper subset. So contrapositively, we have the if part. (Only if) Let A be an infinite set. We have already seen that ∃ a 1 − 1 map from f : N → A. Let f (n) = an. Define g : A → A \ {a1 } by ( x, if x ∈ A \ {a1 , a2 ,... , an...}, g(x) = an+1 , if x = an for some n ∈ N. g is a bijection. 21 2nd observation Theorem Any infinite subset of N is countable. Proof. Let A be an infinite subset of N. Thus, we can construct mk ≥ k such that mk := min A \ {m1 ,... , mk−1 }. Define f : N → A by f (k) = mk. Clearly, f is 1 − 1. To prove f onto, we need to show that for each a ∈ A ∃ n such that a = mn. Note A ∩ Ik ⊆ {m1 ,... , mk }. Since a ∈ N, there exist a natural number N such that a ≤ N (?). So a ∈ A ∩ IN and hence we are done. Exc. Any subset of a countable set is atmost countable. 22 2nd observation Theorem Any infinite subset of N is countable. Proof. Let A be an infinite subset of N. Thus, we can construct mk ≥ k such that mk := min A \ {m1 ,... , mk−1 }. Define f : N → A by f (k) = mk. Clearly, f is 1 − 1. To prove f onto, we need to show that for each a ∈ A ∃ n such that a = mn. Note A ∩ Ik ⊆ {m1 ,... , mk }. Since a ∈ N, there exist a natural number N such that a ≤ N (?). So a ∈ A ∩ IN and hence we are done. Exc. Any subset of a countable set is atmost countable. 22 2nd observation Theorem Any infinite subset of N is countable. Proof. Let A be an infinite subset of N. Thus, we can construct mk ≥ k such that mk := min A \ {m1 ,... , mk−1 }. Define f : N → A by f (k) = mk. Clearly, f is 1 − 1. To prove f onto, we need to show that for each a ∈ A ∃ n such that a = mn. Note A ∩ Ik ⊆ {m1 ,... , mk }. Since a ∈ N, there exist a natural number N such that a ≤ N (?). So a ∈ A ∩ IN and hence we are done. Exc. Any subset of a countable set is atmost countable. 22 2nd observation Theorem Any infinite subset of N is countable. Proof. Let A be an infinite subset of N. Thus, we can construct mk ≥ k such that mk := min A \ {m1 ,... , mk−1 }. Define f : N → A by f (k) = mk. Clearly, f is 1 − 1. To prove f onto, we need to show that for each a ∈ A ∃ n such that a = mn. Note A ∩ Ik ⊆ {m1 ,... , mk }. Since a ∈ N, there exist a natural number N such that a ≤ N (?). So a ∈ A ∩ IN and hence we are done. Exc. Any subset of a countable set is atmost countable. 22 2nd observation Theorem Any infinite subset of N is countable. Proof. Let A be an infinite subset of N. Thus, we can construct mk ≥ k such that mk := min A \ {m1 ,... , mk−1 }. Define f : N → A by f (k) = mk. Clearly, f is 1 − 1. To prove f onto, we need to show that for each a ∈ A ∃ n such that a = mn. Note A ∩ Ik ⊆ {m1 ,... , mk }. Since a ∈ N, there exist a natural number N such that a ≤ N (?). So a ∈ A ∩ IN and hence we are done. Exc. Any subset of a countable set is atmost countable. 22 2nd observation Theorem Any infinite subset of N is countable. Proof. Let A be an infinite subset of N. Thus, we can construct mk ≥ k such that mk := min A \ {m1 ,... , mk−1 }. Define f : N → A by f (k) = mk. Clearly, f is 1 − 1. To prove f onto, we need to show that for each a ∈ A ∃ n such that a = mn. Note A ∩ Ik ⊆ {m1 ,... , mk }. Since a ∈ N, there exist a natural number N such that a ≤ N (?). So a ∈ A ∩ IN and hence we are done. Exc. Any subset of a countable set is atmost countable. 22 2nd observation Theorem Any infinite subset of N is countable. Proof. Let A be an infinite subset of N. Thus, we can construct mk ≥ k such that mk := min A \ {m1 ,... , mk−1 }. Define f : N → A by f (k) = mk. Clearly, f is 1 − 1. To prove f onto, we need to show that for each a ∈ A ∃ n such that a = mn. Note A ∩ Ik ⊆ {m1 ,... , mk }. Since a ∈ N, there exist a natural number N such that a ≤ N (?). So a ∈ A ∩ IN and hence we are done. Exc. Any subset of a countable set is atmost countable. 22 2nd observation Theorem Any infinite subset of N is countable. Proof. Let A be an infinite subset of N. Thus, we can construct mk ≥ k such that mk := min A \ {m1 ,... , mk−1 }. Define f : N → A by f (k) = mk. Clearly, f is 1 − 1. To prove f onto, we need to show that for each a ∈ A ∃ n such that a = mn. Note A ∩ Ik ⊆ {m1 ,... , mk }. Since a ∈ N, there exist a natural number N such that a ≤ N (?). So a ∈ A ∩ IN and hence we are done. Exc. Any subset of a countable set is atmost countable. 22 2nd observation Theorem Any infinite subset of N is countable. Proof. Let A be an infinite subset of N. Thus, we can construct mk ≥ k such that mk := min A \ {m1 ,... , mk−1 }. Define f : N → A by f (k) = mk. Clearly, f is 1 − 1. To prove f onto, we need to show that for each a ∈ A ∃ n such that a = mn. Note A ∩ Ik ⊆ {m1 ,... , mk }. Since a ∈ N, there exist a natural number N such that a ≤ N (?). So a ∈ A ∩ IN and hence we are done. Exc. Any subset of a countable set is atmost countable. 22 2nd observation Theorem Any infinite subset of N is countable. Proof. Let A be an infinite subset of N. Thus, we can construct mk ≥ k such that mk := min A \ {m1 ,... , mk−1 }. Define f : N → A by f (k) = mk. Clearly, f is 1 − 1. To prove f onto, we need to show that for each a ∈ A ∃ n such that a = mn. Note A ∩ Ik ⊆ {m1 ,... , mk }. Since a ∈ N, there exist a natural number N such that a ≤ N (?). So a ∈ A ∩ IN and hence we are done. Exc. Any subset of a countable set is atmost countable. 22 Adjoining an element Take x a new element, N ∪ {x} is countable: f : N → N ∪ {x} given by f (1) = x and f (n) = n − 1, n ≥ 2, is a bijection. Similarly if A is a countable set, then A ∪ {x} is countable. If f : N → A is a bijection and f (n) = an , then A = {a1 ,... , an ,...}. The map g : N → A ∪ {x} defined by g(1) = x and g(n) = an−1 for n ≥ 2, is a bijection. 23 Adjoining an element Take x a new element, N ∪ {x} is countable: f : N → N ∪ {x} given by f (1) = x and f (n) = n − 1, n ≥ 2, is a bijection. Similarly if A is a countable set, then A ∪ {x} is countable. If f : N → A is a bijection and f (n) = an , then A = {a1 ,... , an ,...}. The map g : N → A ∪ {x} defined by g(1) = x and g(n) = an−1 for n ≥ 2, is a bijection. 23 Adjoining an element Take x a new element, N ∪ {x} is countable: f : N → N ∪ {x} given by f (1) = x and f (n) = n − 1, n ≥ 2, is a bijection. Similarly if A is a countable set, then A ∪ {x} is countable. If f : N → A is a bijection and f (n) = an , then A = {a1 ,... , an ,...}. The map g : N → A ∪ {x} defined by g(1) = x and g(n) = an−1 for n ≥ 2, is a bijection. 23 Hilbert’s hotel 24 Hilbert’s hotel 25 Union of countable sets Can we accommodate any finite no. of people? Clearly, for a countable set A, the set A ∪ {x1 , x2 ,... , xk } is countable,since we have the bijection g(i) = xi for 1 ≤ i ≤ k and g(n) = an−k for n ≥ k + 1. What if a countable no. of people come? Evidently, this question boils down to whether union of two countable set is countable! 26 Union of countable sets Can we accommodate any finite no. of people? Clearly, for a countable set A, the set A ∪ {x1 , x2 ,... , xk } is countable,since we have the bijection g(i) = xi for 1 ≤ i ≤ k and g(n) = an−k for n ≥ k + 1. What if a countable no. of people come? Evidently, this question boils down to whether union of two countable set is countable! 26 Union of countable sets Can we accommodate any finite no. of people? Clearly, for a countable set A, the set A ∪ {x1 , x2 ,... , xk } is countable,since we have the bijection g(i) = xi for 1 ≤ i ≤ k and g(n) = an−k for n ≥ k + 1. What if a countable no. of people come? Evidently, this question boils down to whether union of two countable set is countable! 26 Union of countable sets Can we accommodate any finite no. of people? Clearly, for a countable set A, the set A ∪ {x1 , x2 ,... , xk } is countable,since we have the bijection g(i) = xi for 1 ≤ i ≤ k and g(n) = an−k for n ≥ k + 1. What if a countable no. of people come? Evidently, this question boils down to whether union of two countable set is countable! 26 Union of countable sets Can we accommodate any finite no. of people? Clearly, for a countable set A, the set A ∪ {x1 , x2 ,... , xk } is countable,since we have the bijection g(i) = xi for 1 ≤ i ≤ k and g(n) = an−k for n ≥ k + 1. What if a countable no. of people come? Evidently, this question boils down to whether union of two countable set is countable! 26 Finite union of countable sets Theorem If A and B are countable sets, then A ∪ B is a countable set. Proof. Without loss of generality (WLOG) one can assume A = {a1 , a2 ,... , an ,...} and B = {b1 , b2 ,... , bn ,...}. The map g : N → A ∪ B given by ( ak , if n = 2k for some k ∈ N, g(n) = bk , if n = 2k − 1 for some k ∈ N. is a bijection. Are we missing something? N ∪ {0}, Z = −N ∪ {0} ∪ N are countable. 27 Finite union of countable sets Theorem If A and B are countable sets, then A ∪ B is a countable set. Proof. Without loss of generality (WLOG) one can assume A = {a1 , a2 ,... , an ,...} and B = {b1 , b2 ,... , bn ,...}. The map g : N → A ∪ B given by ( ak , if n = 2k for some k ∈ N, g(n) = bk , if n = 2k − 1 for some k ∈ N. is a bijection. Are we missing something? N ∪ {0}, Z = −N ∪ {0} ∪ N are countable. 27 Finite union of countable sets Theorem If A and B are countable sets, then A ∪ B is a countable set. Proof. Without loss of generality (WLOG) one can assume A = {a1 , a2 ,... , an ,...} and B = {b1 , b2 ,... , bn ,...}. The map g : N → A ∪ B given by ( ak , if n = 2k for some k ∈ N, g(n) = bk , if n = 2k − 1 for some k ∈ N. is a bijection. Are we missing something? N ∪ {0}, Z = −N ∪ {0} ∪ N are countable. 27 Finite union of countable sets Theorem If A and B are countable sets, then A ∪ B is a countable set. Proof. Without loss of generality (WLOG) one can assume A = {a1 , a2 ,... , an ,...} and B = {b1 , b2 ,... , bn ,...}. The map g : N → A ∪ B given by ( ak , if n = 2k for some k ∈ N, g(n) = bk , if n = 2k − 1 for some k ∈ N. is a bijection. Are we missing something? N ∪ {0}, Z = −N ∪ {0} ∪ N are countable. 27 Finite union of countable sets Theorem If A and B are countable sets, then A ∪ B is a countable set. Proof. Without loss of generality (WLOG) one can assume A = {a1 , a2 ,... , an ,...} and B = {b1 , b2 ,... , bn ,...}. The map g : N → A ∪ B given by ( ak , if n = 2k for some k ∈ N, g(n) = bk , if n = 2k − 1 for some k ∈ N. is a bijection. Are we missing something? N ∪ {0}, Z = −N ∪ {0} ∪ N are countable. 27 Some more observations Corollary Finite union of countable sets is countable. Exc. For any infinite set A and a countable set B, the sets A and A ∪ B are of same cardinality. Hint. Let {a1 , a2 ,... , an...} ⊆ A. Consider the map g : A → A ∪ B given by  x, if x ∈ A \ {a1 , a2 ,... , an...},   g(x) = ak , if x = a2k for some k ∈ N,   k b , if x = a 2k−1 for some k ∈ N. 28 Some more observations Corollary Finite union of countable sets is countable. Exc. For any infinite set A and a countable set B, the sets A and A ∪ B are of same cardinality. Hint. Let {a1 , a2 ,... , an...} ⊆ A. Consider the map g : A → A ∪ B given by  x, if x ∈ A \ {a1 , a2 ,... , an...},   g(x) = ak , if x = a2k for some k ∈ N,   k b , if x = a 2k−1 for some k ∈ N. 28 Some more observations Corollary Finite union of countable sets is countable. Exc. For any infinite set A and a countable set B, the sets A and A ∪ B are of same cardinality. Hint. Let {a1 , a2 ,... , an...} ⊆ A. Consider the map g : A → A ∪ B given by  x, if x ∈ A \ {a1 , a2 ,... , an...},   g(x) = ak , if x = a2k for some k ∈ N,   k b , if x = a 2k−1 for some k ∈ N. 28 Countable union Theorem Countable union of countable sets is countable. Proof. WLOG, let A1 , A2 ,... , An ,... be a countable family of countable sets. Also let WLOG A1 = {a11 , a12 ,... , a1n,...} A2 = {a21 , a12 ,... , a2n,...}....... · · ·.. · · · An = {an1 , an2 ,... , ann,...}....... · · ·.. · · · ∞ [ Let A = Ai. i=1 Case I. Ai ∩ Aj = ∅ for all i ̸= j. 29 Countable union Theorem Countable union of countable sets is countable. Proof. WLOG, let A1 , A2 ,... , An ,... be a countable family of countable sets. Also let WLOG A1 = {a11 , a12 ,... , a1n,...} A2 = {a21 , a12 ,... , a2n,...}....... · · ·.. · · · An = {an1 , an2 ,... , ann,...}....... · · ·.. · · · ∞ [ Let A = Ai. i=1 Case I. Ai ∩ Aj = ∅ for all i ̸= j. 29 Countable union Theorem Countable union of countable sets is countable. Proof. WLOG, let A1 , A2 ,... , An ,... be a countable family of countable sets. Also let WLOG A1 = {a11 , a12 ,... , a1n,...} A2 = {a21 , a12 ,... , a2n,...}....... · · ·.. · · · An = {an1 , an2 ,... , ann,...}....... · · ·.. · · · ∞ [ Let A = Ai. i=1 Case I. Ai ∩ Aj = ∅ for all i ̸= j. 29 Countable union Theorem Countable union of countable sets is countable. Proof. WLOG, let A1 , A2 ,... , An ,... be a countable family of countable sets. Also let WLOG A1 = {a11 , a12 ,... , a1n,...} A2 = {a21 , a12 ,... , a2n,...}....... · · ·.. · · · An = {an1 , an2 ,... , ann,...}....... · · ·.. · · · ∞ [ Let A = Ai. i=1 Case I. Ai ∩ Aj = ∅ for all i ̸= j. 29 Proof idea 30 Idea of bijection 31 Tweak a little for explicit bijection 32 The bijection Note that [ m(m − 1) m(m + 1) N= ( , ] 2 2 m∈N and that this union is disjoint. Also note that the arrows are like slanting lines joining (1, m) to (m, 1) with any point (r, s) of the m points lying on it satisfies r + s = m + 1. So given n ∈ N, ∃ m such that m(m − 1) m(m + 1)