Lecture 1: Sets, Set Operations, and Mathematical Induction

18.100A: Complete Lecture Notes Lecture 1: Sets, Set Operations, and Mathematical Induction For this class, we will be using the book Introduction to Real Analysis, Volume I by Jir̆í Lebl [L]. I will use  to end proofs of examples, and to end proofs of theorems. Basic Set Theory Remark 1. There are two main goals of this class: 1. Gain experience with proofs. 2. Prove statements about real numbers, functions, and limits. Sets A set is a collection of objects called elements or members of that set. The empty set (denoted ∅) is the set with no elements. There are a few symbols that are super helpful to know as a shorthand, and will be used throughout the course. Let S be a set. Then • a ∈ S means that "a is an element in S." • ∃ means "there exists." • a∈ / S means that "a is not an element in S." • ∃! means "there exists a unique." • ∀ means "for all." • =⇒ means "implies." • := means "define." • ⇐⇒ means "if and only if." Definition 2 (Set Relations) We want to relate different sets, and thus we get the following notation/definitions: 1. A set A is a subset of B, A ⊂ B, if every element of A is in B. Given A ⊂ B, if a ∈ A =⇒ a ∈ B. 2. Two sets A and B are equal, A = B, if A ⊂ B and B ⊂ A. 3. A set A is a proper subset of B, A ( B if A ⊂ B and A 6= B. One way we can describe a set is using "set building notation". We write {x ∈ A | P (x)} or {x | P (x)} to mean "all x ∈ A that satisfies property P (x)". One example of this would be {x | x is an even number}. There are a few key sets that we will use throughout this class: 1. The set of natural numbers: N = {1, 2, 3, 4, . . . }. 2. The set of integers: Z = {0, 1, −1, 2, −2, 3, −3, . . . }. 1 3. The set of rational numbers: Q = { m n | m, n ∈ Z and n 6= 0}. 4. The set of real numbers: R. It follows that N ⊂ Z ⊂ Q ⊂ R. The fourth item on this list brings us to an important question, and the first goal of our course: Problem 3 How do we describe R? We will answer this question in Lectures 3 and 4. In the meantime, let’s continue our study of sets and proof methods. Given sets A and B, we have the following definitions: 1. The union of A and B is the set A ∪ B = {x | x ∈ A or x ∈ B}. 2. The intersection of A and B is the set A ∩ B = {x | x ∈ A and x ∈ B}. 3. The set difference of A and B is the set A \ B = {x ∈ A | x ∈ / B}. / A}. 4. The complement of A is the set Ac = {x | x ∈ 5. A and B are disjoint if A ∩ B = ∅. Theorem 4 (De Morgan’s Laws) If A, B, C are sets then 1. (B ∪ C)c = B c ∩ C c , 2. (B ∩ C)c = B c ∪ C c , 3. A \ (B ∪ C) = (A \ B) ∩ (A \ C), 4. and A \ (B ∩ C) = (A \ B) ∪ (A \ C). We will prove the first statement to give an example of how such a proof would go, but the rest will be left to you. Proof : Let B, C be sets. We must prove that (B ∪ C)c ⊂ B c ∩ C c and B c ∩ C c ⊂ (B ∪ C)c . If x ∈ (B ∪ C)c =⇒ x ∈ / B ∪ C =⇒ x ∈ / B and x ∈ / C. Hence, x ∈ B c and x ∈ C c =⇒ x ∈ B c ∩ C c . Thus, (B ∪ C)c ⊂ B c ∩ C c . 2 If x ∈ B c ∩ C c then x ∈ B c and x ∈ C c =⇒ x ∈ / B and x ∈ / C. Hence, x ∈ / B ∪ C =⇒ x ∈ (B ∪ C)c . Thus, B c ∩ C c ⊂ (B ∪ C)c . Mathematical Induction We will now talk about some of the biggest proof methods there are. Firstly, note that N = {1, 2, 3, . . . } has an ordering (as 1 < 2 < 3 < . . . ). Axiom 5 (Well-ordering property) The well-ordering property of N states that if S ⊂ N then there exists an x ∈ S such that x ≤ y for all y ∈ S. In other words, there is always a smallest element. Note that this is an axiom, and thus we have to assume this without proof. Theorem 6 (Induction) This concept was invented by Pascal in 1665. Let P (n) be a statement depending on n ∈ N. Assume that 1. (Base case) P (1) is true and 2. (Inductive step) if P (m) is true then P (m + 1) is true. Then, P (n) is true for all n ∈ N. Proof : Let S = {n ∈ N | P (n) is not true}. We wish to show that S = ∅. We will prove this by contradiction. Remark 7. When we prove something by contradiction, we assume the conclusion we want is false, and then show that we will reach a false statement. Rules of logic thus imply that the initial statement must be false. Thus in this case, we will assume S 6= ∅ and derive a false statement. Suppose that S 6= ∅. Then, by the well-ordering property of N, S has a least element m ∈ S. Since P (1) is true, m 6= 1, i.e. m > 1. Since m is a least element, m − 1 ∈ / S =⇒ P (m − 1) is true. This implies that P (m) is true =⇒ m ∈ / S by assumption. But then m ∈ S and m ∈ / S. This is a contradiction. Thus S = ∅ and hence P (n) is true for all n ∈ N. Let’s see an example of induction in action. Theorem 8 For all c 6= 1 in the real numbers, and for all n ∈ N, 1 + c + c2 + · · · + cn = 1 − cn+1 . 1−c Proof : We will prove this by induction. First, we prove the base case (n = 1). The left hand side of the 2 (1−c)(1+c) equation is 1 + c for n = 1. The right hand side is 1−c = 1 + c. Hence, the base case has been shown. 1−c = 1−c Assume that the equation is true for k ∈ N, in other words 1 + c + c2 + · · · + ck = 3 1 − ck+1 . 1−c Thus, =⇒ 1 + c + c2 + · · · + ck + ck+1 = (1 + c + c2 + · · · + ck ) + ck+1 1 − ck+1 + ck+1 1−c 1 − ck+1 + ck+1 (1 − c) = (1 − c) = = 1 − c(k+1)+1 . 1−c Therefore, our proof is complete. Let’s do another example: Theorem 9 For all c ≥ −1, (1 + c)n ≥ 1 + nc for all n ∈ N. Proof : We prove this through induction. In the base case, we have: (1 + c)1 = 1 + 1 · c. For the inductive step, suppose that (1 + c)m ≥ 1 + mc. Then, (1 + c)m+1 = (1 + c)m · (1 + c). By assumption, ≥ (1 + mc) · (1 + c) = 1 + (m + 1)c + mc2 ≥ 1 + (m + 1)c. By induction, our proof is complete. 4