Lecture 2: Cantor’s Theory of Cardinality (Size)

18.100A: Complete Lecture Notes Lecture 2: Cantor’s Theory of Cardinality (Size) Functions If A and B are sets, a function f : A → B is a mapping that assigns each x ∈ A to a unique element in B denoted f (x). Let f : A → B. Then 1. If C ⊂ A, we define f (C) := {y ∈ B | y ∈ f (x) for some x ∈ C}. 2. If D ⊂ B, we define f −1 (D) := {x ∈ A | f (x) ∈ D}. As an example, consider the following mapping f : {1, 2, 3, 4} → {a, b}: We can categorize functions in 3 important ways. Let f : A → B. 1. f is injective or one-to-one (1-1) if f (x1 ) = f (x2 ) =⇒ x1 = x2 . 2. f is surjective or onto if f (A) = B. 3. f is bijective if it is 1-1 and onto. If a function f : A → B is bijective, then f −1 : B → A is the function which assigns each y ∈ B to the unique x ∈ A such that f (x) = y. Note that f (f −1 (x)) = x. Cardinality Question 1. When do two sets have the same size? Cantor answered this question in the 1800s, stating that two sets have the same size when you can pair each element in one set with a unique element in the other. Definition 2 (Cardinality) We state that two sets A and B have the same cardinality if there exists a bijection f : A → B. With this new concept comes some new notation: 1. |A| = |B| if A and B have the same cardinality. 2. |A| = n if |A| = |{1, . . . , n}|. If this is the case we say A is finite. 1 3. |A| ≤ |B| if there exists an injection f : A → B. 4. |A| < |B| if |A| ≤ |B| but |A| 6= |B|. Theorem 3 (Cantor-Schröder-Bernstein) If |A| ≤ |B| and |B| ≤ |A| then |A| = |B|. If |A| = |N|, then A is countably infinite. If A is finite or countably infinite, we say A is countable. Otherwise, we say A is uncountable. Example 4 There are a few key theorems that we can prove with this new concept: 1. |{2n | n ∈ N}| = |N|. 2. |{2n − 1 | n ∈ N}| = |N|. 3. |{x ∈ Q | x > 0}| = |N|. The first two statements can be summarized by Feynman: "There are twice as many numbers as numbers." Proof : 1. Define the function f : N → {2n | n ∈ N} as f (n) = 2n. Then, f is 1-1– if f (n) = f (m) then 2n = 2m =⇒ n = m. Furthermore, f is also onto, as if m ∈ {2n | n ∈ N} then ∃n ∈ N such that m = 2n = f (n). 2. The second statement can be proven similarly. 3. This is left as an exercise to the reader in Assignment 1.  2