Lecture 6: The Uncountabality of the Real Numbers

18.100A: Complete Lecture Notes Lecture 6: The Uncountabality of the Real Numbers Theorem 1 (Triangle Inequality) ∀x, y ∈ R, |x + y| ≤ |x| + |y|. Proof : Let x, y ∈ R. Then, x + y ≤ |x| + |y| and (−x) + (−y) ≤ | − x| + | − y| = |x| + |y|. Therefore, −(|x| + |y|) ≤ x + y ≤ |x| + |y|. Hence, |x + y| ≤ |x| + |y| by our previous theorem. Remark 2. We may denote the Triangle Inequality with 4-inequality as a shorthand. Question 3. As we showed in Assignment 1, we know that Q is countable. Is the set of real numbers countable? Recall 4 Recall that a set A is countable if A is either finite or |A| = |N|. We can think of Q as decimal expansions. In other words, we can think of a rational number x as being in the form x = 10k dk + · · · + 10d1 + d0 + 10−1 d−1 + · · · + 10−M d−M with di ∈ {0, 1, 2, 3, . . . , 9}. We may write x = dk dk−1 . . . d1 d0 • d−1 . . . d−M where • is the decimal point. The same can be said about real numbers if we allow for infinite decimal expansions. Definition 5 Let x ∈ (0, 1] and let d−j ∈ {0, 1, . . . , 9}. We say that x is represented by the digits {d−j | j ∈ N}, i.e. x = 0 • d−1 d−2 . . . , if x = sup{10−1 d−1 + 10−2 d−2 + · · · + 10−n d−n | n ∈ N}. Here is an example: .2500 = sup{2 · 10−1 , 2 · 10−1 + 5 · 10−2 , 2 · 10−1 + 5 · 10−2 + 0 · 10−3 , . . . }. Notice here that  after a while the previous set becomes 41 repeating. Hence, we have .2500 = sup 15 , 14 = 14 . 1 Theorem 6 For every x ∈ (0, 1], there exists a unique sequence of digits d−j such that x = 0 • d−1 d−2 . . . and 0 • d−1 d−2 . . . d−n < x ≤ 0 • d−1 d−2 . . . d−n + 10−n . Furthermore, for every set of digits {d−j | j ∈ N}, there exists a unique x ∈ [0, 1] such that x = 0 • d−1 . . . . Notice however that the representative of 1 2 is 0.4999 . . . . Theorem 7 (Cantor) (0,1] is uncountable. Proof : We will prove this through contradiction. Suppose that (0, 1] is countable. Therefore, there exists a bijection x : N → (0, 1]. We now construct a y ∈ (0, 1] such that y is not in the range of x. We write (n) (n) x(n) = 0 • d−1 d−2 . . . . These are not exponents! This is the setn of digits foroa given n ∈ N. In other words, x takes in a natural number (n) n and maps it to the sequence of digits d−j | n ∈ N . Let e−j  1, = 2, (j) d−j 6= 1 (j) . d−j = 1 Let y = 0 • e−1 e−2 . . . . Then, ∀n ∈ N, 0 • e−1 e−2 . . . e−n ≤ y0 • e−1 . . . e−n + 10−n (n) since all e−j s are positive. Thus, 0•e−1 . . . is the unique decimal expansion of y. However, for all n ∈ N, d−n 6= e−n . Therefore, ∀n, x(n) 6= y. This is a contradiction, and thus (0, 1] is uncountable. So (0, 1] ⊂ R is uncountable! Corollary 8 The set of real numbers, R, is uncountable. Sequences and Series Remark 9. Analysis is the study of limits. Sequences and Limits Definition 10 (Sequence of Reals) A sequence of real numbers is a function x : N → R. We denote x(n) = xn and we denote the sequence by {xn }∞ n=1 , {xn }, or x1 , x2 , . . . . Definition 11 A sequence {xn } is bounded if ∃B ≥ 0 such that ∀n, |xn | ≤ B. 2 One example of a bounded sequence is xn = 1 n, since 1 n ≤ 1 for all n ∈ N. However, xn = n is not bounded. Remark 12. A sequence is different from a set! For example, −1, 1, −1, 1, · · · = {(−1)n }∞ n=1 , while {(−1)n | n ∈ N} = {−1, 1}. Definition 13 (Sequence Convergence of Reals) A sequence {xn } converges to x ∈ R if ∀ > 0, ∃M ∈ N such that ∀n ≥ M , |xn − x| < . A sequence that converges is said to be convergent, and otherwise is said to be divergent. We can also define divergence as the negation of convergent. Negation 14 (Not Convergent) The sequence {xn } is not convergent, or divergent if ∃0 > 0 such that ∀M ∈ N, ∃n ≥ M so that |xn − x| ≥ 0 . We now prove two theorems: Theorem 15 If {xn } converges for x and y, then x = y. In other words, limits of convergent sequences of real numbers are unique. Theorem 16 Let x, y ∈ R. If ∀ > 0, |x − y| < , then x = y. Proof : We first prove the second theorem. Suppose that x 6= y. Then, |x − y| > 0. Hence, choosing  = |x−y| 2 , we have |x − y| |x − y| |x − y| ≤ =⇒ <0 2 2 which is a contradiction. Using this we prove the former theorem. Suppose xn converges to x and to y. We will show that for all  > 0, |x − y| < . Firstly, given xn → x, for  > 0 there exists an N1 ∈ N such that ∀n ≥ N1 , |xn − x| <  . 2 Then, given xn → y, for  > 0 there exists an N2 ∈ N such that ∀n ≥ N2 , |xn − y| <  . 2 Let N = max{N1 , N2 }. Then, for all  > 0 there exists an N = max{N1 , N2 } such that for all n ≥ N , |x − y| ≤ |x − xn | + |xn − y| < 3   + = 2 2 by the Triangle Inequality. Hence, for all  > 0, |x − y| < . Therefore, x = y. Notation 17 We write x = limn→∞ xn or xn → x. Example 18 Given the sequence xn = c ∀n, limn→∞ xn = c. Proof : Let  > 0 and M = 1. Thus, for all n ≥ 1, |xn − c| = |c − c| = 0 < .  Example 19 limn→∞ 1 n = 0. Proof : Let  > 0. Choose M ∈ N such that M −1 > −1 . Hence, for all n ≥ M , 4 1 n −0 = 1 n ≤ 1 M ≤ .