Lecture 3: Cantor’s Remarkable Theorem and the Rationals’ Lack of the Least Upper Bound Property

18.100A: Complete Lecture Notes Lecture 3: Cantor’s Remarkable Theorem and the Rationals’ Lack of the Least Upper Bound Property Question 1. Is anything bigger than N? If A is a set then P(A) = {B | B ⊂ A}. Here are a few examples: 1. A = ∅ then P(A) = {∅}. 2. A = {1}, then P(A) = {∅, {1}}. 3. A = {1, 2}, then P(A) = {∅, {1}, {2}, {1, 2}}. In general, if |A| = n then |P(A)| = 2n . This is why we call P(A) the power set of A. Theorem 2 (Cantor) If A is a set, then |A| < |P(A)|. Remark 3. Therefore, N < |P(N)| < |P(P(N))| < . . . . Hence, there are an infinite number of infinite sets. Proof : Define the function f : A → P(A) by f (x) = {x}. Then, f is 1-1– as if {x} = {y} =⇒ x = y. Thus, |A| ≤ |P(A)|. To finish the proof now all we need to show is that |A| = 6 |P(A)|. We will do so through contradiction. Suppose that |A| = |P(A)|. Then, there exists a surjection g : A → P(A). Let B := {x ∈ A | x ∈ / g(x)} ∈ P(A). Since g is surjective, there exists a b ∈ A such that g(b) = B. There are two cases: 1. b ∈ B. If this is the case, then b ∈ / g(b) = B =⇒ b ∈ / B. 2. b ∈ / B. If this is the case, then b ∈ / g(b) = B =⇒ b ∈ B. In either case we obtain a contradiction. Thus, g is not surjective =⇒ |A| = 6 |P(A)|. Remark 4. This is another proof method: casework. If the conclusion for every case is true, then the conclusion must be true. Corollary 5 For all n ∈ N ∪ {0}, n < 2n . Remark 6. This can also be shown by induction, see Assignment 1. 1 Real Numbers Remark 7. In a sense, to be made precise, the set of real numbers is the unique set with all of the algebraic and ordering properties of the rational numbers, but none of the holes. Problem 8 Now let’s try to precisely describe R. We will start by stating what our end result will be, and then we will derive it: Theorem 9 (Real Numbers (R)) There exists a unique ordered field containing Q with the least upper bound property. We denote this field by R. Ordered Sets & Fields Definition 10 (Ordered set) An ordered set is a set S with a relation < called an "ordering" such that 1. ∀x, y ∈ S either x < y, y < x, or x = y. 2. If x < y and y < z then x < z. Here are a few examples and one non-example: • Z is an ordered set, with the relation that m > n ⇐⇒ m − n ∈ N. • Q is an ordered set, with the relation that p > q ⇐⇒ ∃m, n ∈ N such that p − q = • Q × Q is an ordered set with the relation (q, r) > (s, t) ⇐⇒ q > s or q = s and r > t. • Consider the set P(N). Let A, B ∈ P(N) and let A ≺ B if A ⊂ B. This is NOT an ordered set– it doesn’t satisfy the first property of an ordered set. m n. Definition 11 (Bounded Above/Below) Let S be an ordered set and let E ⊂ S. Then, 1. If there exists a b ∈ S such that x ≤ b for all x ∈ E, then E is bounded above and b is an vocab of E. 2. If ∃c ∈ S such that x ≥ c for all x ∈ E, then E is bounded below and c is a lower bound of E. From here, there are some very important definitions in real analysis. We say that b0 is the least upper bound, or the supremum of E if A) b0 is an upper bound for E and B) if b is an upper bound for E then b0 ≤ b. We denote this as b0 = sup E. Similarly, we say that c0 is the greatest lower bound, or the infinimum of E if A) c0 is a lower bound for E and B) if c is a lower bound for E then c < c0 . We denote this as c0 = inf E. 2 Example 12 Here are a few examples of infimums and supremums: • S = Z and E = {−2, −1, 0, 1, 2}. Then, inf E = −2 and sup E = 2. • But, note that the supremum nor the infimum need to be in E. Consider the sets S = Q and E = {q ∈ Q | 0 ≤ q < 1}. Then, inf E = 0 ∈ E, but sup E = 1 ∈ / E. • Furthermore, neither the supremum nor the infimum need exist. Consider the sets S = Z and E = N. Then, inf E = 1, but sup E does not exist as there is not an integer greater than all natural numbers. Definition 13 (Least Upper Bound Property) An ordered set S has the least upper bound property if every E ⊂ S which is nonempty and bounded above has a supremum in S. One example of such a set is −N = {−1, −2. − 3. . . . }. Then, E ⊂ S is bounded above if and only if −E ⊂ N is bounded below. By the well-ordering principle, −E has a least element x ∈ −E, and thus −x = sup E. We will now show that Q does not have the least upper bound property. Theorem 14 If x ∈ Q and x = sup{q ∈ Q | q > 0, q 2 < 2} then x > 0 and x2 = 2. Proof : Let E equal the set on the right hand side, and suppose x ∈ Q such that x = sup E. Then, since 1 ∈ E and x is an upper bound for E, 1 ≤ x =⇒ x > 0. n o 2−x2 We now prove that x2 ≥ 2. Suppose that x2 < 2. Define h = min 21 , 2(2x+1) < 1. Then, if x2 < 2 then h > 0. We now prove that x + h ∈ E. Indeed, (x + h)2 = x2 + 2xh + h2 < x2 + h(2x + 1) as h < 1. Hence (x + h)2 ≤ x2 + (2 − x2 ) · 2x + 1 2(2x + 1) 2 − x2 2 2−2 <2+ 2 = 2. = x2 + Therefore, x + h ∈ E and x + h > x =⇒ x is not an upper bound for E. Therefore, x 6= sup E which is a contradiction. Hence, x2 ≥ 2. 3 We now prove that x2 ≤ 2. Suppose x2 > 2. Let h = show that x − h is an upper bound for E. We have x2 −2 2x . Hence, if x2 > 2 then h > 0 and x − h > 0. We will (x − h)2 = x2 − 2xh + h2 = x2 − (x2 − 2) + h2 = 2 + h2 > 2. Let q ∈ E. Then, q 2 < 2 < (x − h)2 =⇒ (x − h)2 − q 2 > 0. Hence, ((x − h) + q)((x − h) + q) > 0 =⇒ (x − h) − q > 0. Thus, for all q ∈ E, q < x − h < x =⇒ x 6= sup E. This is a contradiction. Therefore, x2 = 2. Theorem 15 The set E = {q ∈ Q | q > 0 and q 2 < 2} does not have a supremum in Q. Proof : Suppose there exists an x ∈ Q such that x = sup E. Then, by our previous theorem, x2 = 2. In particular, note that x > 1 as otherwise x ≤ 1 =⇒ 2 = x2 < 12 . Thus, ∃m, n ∈ N such that m > n and x = m n . Therefore, ∃n ∈ N such that nx ∈ N. Let S = {k ∈ N | kx ∈ N}. Then, S 6= ∅ since n ∈ S. By the well-ordering property of N, S has a least element k0 ∈ S. Let k1 = k0 x − k0 ∈ Z. Then, k1 = k0 (x − 1) > 0 since k0 ∈ N and x > 1. Therefore, k1 ∈ N. Now x2 = 2 =⇒ x < 2, as otherwise x2 > 4 > 2. Thus, k1 = k0 (x − 1) < k0 (2 − 1) = k0 . So, k1 ∈ N and k1 < k0 =⇒ k1 ∈ / S as k0 is the least element of S. But, xk1 = k0 x2 − xk0 = 2k0 − xk0 = k0 − k1 ∈ N =⇒ k1 ∈ S. This is a contradiction. Thus, 6 ∃x ∈ Q such that x = sup E. Q is an example of a field, which we will start to discuss in the next lecture. 4