Show work/explanation where indicated. Answers without any work may earn little, if any, credit. You may type or write your work in your copy of the exam, or if you prefer, create a document containing your work. Scanned work is acceptable also. 1. (10 pts) True/False. Indicate whether the statement is True or False. (no explanation required) TRUE (a) Between any two rational numbers, there is an irrational number. TRUE (b) Let r be a real number. If 3 r < 3 + for all > 0, then r = 3. TRUE (c) positive real number t, positive integer N such that integer n > N, 0 < 8/n < t. TRUE (d) If sequence (sn) converges to 0, then the sequence (1/sn) diverges to . TRUE (e) Given any set S of real numbers, every boundary point of S is either an upper bound or a lower bound of the set S. 2. (6 pts) Let A = [1, 4] and B = [3, 1]. Define function f: A B by f ( x )=12|x3| . True or False? (No explanation required.) TRUE (a) f is a surjective function. FALSE (b) f is an injective function. TRUE (c) Let T = {1, 1}. Then pre-image f 1(T) = {4, 3}. 3. (8 pts) Prove by induction: 1 1 1 1 n + + ++...+ = 6 7 7 8 8 9 ( n+5 ) (n+6) 6(n+6) for all n N. Page 1 of 11 For n 1, LHS RHS 1 1 5 1 6 1 6 7 1 42 1 6 1 6 1 6 7 1 42 Since LHS=RHS, so base step is true. Let it is true for nk 1 1 1 1 k ... 6.7 7.8 8.9 k 5 k 6 6 k 6 We have to show that it is true for For n k 1 n k 1 , Page 2 of 11 LHS 1 1 1 1 1 ... 6.7 7.8 8.9 k 5 k 6 k 6 k 7 k 1 6 k 6 k 6 k 7 k k 7 6 6 k 6 k 7 k 2 7k 6 6 k 6 k 7 k 1 k 6 6 k 6 k 7 k 1 6 k 7 RHS k 1 6 k 1 6 k 1 6 k 7 Since LHS=RHS, so result is true for n k 1 Hence by induction it is proved. 4. (16 pts) True or False? For each part: If true, prove it carefully. You can apply or cite any of our relevant definitions, theorems, examples, or exercises in a proof. If false, provide a counterexample and explain it. (a) If {An : n N} is any collection of open subsets of R, then the intersection n=1 A n is open or bounded. The statement is not true. According to Lemma, the intersection of any finite collection of open subsets of R is open. In case of infinite, it is not true. Counterexample: Suppose A1, A2, . . . , An are open sets and let A = Tn i=1 Ai . Let x A be arbitrary. Then x Ai for every i = 1, . . . , n. For each i, since Ai is open, there exists ri > 0 such that Bri (x) Ai . Let r = min{r1, r2, . . . , rn}. Then Br(x) Bri (x) Ai for all i = 1, . . . , n, and hence Br(x) A. But x A was chosen arbitrarily, and hence A is an open set. An infinite intersection of open sets is not necessarily open Page 3 of 11 (b) If (an) is any Cauchy sequence of real numbers and (bn) is any decreasing sequence of positive real numbers, then the sequence (an 5bn) converges. Since is any Cauchy sequence of real numbers, so by theorem we know that every Cauchy an sequence of real numbers converges to a limit. Since bn is any decreasing sequence of positive real numbers, so it is bounded. Then the sequence is convergent. By a limit theorem, we know the limit of the difference of two convergent sequences is the difference of their limits. So, converges. The statement is true. an 5bn Counterexample 5. (15 pts) Complete the following table. For each set, determine the infimum, minimum, maximum, and supremum (if they exist). (If there is not a finite value or it does not exist, record an X instead). Indicate whether the set is open, closed, neither, or both. (explanation optional) Set { S= 6+ (1 ) n S= n N [ n+1 :n N Infimum Minimum Maximum Supremum Open / closed/ neither / both NO NO NO NO NEITHER 4 NO NO 4 OPEN } 1 1 , 3+ n 2 n ) Page 4 of 11 0 S= n N ( 5 n4 1 , 7 n n 7 NO 7 BOTH 6. (12 pts) For each of the following sequences (sn), state whether the sequence converges or diverges. If the sequence converges, determine the limit. If the sequence diverges to or to - state the infinite limit. Show work / explanation. You may cite textbook/notes theorems, examples, and/or homework textbook exercises if relevant (by source and page numbers). s n=n3 ( 0.3 )n (a) Consider the sequence Sn n 0.3 3 Let S 0.3 n : , so Sn S n3 0.3 0.3 for 1 n So, sequence is convergent. Thus, lim n3 0.3 0 n n (b) s n= n! 100n Consider the sequence n! Sn 100n : Page 5 of 11 S n 1 n 1! 100n 1 So, n 1! n 1 S n 1 lim lim 100 n S n n! n 100n n 1! 100n n 100 n 1 n! lim lim n n 1 n ! 1 100 n ! n 1 100 n 1 lim n 100 lim n Thus, by ratio test sequence is not convergent. So, lim S n n (c) s n=n [ 2n +(2)n ] Consider the sequence If lim sn 0 x sn n[2 n (2) n ] : , the sequence diverges sn lim Sn lim n[2n ( 2) n ] n n 22 0 Hence, sequence Sn is divergent. Page 6 of 11 7. (3 pts) For each of the sequences in the previous problem, state the subsequential limits (which could be infinite). Sequence part in #6 (a) Subsequential Limits Subsequential limits =0, Limit inferior 0 Limit superior Subsequential limits =,1 Limit inferior Limit superior 1 (b) (c) Subsequential limits =-, 0 Limit inferior 0 Limit superior does not exist 8. (7 pts) Claim: If s 1=2 s n+1 =1+2 s n and for all n in N, then lim sn =1. Proof: Let s 1=2 and s n+1 =1+2 s n for all n in N. Taking the limit of both sides of the equation, we have lim s n+1=lim (1+ 2 sn ) lim s n+1=1+2 lim s n We have Call the limit s. s=1+2 s , so, solving for s, we get We conclude that lim s n=s=1 1=s . . Page 7 of 11 (a) Is the Claim true or false? Explain carefully. (b) Critique the proof. Is it complete? Does it prove the claim? What are the flaws, if any? Be very specific. 9. (8 pts) Use the definition (page 2 of the Week 3 Sequences document or page 44 of Lebl) to prove that lim n (1)n sin ( n2 ) =0 . 0.2 n Consider the limit Let 0 (1)n sin(n 2 ) lim n 0.2n if there exist a 0 : such that for 0 x x0 and f x f x0 then lim f x f x0 x Choose n0 2 , 0 n 2 So, f n f n0 2 (1) n sin( n 2 ) ( 1) sin( 2 ) 0.2n 0.2 2 ( 1) (1) n sin(n 2 ) ( 1) sin( 2 ) n 0.2 (1) 1 1 2 0.2 n ( 1) 2 n 2 0.2 n 1 2 2 n 2 n n ( 1) 2 n 2 n For n (1) n 2 2 Page 8 of 11 Hence, lim f n f n0 n f 2 2 ( 1) sin( 2 ) 0.2 ( 1) 0 0.2 0 sin 0 Therefore, (1) n sin( n 2 ) lim 0 n 0.2n Page 9 of 11 10. (7 pts) Let S be a subset of R. Claim: If int S , then S is uncountable. (Given a set S of real numbers, if its interior is a nonempty set, then the set S is uncountable.) PART (a): Fill in the blanks below, to prove the Claim. Remark: The notation and terminology refer to my notes and the textbooks which comprise our course resources. Proof: Let S be a subset of R. Suppose uncountable___________________. Then there exists some real number x int S. By definition of interior point, there is a neighborhood W of x such that W ___ S. (choose = , , or ) By definition of neighborhood, W is a bounded _uncoutable___________ interval. (choose open or closed ) Interval W has the same cardinality as the interval (0, 1), by Week 2 Homework, #_Week 2 Homework _____. The interval (0, 1) is ______uncountable______________ (choose countable or uncountable), so W must be _______uncountable_____________ (choose countable or uncountable). and since W _ __ S (choose = , , or ), S must be __uncountable_______________ (choose countable or uncountable). PART (b): State the contrapositive of the Claim. Is the contrapositive true or false? (no explanation required) 11. (8 pts) Consider the following claim. s Claim: The sequence ( n ) given by s n= n ( ) 4 converges to 0. Proof: n ( ) s = n Let 4 . The sequence of ratios n +1 s n+1 4 = = n sn 4 4 ( ) ( ) <1 converges to 4 . so by the Ratio test for sequences (Week 3 sequence notes, page 9, or Lemma 2.2.12(iii) Lebl), s the sequence ( n ) converges to 0. (a) Is the Claim true or false? Explain carefully. Page 10 of 11 From the ratio test, for given sequence Sn , if then lim n S n 1 L 1 Sn lim S n 0 .then sequence n Sn converges to zero. Given n , so 4 Sn n 1 4 Sn 1 Then n 1 lim n S n 1 Sn So, sequence 4 lim n n 4 4 lim n 4 4 3.14 1.273 1 n not converges to zero. Hence claim is false. 4 Sn (b) Critique the proof. Is it complete? Does it prove the claim? What are the flaws, if any? Be very specific. Page 11 of 11 Bounds, Supremum, Infimum, the Completeness Axiom, and the Archimedean Property Section 12: The Completeness Axiom Definitions. Let S be a subset of R. If there exists a real number m such that m s for all s S, then m is called an upper bound for S, and we say that S is bounded above. If there exists a real number m such that m s for all s S, then m is called a lower bound for S, and we say that S is bounded below. Set S is bounded if it bounded both above and below. If an upper bound m for S is an element of S, then m is called the maximum (or largest element) of S, written m = max S. If a lower bound m for S is an element of S, then m is called the minimum (or smallest element) of S, written m = min S. If S is bounded above, then the least upper bound of S is called its supremum, denoted sup S. m = sup S iff (1) m s for all s S, and (2) if m' < m, then there exists s' S such that s' > m'. In other words, sup S must be an upper bound, and no number smaller than sup S is an upper bound. Equivalent definition, page 21, Lebl book: m = sup S iff m b for all upper bounds b of set S. Note that sup S is not necessarily an element of S. If S is bounded below, then the greatest lower bound of S is called its infimum, denoted inf S. m = inf S iff (1) m s for all s S, and (2) if m' > m, then there exists s' S such that s' < m'. In other words, inf S must be a lower bound, and no number larger than sup S is a lower bound. Equivalent definition, page 21, Lebl book: m = sup S iff m b for all lower bounds b of set S. Note that inf S is not necessarily an element of S. Examples: (a) Any finite set is bounded and has both a maximum and a minimum, and those values are the supremum and infimum respectively. (b) For sets in interval notation, it is easy to determine upper/lower bounds and maxima/minima (if they exist). For instance, the interval (, 5) is bounded above but not below. There is no maximum and no minimum. The supremum is 5 but there is no infimum. Note that 5 is not the maximum because 5 is not contained in the set. (c) Any subset of a bounded set is also bounded. Page 1 of 7 Lemma. 2 is not a rational number. Proof: (by contradiction) Suppose not. Suppose\t2\tis a rational number. \u0005 Then we can write 2 = , where m and n are some integers with no common factors. \u0006 Squaring both sides, we have 2 = \u0005\u0007 . \u0006\u0007 Then m2 = 2n2, so m2 is a multiple of 2, and since 2 is prime, m must also be a multiple of 2. Therefore, m = 2k for some integer k. Squaring both sides, we have m2 = 22 k2. Substituting for m2 in m2 = 2n2, we have 22 k2 = 2n2. Therefore 2 k2 = n2. Now we can conclude that n2 is a multiple of 2, and since 2 is prime, n is multiple of 2. So, both m and n are multiples of 2. But this contradicts what we have stated earlier about m and n not having any common factors. Therefore, 2\tcannot be a rational number. Theorem. Let p be a prime number. Then \b is not a rational number. Proof: In the proof of the lemma, replace 2 by p. Example: Let T = {q Q | 0 q 2}. Considering T as a subset of R, then minimum = inf T = 0 and maximum = 2 = sup T. However, if we are looking for a least upper bound in Q (rather than R), that value does not exist. So, there is a fundamental property of real numbers not possessed by the set of rational numbers, known as the Completeness Axiom. Completeness Axiom (Least upper bound property) [See page 22 in Lebl] Every nonempty subset S of R that is bounded above has a least upper bound; i.e., sup S exists and is a real number. Analog for sets bounded below: Every nonempty subset S of R that is bounded below has a greatest lower bound; i.e., inf S exists and is a real number. Proof: Suppose S is a nonempty subset of R which has lower bound L. Then the set S = {s : s S} is a set which is bounded above by L. So, by the completeness axiom S has a supremum m. But this means set S has infimum equal to m. Therefore S has a greatest lower bound. Page 2 of 7 Theorem. Given nonempty subsets A and B of R, let set C be defined by C = {x + y | x A and y B}. If sup A and sup B exist, then sup C exists, and sup C = sup A + sup B. Proof: Suppose sup A and sup B exist, and we label them a and b respectively. We want to show that sup C = a + b by establishing that a + b is an upper bound and that a + b must be the least upper bound. Suppose z is any element of C. Then by definition of C, z = x + y for some x A and y B. Since a is an upper bound of A, we must have x a and since b is an upper bound of B, y b. so z = x + y a + b, and so a + b must be an upper bound for C. By the completeness axiom, since C is bounded above, C must have a supremum, so sup C exists (call it c), and since it is the least upper bound, c a + b. Now we want to show that c is actually equal to a + b. Since we already know c a + b, it will suffice to show that c a + b. We will use Theorem 11.7 (described in section 11 notes). Suppose > 0. Since a = sup A, a - /2 cannot be an upper bound for A, so there exists x' A such that x' > a - /2. Since b = sup b, b - /2 cannot be an upper bound for B, so there exists y' B such that y'> b - /2. Then there exists z' = x' + y' in C such that z ' = x' + y' > a + b - So, z' > a + b - for all > 0. We already know that c z' since c is the least upper bound for C. Therefore, c > a + b - for all > 0. By Theorem 11.7, we have c a + b. Theorem. Suppose D is a nonempty subset and that f: D R and g: D R. If for every, x, y D, f(x) g(y), then f(D) is bounded above and g(D) is bounded below. Furthermore, sup f(D) inf g(D). [Prop. 1.3.7, page 33, Lebl] Proof: Given any y0 in D, by hypothesis, f(x) g(y0) for all x D. So, g(y0) is an upper bound for f(D), and so the least upper bound, sup f(D), must be g(y0). But now, sup f(D) g(y0) is true for all y0 in D, so sup f(D) is a lower bound for g(D), and so, sup f(D) must be greatest lower bound of g(D), but the greatest lower bound of g(D) is inf g(D). Therefore sup f(D) inf g(D). Page 3 of 7 Archimedean property and equivalent statements [Section 1.2.2 in Lebl] Theorem. (Archimedean Property of R). The set N of natural numbers is unbounded above in R. Proof: In the Chapter 1 notes, it was proven by contradiction that there is no greatest integer. The same proof can be modified slightly to show that there is no real number greater than all the integers. Theorem. Each of the following is equivalent to the Archimedean property. (a) For each z R, there exists an n N such that n > z. (b) For each x > 0 and for each y R, there exists an n N such that nx > y. (c) For each x > 0, there exists an n N such that 0 < 1/n < x. [Th 1.2.4(a) in Lebl, p. 27] Proof: We will prove that Archimedean property (a) (b) (c) Archimedean property. Archimedean property (a) : (proof by contradiction) Suppose not. Suppose the Archimedean property holds but there exists z' R such that for all n N, n z'. Then z' would be an upper bound for N, which contradicts the Archimedean property. Therefore (a) must be true. (a) (b): Let x and y be any real numbers for which x > 0. Let z = y/x. Since x > 0 the denominator is nonzero and z exists and is a real number. By (a), there exists n N such that n > z. But then n > y/x. By multiplying both sides by positive number x, we get nx > y as desired in part (b). (b) (c): Let x be any positive real number. Let y = 1. By (b), there exists an n N such that nx > 1. By dividing both sides by positive number x, we get x > 1/n. Of course for any n N, 1/n > 0. So part (c) is established. (c) Archimedean property: (proof by contradiction) Suppose not. Suppose that (c) holds but there exists a positive real number r which is an upper bound for N. Then n r for all n N. 1/n 1/r for all n N. Let x = 1/r. Then there exists x > 0 such that for all n N, 1/n x. This contradicts (c). Therefore, the Archimedean property must be true. Page 4 of 7 Theorem. There exists a positive real number x such that x2 = 2. [Page 25, Lebl] Proof: Let S = {r R : r > 0 and r2 < 2}. Since 12 < 2, we see that 1 S, so S is nonempty. Also, for any r R, r2 < 2 < 22, so r < 2. Therefore 2 is an upper bound for S. By the completeness axiom, sup S must exist and is a real number. Denote sup S by x. Claim: x2 = 2. Suppose not. Then x2 < 2 or x2 > 2. Case of x2 < 2: We will show that this violates the fact that x = sup S. So, we will show that x2 < 2 allows us to find some y S with y > x, a contradiction of the property that x is an upper bound for S. The crux of the matter is to find that y. y must be a bit larger than x, but to be in S, we need y2 < 2. Say we let y = x + 1/n for some integer n, so y is a bit larger than x, and by choosing a large enough n, we can make y and x very close in size. Then y2 = (x + 1/n)2 = x2 + 2x/n + 1/n2 = x2 + (1/n)(2x + 1/n) and since n 1 x2 + (1/n)(2x + 1)and we want this quantity < 2. Solving the inequality x2 + (1/n)(2x + 1) < 2 results in (1/n)( 2x + 1) < 2 - x2 so 1/n < (2 - x2)/(2x + 1) 2 2 Let z = (2 - x )/(2x + 1). Since x < 2 and x > 0, we have 2 - x2 > 0 and 2x + 1 > 0, and so z > 0. By (c) of the previous theorem, there must exist n0 N such that 0 < 1/n0 < z. Therefore there exists n0 N such that y = x + 1/n0 satisfies y > x and y2 < p, so y S and is greater than the least upper bound, contradicting the fact that x is sup S. Therefore, x2 cannot be < 2. Case of x2 > 2: We follow the same sort of approach. We will show that x2 > 2 allows us to find some y < x where y is an upper bound for S. This would violate the fact that x is the least upper bound of S. Say we let y = x 1/m for some integer m, so y is a bit smaller than x, and by choosing a large enough m, we can make y and x very close in size. Then y2 = (x 1/m)2 = x2 2x/m + 1/m2 and since 1/m > 0 > x2 2x/m and we want this quantity > 2 ( so that y > r2 for all r S). Solving the inequality x2 2x/m > 2 results in x2 2 > 2x/m so 1/m < (x2 - 2)/(2x) Page 5 of 7 Let z = (x2 - 2)/(2x). Since x2 > 2 and x > 0, x2 - 2 > 0 and 2x > 0, and so z > 0. By (c) of the previous theorem, there must exist m0 N such that 0 < 1/m0 < z. Therefore there exists m0 N such that y = x 1/m0 satisfies y < x and y > 2 > r2 for all r S. So, y is less than the least upper bound, contradicting the fact that x is sup S. Therefore, x2 cannot be > 2. By the trichotomy law for ordered fields, since x2 is not < 2 and is not > 2, x2 must be = 2. Theorem. Let p be a prime number. Then there exists a positive real number x such that x2 = p. Proof: Repeat the previous proof with the role of "2" replaced by "p". Def. Suppose that S and T are two nonempty subsets of R. We say that set S is dense in T if between any two distinct numbers in T, there exists a number in S. Theorem. (Density of Q in R) Between any two real distinct numbers, there exists a rational number. More precisely, if x and y are any distinct real numbers (say that x < y), there exists a rational number q such that x < q < y. [Th 1.2.4(b) in Lebl, page 27] Proof: (by cases) Suppose x and y are real numbers with x < y. Case 1. Suppose that x > 0. Let r = 1/(y - x). Note that r > 0. By part (a) of the Archimedean theorem, there exists n N such that n > r. So, n > 1/(y - x) ny - nx > 1 ny > nx + 1, so nx + 1 < ny Since x > 0, we have nx > 0, and we can show that there exists m N such that m - 1 nx < m. (That is, nx must be trapped between two consecutive nonnegative integers.) Since m - 1 nx we have m nx + 1, and earlier we had nx + 1 < ny, so m < ny. Since nx < m, we have nx < m < ny. Dividing by n (which is a positive integer) we get x < m/n < y. Therefore we have found a rational number m/n between x and y. Case 2. Suppose that x 0. Then |x| 0. There exists positive integer k such that |x| < k. Now consider the numbers a = x + k and b = y + k. Both a and b must be positive. Apply case 1 to find a rational number q' such that a < q' < b. Substituting for a and b, we get x + k < q' < y + k. x < q' - k < y. Let q = q' - k. Since q' is rational and k is an integer, q is rational. Page 6 of 7 We have x < q < y for rational number q, which is what we wanted. Lemma: If x is any nonzero real number and y is any irrational number, then xy is irrational. Theorem. (Density of irrational numbers in R) Between any two real distinct numbers, there exists a irrational number. In other words: If x and y are real numbers with x < y, then there exists an irrational number w such that x < w < y. Proof: Suppose x and y are any two real numbers with x < y. Then and By the previous theorem, there must be a rational number q such are real numbers with that <\u000e < . < . We can assume q 0. (Otherwise, apply the theorem again to find a rational number between 0 and .) Multiplying through by\t2 , we get \u000f < \u000e2 < \u000f. By the previous lemma, since q is nonzero and rational and 2 is irrational, \u000e2\tis irrational. So, we have found an irrational number between real numbers x and y. --------------------------------Extensions of the definition of sup and inf, used in Lebl only, page 29: Definition. Let A be a subset of R. If A is empty, define sup A = and inf A = +. If A is not bounded above, define sup A = +. If A is not bounded below, define inf A = . Page 7 of 7 Cardinality Sets S and T have the same cardinality (are equinumerous), denoted S ~ T, if there exists a bijective function from S onto T. Given a collection of sets , ~ is an equivalence relation on . Then the relation ~ partitions the collection of sets into disjoint equivalence classes. For each set, associate a cardinal number representing the size of the set. A set S is finite iff S = empty or there is a bijection f: {1, 2, ..., n} S for some positive integer n. Essentially, this says that a nonempty set is finite iff we can put the elements of the set in a list of finite length, labeling one element as element #1 and another as element #2, and so on. If a set is not finite, then it is infinite. Notation: Denote {1, 2, ..., n} by In. The cardinal number of In is n, and if S ~ In, we say that S has n elements. The cardinal number of is 0. The cardinal number of an infinite set is called transfinite. A set S is denumerable iff there exists a bijection f: N S. Essentially, this says that a nonempty set is denumerable iff we can put the elements of the set in a list of infinite length, labeling one element as element #1 and another as element #2, and so on, and never ending. That is, we can enumerate the elements, using natural number subscripts. S = {s1, s2, s3, s4, ...}. A set S is countable (i.e., countably infinite) iff it is finite or denumerable. A set S is uncountable iff it is not countable. infinite sets countable sets finite sets denumerable sets uncountable sets The cardinal number of a denumerable set is denoted 0 ("Aleph zero"). Examples: N is denumerable. The identity function iN : N N is a bijection. The set of odd natural numbers S is denumerable, since f: N S defined by f(n) = 2n - 1 is a bijection. The set of integers Z is denumerable --- think of Z = {0, 1, -1, 2, -2, 3, -3, ...} so we can define a bijection f: N Z such that f(1) = 0, f(2) = 1, f(3) = -1, f(4) = 2, etc. Page 1 of 5 Example: Show that the open interval (-1, 1) and R are equinumerous. One way to do this is to find a bijection f: (-1, 1) R. Consider the following graph: Visually, notice that the graph represents a function, and since every horizontal line intersects the graph in exactly one point, the function is both injective and surjective. Therefore the function f represented by this graph appears to be a bijection f: (-1, 1) R. Can we guess the formula for this function? It has vertical asymptotes x = -1 and x = 1, and intercept (0, 0). This suggests that a rational function may work. \u0006 Let \u0001\u0002\u0003\u0004 = \u0002\u0006\u0007\b\u0004\u0002\u0006\t\b\u0004 for x (-1, 1). This function has the desired asymptotes and intercept. (Checking more points confirms that this is a likely candidate.) Let's check that this is a bijection. \u0006 \u0001\u0002\u0003\u0004 = \u0006 \b Taking the derivative and simplifying, we get \u0001 \u0002\u0003\u0004 = \u0006 \u0007\b \u0002\u0006 \b\u0004 < 0 for all x (-1, 1), so f is strictly decreasing on (-1, 1). \u0006 \u0006 Note too that lim\u0006\t\b\u0014 = and lim\u0006\b\u0016 = . \u0006 \b \u0006 \b So, f must be injective and the range must include all real numbers. Example: Closed intervals [-1, 1] and [c, d] are equinumerous. We want to find a bijection f: [-1, 1] [c, d]. Can we find a function f so that f(-1) = c and f(1) = d? Yes, a line through the points (-1, c) and (1, d) will \u0018\t\u0019 work. That line has slope \u001a . y = mx + b \u0018\t\u0019 \u001dx + b Substitute the point (1, d) to get \u001a \u0018\t\u0019 \u0018\u0007\u0019 \u001c \u001a \u001d + b. Solving for b results in \u001f = \u001a . \u001b=\u001c \u001e= \u0018\t\u0019 \u0018\t\u0007\t\u0019 Let f: (-1, 1) (c, d) defined by \u0001\u0002\u0003\u0004 = \u001c \u001a \u001d \u0003 + \u001c \u001a \u001d . This is a linear function mapping [-1, 1] onto [c, d]. Any linear function with nonzero slope must be injective. So, we have found a bijection between the two intervals. Theorem. If S is a countable set and T S, then T is countable. Theorem. Suppose S is a nonempty set. The following statements are equivalent: (a) S is countable. (b) There exists an injection f: S N (c) There exists a surjection g: N S Page 2 of 5 Additional results: (a) If S and T are nonempty countable sets, the union S T is a countable set. See book, pages 81 and 82 (diagram on page 82) (b) The Cartesian product of two countable sets is countable. (c) The set of rational numbers, Q, is countable. (d) The union of a countable family of countable sets is countable. Proof of (d): Suppose is a countable family of countable sets. Since the family is countable, we can use the natural numbers N as an index. So = {Sn | n N}, and by hypothesis, each set Sn is countable. Since S1 is countable, we can list the elements {s11, s12, s13, s14, ...}. Since S2 is countable, we can list the elements {s21, s22, s23, s24, ...} : In general, since Sn is countable, we can list the elements {sn1, sn2, sn3, sn4, ...} Now arrange the elements in a rectangular array: s12, s13, s14, ... s11, s21, s22, s23, s24, ... s31, s32, s33, s34, ... s42, s43, s44, ... s41, : We want to show how to choose a first element in the list, then the second, and so on. Follow the arrows: s11, s12, s13, s14, ... s22, s23, s24, ... s21, s31, s32, s33, s34, ... s41, s42, s43, s44, ... : The union is the set {s11, s12, s21, s31, s22, s13, s14, s23, ...} and we have now shown that the set is countable. Proof of (c): We want to show that the set of rational numbers, Q, is countable. Recall that Q = {m/n | m and n Z and n 0}. First consider Q+, the set of all positive rational numbers. Let S1 = {positive rational numbers having numerator 1} = {1/1, 1/2, 1/3, 1/4, ...}. Let S2 = {positive rational numbers having numerator 2} = {2/1, 2/2, 2/3, 2/4, ...}. Let S3 = {positive rational numbers having numerator 3} = {3/1, 3/2, 3/3, 3/4, ...}. and in general, Sn = {positive rational numbers having numerator n} = {n/1, n/2, n/3, n/4, ...}. Clearly, each set Sn is countable, and $& #$ = '\u0007 . Now we have a countable family of countable sets, so the union Q+ must be countable. Using a similar argument, Q- (the set of negative rational numbers) is countable. Since Q = Q+ U {0} U Q-, the union of three countable sets, Q must be countable. Page 3 of 5 What about R, the set of real numbers? There is a famous proof, called the Cantor diagonalization proof, which leads to the conclusion that the set of real numbers is uncountable. Georg Cantor, a late 19th century mathematician, developed ground-breaking work on the cardinality of sets, but his ideas were so revolutionary that they were controversial, and sadly, he suffered from mental illness. For more, see http://www.mathcs.org/analysis/reals/history/cantor.html and http://www-history.mcs.standrews.ac.uk/Biographies/Cantor.html Theorem. The set R of real numbers is uncountable. Proof: We will show that the open interval (0, 1) is uncountable. Since (0, 1) R, we can then conclude that R is uncountable. Claim: The open interval (0, 1) is uncountable. Proof (by contradiction): Suppose the open interval (0, 1) is countable. Then we could make a list x1, x2, x3, ... of the elements, producing a one-to-one correspondence between the natural numbers and the real numbers between 0 and 1. Note that any real number between 0 and 1 can be expressed as decimal value with an infinite decimal expansion involving digits 0 through 9. (In the case of a terminating decimal, all digits beyond a certain point are 0. Some numbers, such as 0.50000000000 and 0.499999999... have more than one representation). So, we can write our list as x1 = 0.a11 a12 a13 a14 ... x2 = 0.a21 a22 a23 a24 ... x3 = 0.a31 a32 a33 a34 ... x4 = 0.a41 a42 a43 a44 ... x5 = 0.a51 a52 a53 a54 ... : Now we construct a real number y = 0.b1 b2 b3 b4 ... between 0 and 1 as follows: x1 = 0.a11 a12 a13 a14 ... x2 = 0.a21 a22 a23 a24 ... x3 = 0.a31 a32 a33 a34 ... x4 = 0.a41 a42 a43 a44 ... : To determine b1, look at a11. If a11 = 2, we set b1 = 3; otherwise we set b1 = 2. To determine b2, look at a22. If a22 = 2, we set b2 = 3; otherwise we set b2 = 2. Continuing in same way, we define bn as follows: \u001f$ = ( 3, +\u0001\t,$$ = 2/ 2, +\u0001\t,$$ 2 Now let's compare y = 0.b1 b2 b3 b4 ... with the numbers in the list. Is y = x1? No, because the first digits b1 and a11 are different. Is y = x2? No, because second digits b2 and a22 are different. Continuing in the same way, comparing y and xn, we see that they are not equal because the nth digits bn and ann do not match. Page 4 of 5 Therefore, we have constructed a number y which is not in our list of all the real numbers between 0 and 1! But that list was supposed to include all of the real numbers in the interval. This contradicts our assumption that the interval (0, 1) is countable. We conclude that the interval (0, 1) is uncountable. Remark: Was there any particular reason why the digits of y were 2's or 3's? No, we could have worked with 4 and 7, for instance. Page 5 of 5 Natural Numbers and Induction Natural Numbers Peano Axioms: Suppose there exists a set P, whose elements are called natural numbers, having the following properties. P1. There exists a natural number, denoted by 1, that is not the successor of any other natural number. P2. Every natural number has a unique successor. If m in P, then we let m' denote the successor of m. P3. Every natural number except 1 is the successor of exactly one natural number. P4. (Principle of Mathematical Induction) Let M be a subset of P. M is equal to P provided that (i) 1 M and (ii) for each k P, if k M, then k' M. Definitions D1. Adding 1: For every n P, define n + 1 = n'. D2. Adding n and m: Let n, m P, with m 1. Then m = k' = k + 1 for some k, and we define n + m = (n + k)' = (n + k) + 1. (recursive) D3. Multiplying by 1: For every n P, define n 1 = n. D4. Multiplying n and m: Let m, n P, with m 1. Then m = k' for some k, and we define n m = n (k + 1) = (n k) + n. (recursive) Axiom (Well-Ordering Property of N) If S is a nonempty subset of N, then there exists an element m S such that m k for all k S. 3 2 1 Suppose you have a vertical ladder reaching up to the sky, with no end in sight. Consider the lowest rung and call it rung #1, the next rung up is #2, and so on. Can you climb the ladder? Suppose you know the following two ideas to be true: a. You can climb the bottom rung of the ladder. That is, you can reach rung #1. b. If you can climb to a rung, you can climb to the next rung up. In other words, if you can reach rung k, then you can climb to rung k + 1. So, you can climb the ladder, one rung at a time. Writing the ladder problem in a more mathematical form, let the statement P(n) be, "You can climb to rung n." Then steps 1 and 2 become: a. P(1) is true. (called the Basis Step) b. For each natural number k, if P(k) is true, then P(k + 1) is true. (called the Inductive Step) If you can establish steps a and b, then you have carried out a proof by induction. This same idea applies to any collection of statements P(n) for which n N. Page 1 of 5 Principle of Mathematical Induction for a set of statements P(1), P(2), ... Let P(n) be a statement that is either true or false for each n N. Then P(n) is true for all n N provided that (a) P(1) is true. (Basis Step) and (b) For each integer k N, if P(k) is true, then P(k + 1) is true. (Induction Step) Proof (by contradiction): Suppose not. Suppose that conditions (a) and (b) hold but P(n) is false for some n N. Let S = { n N | P(n) is false}. S is nonempty and by the Well-Ordering Property, there exists a smallest element in S. Call in m. So, P(m) is false and m cannot be equal to 1 because condition (a) says that P(1) is true. Therefore m > 1, and so m - 1 is also a natural number. Since m is the smallest element in S, m - 1 S. But m - 1 S means that P(m - 1) is true. By condition (b), since P(k) is true for k = m - 1, we must have P(k + 1) true for k + 1 = (m - 1) + 1 = m. Therefore, we have both P(m) false and P(m) true, which is impossible. We conclude that P(n) must be true for all n N. Often a statement P(n) represents a formula for doing a calculation. For a particular set of statements P(n), to prove by induction, steps a and b are usually established in the following way: a. The Basis Step is established by direct substitution and usually a very easy calculation. b. To establish the Inductive Step: Suppose that P(k) is true, where k N. Then you must show that P(k + 1) is true (i.e., you must show that the formula is true when k + 1 is substituted for n.) This process is illustrated in the following example (Also proven on page 154 of Hammack book.) Example 1: P(n): 1 + 3 + 5 + ... + (2n - 1) = n2 for n 1. Notice that P(n) is a statement, not a number. It represents a formula for computing the sum of the odd numbers 1, 3, 5,..., (2n - 1). Before we use induction to prove that P(n) is true for all n 1, let's get a feel for this collection of statements, by looking at some values of n. P(n) Statement Stmt, simplified Truth value of Stmt P(1): 2(1) - 1 = 12 P(2): 1 + [2(2) - 1] = 2 2 P(3): 1 + 3 + [2(3) - 1] = 32 1=1 True 1+3=4 True 1+3+5=9 True 2 P(4): 1 + 3 + 5 + [2(4) - 1] = 4 1 + 3 + 5 + 7 = 16 True Notation: Let LHS mean "Left Hand Side" and RHS mean "Right Hand Side" Notice that when we go from one of the P's to the next, the LHS changes by just adding one more term. Page 2 of 5 Suppose now we assume P(4) is true and we want to use it to establish the truth of P(5). For P(5), LHS = 1 + 3 + 5 + 7 + [2(5) - 1] = 1 + 3 + 5 + 7 + 9 = (1 + 3 + 5 + 7) + 9 (grouping together the terms we saw in LHS of P(4)) = 16 + 9 (because P(4) tells us that 1 + 3 + 5 + 7 = 16) = 25 (arithmetic) = 52 (algebra) We would like to use the same ideas to prove that P(n) is true for ALL integers n 1, not just for n = 1, 2, 3, 4, 5. We will use proof by induction; that is, we will show that the Principle of Mathematical Induction holds. P(n): 1 + 3 + 5 + ... + (2n - 1) = n2 for all integers n 1. Proof (by Induction)--General Outline Proof (by Induction) of Example 1: (a) To show: P(1) is true. a. To show: P(1) is true. Show that the left hand side (LHS) LHS of P(1) = 2(1) - 1 = 1. RHS of P(1) = 12 = 1. is equal to the right hand side Since LHS = RHS, P(1) is true. (RHS). (b) Suppose P(k) is true: That is, suppose the formula is true, where k N. (a) Suppose P(k) is true, where k N. That is, suppose (*) 1 + 3 + 5 + ... + (2k - 1) = k2 To show: P(k + 1) is true: That is, we must show that the formula is true when k + 1 is substituted for n. To show: P(k + 1) is true: That is, we must show (**) 1 + 3 + 5 + ... + [2(k + 1) - 1] = (k + 1)2. LHS of (**) = 1 + 3 + 5 + ... + [2(k + 1) - 1] = 1 + 3 + 5 + ... + (2k + 1) (simplifying the last term) Start with LHS of P(k + 1). Group all terms but the last term together. Apply the formula for P(k) to the grouped terms. Perform some algebraic manipulations to arrive at the RHS of P(k + 1). = 1 + 3 + 5 +... + (2k - 1) + (2k + 1) (Explicitly showing the next-to-last term, which is the last term on the RHS of P(k)) = [1 + 3 + 5 +... + (2k - 1)] + (2k + 1) (grouping together all but the last term) = k2 + (2k + 1) (because P(k) tells us the formula for the grouped terms--see (*) above) = k2 + 2k + 1 = (k + 1)2 (using algebra), which is what we wanted to show [see (**) above]. So, P(k + 1) is true. We conclude that P(n) is true for all n N. Page 3 of 5 Notice that some factoring was involved in the example. (We used the fact that k2 + 2k + 1 = (k + 1)2.) Algebraic manipulation, multiplying out expressions and/or factoring are commonly used in proofs by induction. The algebra involved can be messy. Example: Prove by induction that \u0003\u0004\u0005\u0006 \u0002 = 1 + 2 + 3 + + = \u0003(\u0003\u000f\u0006) \u0011 Proof: a. When n = 1, we have LHS = 1 and RHS = \u0006(\u0006\u000f\u0006) \u0011 \u0011 \u0011 = = 1. Since LHS = RHS, P(1) is true. b. Let k N and suppose P(k) is true: 1 + 2 + 3 + + \u0002 = \u0004(\u0004\u000f\u0006) . \u0011 To show: To show: P(k + 1) is true: That is, we must show 1 + 2 + 3 + + (\u0002 + 1) = (\u0004\u000f\u0006)\u0014(\u0004\u000f\u0006)\u000f\u0006\u0015 \u0011 = (\u0004\u000f\u0006)(\u0004\u000f\u0011) \u0011 We have 1 + 2 + 3 + + (\u0002 + 1) = 1 + 2 + 3 + + \u0002 + (\u0002 + 1) (explicitly showing the next-to-last term) = (1 + 2 + 3 + + \u0002) + (\u0002 + 1) grouping = \u0004(\u0004\u000f\u0006) + \u0011 (\u0002 + 1) using P(k). \u0004 = (\u0002 + 1) \u0016\u0011 + 1\u0017 factoring out (k + 1) \u0004\u000f\u0011 \u0017 \u0011 = (\u0002 + 1) \u0016 = (\u0004\u000f\u0006)(\u0004\u000f\u0011) \u0011 so P(k + 1) is true. We conclude that P(n) is true for all n N. Useful Formulas (which can be proven by induction): \u0003(\u0003\u000f\u0006) Sum of the first n positive integers: \u0003\u0004\u0005\u0006 \u0002 = 1 + 2 + 3 + + = \u0011 Sum of the square of the first n positive integers: \u0003\u0004\u0005\u0006 \u0002 \u0011 = 1\u0011 + 2\u0011 + 3\u0011 + + \u0011 = Sum of the cubes of the first n positive integers: \u0003(\u0003\u000f\u0006)(\u0011\u0003\u000f\u0006) \u0018 \u0003\u0004\u0005\u0006 \u0002 \u0019 = 1\u0019 + 2\u0019 + 3\u0019 + + \u0019 = \u0016 \u0003(\u0003\u000f\u0006) \u0011 \u0017 \u0011 Sum of a finite geometric sequence with first term 1 and factor r (where r is not equal to 1) \u0003\u0004\u0005\u001b \u001a \u0004 = 1 + \u001a + \u001a \u0011 + + \u001a \u0003 = \u0006\u001c\u001d \u001e\u001f \u0006\t\u001c\t\u001d Page 4 of 5 Example: Prove by induction that 7n - 4n is a multiple of 3, for all n N. Proof: a. When n = 1, we have 71 - 41 = 3, which is a multiple of 3. Therefore, P(1) is true. b. Let k N and suppose P(k) is true, that 7k - 4k is a multiple of 3. Then 7k - 4k = 3m for some integer m. To show: 7k+1 - 4k+1 is a multiple of 3 7k+1 - 4k+1 = 7k+1 - 7 4k + 7 4k - 4k+1 (Tricky part --- adding and subtracting the right quantity!) = (7 7k - 7 4k ) + ( 7 4k - 4 4k) grouping = 7(7k - 4k) + (7 - 4)4k factoring = 7(3m) + 3 4k since 7k - 4k = 3m = 3(7m + 4k) factoring out 3 = 3q for integer q = 7m + 4k Thus 7k+1 - 4k+1 is a multiple of 3, so P(k + 1) is true. We conclude that 7n - 4n is a multiple of 3 for all n N. Important Example: Bernoulli's inequality. Suppose x is a real number with x > 1. (1 + x)n 1 + nx for every n N . (Note that x is a fixed real number and does not depend on n.) Bernoulli's inequality is proven by induction on page 158 of the Hammack book. Generalized Principle of Mathematical Induction (for a set of statements P(m), P(m+ 1), ... ) Let P(n) be a statement that is either true or false for each n m . Then P(n) is true for all n m, provided that (a) P(m) is true. (Basis Step) and (b) For each integer k m , if P(k) is true, then P(k + 1) is true. (Induction Step) Page 5 of 5 Inequalities and Absolute Value Theorem. Let x, y R. If x y + for every > 0, then x y. Contrapositive: Let x, y R. If x > y, then x > y + for some > 0. Note: "not x y" means "x > y" because of the trichotomy order axiom O1. Proof of theorem (by contraposition). Let x, y R and suppose x > y. To show: x > y + for some > 0, i.e., that x y > for some > 0. Since x > y, we have x y > 0. Let = (x y)/2, so > 0. Then x y > (x y)/2 = So, we have found an > 0 such that x y > . Corollary. If 0 r < for all real numbers > 0, then r = 0. Note: This is Week 2 Homework #17, and is also Proposition 1.2.2 on page 25 of Lebl. Proof of corollary, using the theorem: Suppose 0 r < for all real numbers > 0. Thus r 0 + . Apply the theorem with x = r and y = 0 to conclude that r 0. Now we have 0 r 0 which is possible only if r = 0. Definition of absolute value: | = | , < 0\u0001 , 0 Section 1.3 of Lebl book Theorem. Let x, y R and let a 0. Then (a) | x | 0. (b) | x | a iff a x a (c) | xy | = | x | | y | (d) Triangle inequality: | x + y | | x | + | y |. Page 1 of 2 Proof of (d), the Triangle Inequality: Let x and y be any real numbers. Clearly, | x | | x |. By part (b), with a = | x | 0, we have | x | x | x |. Likewise, with a = | y | 0, we have | y | y | y |. Adding the inequalities, we have (| x | + | y |) x + y | x | + | y |. Applying part (b) with a = | x | + | y |, we have | x + y | | x | + | y |. Variation on the Triangle Inequality: Proposition. For any real numbers a, b, and c, | a b | | a c | + | c b | The distance between a and b is less than or equal to the sum of the distance between a and c and the distance between c and b. Proof: Apply the Triangle Inequality with x = a c and y = c b as follows: | a b | = | (a c) + (c b) | = | x + y | | x | + | y | = | a c | + | c b | Proposition. For any n in N, given any n real numbers x1, x2, ..., xn , | x1 + x2 + ... + x n | | x1 | + | x2 | + ... + | x n |. Proof (by induction): Let x1 be any real number. When n = 1, we have LHS = | x1 | and RHS = | x1 |. Since LHS RHS, P(1) is true. Let k N and suppose P(k) is true: For any real numbers x1, x2, ..., xk suppose | x1 + x2 + ... + x k | | x1 | + | x2 | + ... + | x k | To show: P(k + 1) is true: for any real numbers x1, x2, ..., xk+1, | x1 + x2 + ... + x k + 1 | | x1 | + | x2 | + ... + | x k + 1 | Let x1, x2, ..., xk+1 be any real numbers. We have | x1 + x2 + ... + x k + 1 | = | (x1 + x2 + ... + xk ) + x k + 1 | by field axiom A3 | x1 + x2 + ... + xk | + |x k + 1 | by the triangle inequality (Theorem (d)) | x1 | + | x2 | + ... + | x k | + |x k + 1 | applying P(k) So, P(k + 1) is true. We conclude that P(n) is true for all n N. Page 2 of 2 Limits and Continuity Limits of Functions Definition. Let f: D R and let c be an accumulation point (cluster point) of D. We say that a real number L is a limit of f at c, if for each > 0 there exists a > 0 such that | f(x) - L | < whenever x D and 0 < | x - c | < . Notation: We write lim\u0004\u0006 \u0007\b = . (equivalent to Def. 3.1.3 Lebl) Theorem: Let f: D R and let c be an accumulation point of D. Then lim\u0004\u0006 \u0007\b = iff for each neighborhood V of L there exists a deleted neighborhood U of c such that f(U D) V. Example: Let f(x) = 5x + 9. Show that lim\u0004\u000e\u000f \u0007\b = 6. Discussion: Suppose is any positive real number. We want to find such that | f(x) - (-6) | = | (5x + 9) - (-6) | < whenever 0 < | x - (-3)| < . But | (5x + 9) - (-6) | = | 5x + 15 | = 5|x + 3| = 5| x - (-3)| < 5. So, we want 5 = , which implies that = /5. Formal Proof: Given any > 0, let = /5. Whenever 0 < | x - (-3)| < we have | f(x) - (-6) | = | (5x + 9) - (-6) | = | 5x + 15 | = 5|x + 3| = 5|x - (-3)| < 5 = 5(/5) = . Page 1 of 10 Example: Let \u0007\b = \u0012 Note that \u0013\u0004 \u0014 \u000e\u000f\u0004\u0015\u0016 \u0004\u000e\u0016 = \u0013\u0004 \u0014 \u000e\u000f\u0004\u0015\u0016 \u0004\u000e\u0016 , 1\u001b 5, = 1 \b\u0013\u0004\u000e\u0016 \b\u0004\u000e\u0016 \u0004\u000e\u0016 = 2 1 provided that x 1. As x approaches 1, we expect that f(x) approaches 2(1) - 1 = 1. Claim: lim\u0004\u0016 \u0007\b = 1. (Note that this limit is not equal to f(1), which is 5.) Discussion: Suppose is any positive real number. If 0 < | x - 1| < , we have \u0013\u0004 \u0014 \u000e\u000f\u0004\u0015\u0016 | f(x) - 1| = \u001d 1\u001d = |\b2 1 1| = |2 2| = 2| 1| < 2! \u0004\u000e\u0016 So, we want 2 = , which implies that = /2. Formal Proof: Given any > 0, let = /2. Whenever 0 < | x - 1| < , \u0013\u0004 \u0014 \u000e\u000f\u0004\u0015\u0016 we have | f(x) - 1 | = \u001d \u0004\u000e\u0016 1\u001d = |\b2 1 1| = |2 2| = 2| 1| < 2! = 2(/2) = Example: f(x) = x2 + 2x + 6. Show that lim\u0004\u000f \u0007\b = 21. Discussion: Suppose is any positive real number. If 0 < | x - 3| < . We want to find such that | f(x) - 21 | = | (x2 + 2x + 6) - 21 | < . But | f(x) - 21 | = | (x2 + 2x + 6) - 21 | = | x2 + 2x -15| = |x +5||x - 3| < |x +5|. Now we need a numerical bound on |x +5| when x is close to 3. Say that x is within 1 unit of 3, so = 1, and 2 < x < 4. Then 2 + 5 < x + 5 < 4 + 5 so 7 < x + 5 < 9, and thus |x + 5| < 9. So |x +5| < 9 = if = /9. So, we want = min {1, /9}. Formal Proof: Given any > 0, let = min {1, /9}. Whenever 0 < | x - (-3)| < , we have | f(x) - 21 | = | (x2 + 2x + 6) - 21 | = | x2 + 2x -15| = |x +5||x - 3| < 9 9(/9) = Page 2 of 10 Sequential Criterion for Limits (Lemma 3.1.7 Lebl) Theorem. Let f: D R and let c be an accumulation point of D. Then lim\u0004\u0006 \u0007\b = iff for every sequence (sn) in D with sn c and sn c, the sequence (f(sn)) converges to L. Proof: Suppose lim\u0004\u0006 \u0007\b = and let (sn) be any sequence with sn c and sn c. To show: lim"# \u0007\b$% = . Let > 0. Since lim\u0004\u0006 \u0007\b = , > 0 such that| f(x) - L | < whenever x D and 0 < | x - c | < . Since lim"# $% = &, N such that n > N implies that | sn - c | < . Therefore, since sn c, for n > N , we have 0 < | sn - c | < and sn D, so | f(sn) - L | < . Hence lim"# \u0007\b$% = . Proof of the converse (by contraposition): Suppose lim\u0004\u0006 \u0007\b . To show: There exists a sequence (sn) in D with sn c and sn c, for which the sequence (f(sn)) does not converge to L. Since lim\u0004\u0006 \u0007\b , > 0 such that > 0, x D with 0 < |x - c| < such that |f(x) - L | . In particular, positive integer n, sn D with 0 < |sn - c| < 1/n such that |f(sn) - L | . Now we have a sequence (sn) in D which converges to c with sn c for all n, but the sequence (f(sn)) cannot converge to L. Corollary: If f: D R and if c is an accumulation point of D, then f can have only one limit at c. Theorem. Let f: D R and let c be an accumulation point of D. Then the following are equivalent: (a) f does not have a limit at c. (b) There exists a sequence (sn) in D with each sn c such that (sn) converges to c, but (f(sn)) is not convergent in R. Page 3 of 10 Example: f(x) = sin (1/x) for x 0. Investigate what happens as x approaches 0. (Example 3.1.8 Lebl, p. 98) The function oscillates between -1 and 1, faster and faster as x approaches 0. \u0016 We can use the previous theorem to prove that lim\u0004' sin \u0004 does not exist. \u0013 \u0013 "* Let $" = "*. Then \u0007\b$" = \u0007 +"*, = sin + \u0013 ,. As n , sn 0 and -\u0007\b$" . = \b1,0, 1,0,1,0, 1,0, ... which diverges. By the previous theorem, the limit does not exist. Theorem: Let f: D R and g: D R, and let c be an accumulation point of D. If lim\u0004\u0006 \u0007\b = , lim\u0004\u0006 1\b = 2 , and k R, then lim\u0004\u0006 \b\u0007 + 1 \b = + 2 , lim\u0004\u0006 \b\u00071 \b = 2,\tand lim\u0004\u0006 \b4\u0007 \b = 4\f. 5 7 Furthermore, if g(x) 0 for all x D and M 0, then lim\u0004\u0006 +6, \b = 8 . (Corollary 3.1.12 Lebl) One way to prove the statements is to use the sequence criterion. Here is the proof of the sum result: Proof: Let (sn) be a sequence in D that converges to c with each sn c . By our previous theorem, since lim\u0004\u0006 \u0007\b = and lim\u0004\u0006 1\b = 2, we have lim"# \u0007\b$" = and lim"# 1\b$" = 2, and now by definition of the sum function and our sum theorem for sequences, we have lim \b\u0007 + 1 \b$" = lim 9\u0007\b$" + 1\b$" : = lim \u0007\b$" + lim 1\b$" = + 2 "# "# "# "# Page 4 of 10 Examples applying parts of the previous theorem: Example: lim\u0004\u0016 \u0013\u0004 \u0014 \u000e\u000f\u0004\u0015\u0016 \u0004\u0015\u0016 Example: Let \u0007\b = \u0012 Consider lim\u0004\u0016 \u0013\u0004 \u0014 \u000e\u000f\u0004\u0015\u0016 \u0004\u000e\u0016 \u0013\u0004 \u0014 \u000e\u000f\u0004\u0015\u0016 \u0004\u000e\u0016 ;<= \b\u0013\u0004\u000e\u0016 \b\u0004\u000e\u0016 = >?;<= \b\u0004\u0015\u0016 >? , 1\u001b 5, = 1 ;<= \b\u0013\u0004\u000e\u0016 ;<= \b\u0004\u000e\u0016 = >? >? ;<= \b\u0004\u0015\u0016 >? = \u0016' \u0013 ' = \u0013 = 0. . We cannot use the quotient theorem directly because the limit of the denominator is 0: lim\u0004\u0016 \b 1 = 1 1 = 0. First factor and simplify, and then find the limit: lim\u0004\u0016 \u0013\u0004 \u0014 \u000e\u000f\u0004\u0015\u0016 \u0004\u000e\u0016 = lim\u0004\u0016 \b\u0013\u0004\u000e\u0016 \b\u0004\u000e\u0016 \u0004\u000e\u0016 = lim\u0004\u0016 \b2 1 = 2\b1 1 = 1 Other familiar results: Corollary 3.1.10 and Corollary 3.1.11 on page 99 in Lebl: "Squeeze theorem" Let f: D R , g: D R , and h: D R and let c be an accumulation point (cluster point) of D. Suppose \u0007\b 1\b \b for all x in D, and suppose limits of f and h exist as x c. That is, suppose lim\u0004\u0006 \u0007\b = and lim\u0004\u0006 \b = . Then lim\u0004\u0006 1\b = . One-sided limits: (also in Lebl, pages 100-101) Definition. Suppose the domain D = interval (a, b). Let f: D R. We say that a real number L is a right-hand limit of f at a, if for each > 0 there exists a > 0 such that | f(x) - L | < whenever x D and 0 < x - a < , i.e., a < x < a + . Notation: We write lim\u0004C\u0015 \u0007\b = . We say that a real number L is a left-hand limit of f at b, if for each > 0 there exists a > 0 such that | f(x) - L | < whenever x D and 0 < b - x < , i.e., b - < x < b. Notation: We write lim\u0004D\u000e \u0007\b = . Note that lim\u0004\u0006 \u0007\b = iff lim\u0004\u0006\u0015 \u0007\b = and lim\u0004\u0006\u000e \u0007\b = . That is, the two-sided limit exists and is equal to L iff both of the one-sided limits exist and are equal to L. Page 5 of 10 Continuous Functions Definition: Let f: D R and let c D. We say that f is continuous at c if for every > 0 there exists a > 0 such that | f(x) - f(c)| < whenever |x - c| < and x D. If f is continuous at each point of a subset S of D, then f is said to be continuous on S. If f is continuous on its domain D, then f is said to be continuous. (Also Def. 3.2.1, p. 103 Lebl) Theorem: Let f: D R and let c D. Then the following three conditions are equivalent: (a) f is continuous at c. (b) If (xn) is any sequence in D such that (xn) converges to c, then EFGHI J\bH = J\bI . (c) For every neighborhood V of f(c), there exists a neighborhood U of c with f(U D) V. Furthermore, if c is an accumulation point of D, then the above are all equivalent to (d) f has a limit at c and EFGHI J\bH = J\bI . (Also Prop. 3.2.2, p. 103 Lebl) Example: Every polynomial function is continuous on R. Example: \u0007\b = \u0012 (Lebl, page 98) \u0016 sin \u0004 , 0\u001b 0, = 0 is continuous on R. Page 6 of 10 Theorem. Let f: D R and let c D. Then f is discontinuous at c iff there exists a sequence (xn) in D such that (xn) converges to c but the sequence (f(xn)) does not converge to f(c). 1, LMNOP%MQ \u001b Example: Dirichlet function f: R R where \u0007\b = K is discontinuous at each 0, OLLMNOP%MQ real number. (Example 3.2.11, p. 106 Lebl) Example: Modified Dirichlet function: f: (0, 1) (0, 1) where 1 \u0007\b = R% , 0, S O$\tLMNOP%MQ\tO%\tQPTU$N\tNULS$\u001b % OLLMNOP%MQ O\u0007 = is continuous at each irrational number in the interval (0, 1) and discontinuous at each rational number in (0, 1). Also known as the "popcorn" function. (Example 3.2.12, p. 107Lebl) Section 3.2.2 (Lebl) Theorem. Let f: D R and g: D R and let c D. Suppose that f and g are continuous at c. Then (a) f + g and fg are continuous at c, and (b) f/g is continuous at c if g(c) 0. Theorem. Let f: D R and g: E R such that f(D) E . If f is continuous at a point c D and g is continuous at f(c), then the composition g o f: D R is continuous at c. Page 7 of 10 Theorem. A function f: D R is continuous on D iff for every open set G of real numbers there exists an open set H of real numbers such that H D = J\u000eV \bW . Corollary. A function f: R R is continuous iff J\u000eV \bW is an open subset of R whenever G is an open subset of R. --------------------------------------------------------------------------------------------------------------------------Section 22: Properties of Continuous Functions A function f: D R is said to be bounded if its range f(D) is a bounded subset of R. That is, f is bounded if there exists a real number M such that | f(x) | M for all x in D. Example: A continuous function is not necessarily bounded. For instance, let f: (0, 1) R where f(x) = 1/x. f is continuous on (0, 1) but the range (0, ) is unbounded. Recall that "compact" is equivalent to "closed and bounded". Theorem. Let D be a compact subset of R and suppose that f: D R is continuous. Then f(D) is compact. (Min-max theorem, section 3.3.2, p. 109 Lebl): Corollary. Let D be a compact subset of R and suppose that f: D R is continuous. Then f assumes minimum and maximum values on D. That is, there exist points x1 and x2 in D such that f(x1) f(x) f(x2) for all x in D. Example: A continuous bounded function does not necessarily assume maximum and minimum values on its domain. For instance, let f: (0, 1) R where f(x) = x. f is continuous on (0, 1) but the range (0, 1) has neither a maximum nor a minimum. Lemma: Let f: (a, b) R and be continuous and suppose that f(a) < 0 < f(b). Then there exists a point c in (a, b) such that f(c) = 0. Page 8 of 10 (Bolzano Intermediate Value Theorem (3.3.8, Lebl) ): Intermediate Value Theorem. Suppose that f: D R is continuous. If k is any value between f(a)and f(b), then there exists c in (a, b) such that f(c) = k. Example: Every polynomial of odd degree has at least one real root. Theorem. Let I be a compact interval and suppose that f: I R is a continuous function. Then the set f(I) is a compact interval. ------------------------------------------------------------------------------------------------------------------------------Section 23: Uniform Continuity From section 21: Definition: Let f: D R and let c D. We say that f is continuous at c if for every > 0 there exists a > 0 such that | f(x) - f(c)| < whenever |x - c| < and x D. Note that the depends on and on real number c. Definition. A function f: D R is said to be uniformly continuous on D if for every > 0 there exists a > 0 such that | f(x) - f(y)| < whenever |x - y| < and x, y D. (Def. 3.4.1, Lebl) Note that here can depend on set D but not on a particular element of D. Examples: The function f(x) = 2x is uniformly continuous on R. The function f(x) = x2 is not uniformly continuous on R. The function f(x) = x2 is uniformly continuous on [0, 1]. (See Lebl, p. 115, example 3.4.3) The function f(x) = 1/x is not uniformly continuous on (0, 1). (See Lebl, p. 115, example 3.4.2) Page 9 of 10 (Th. 3.4.4, Lebl) Theorem. Let f: D R be continuous on a compact set D. Then f is uniformly continuous on D. (Lemma 3.4.5, Lebl, p. 116) Theorem: Let f: D R be uniformly continuous on D and suppose that (xn) is a Cauchy sequence in D. Then (f (xn)) is a Cauchy sequence. Example: The function f(x) = 1/x is not uniformly continuous on (0, 1], applying the theorem: \tcontinuous function f: D R and a Cauchy sequence (xn) in D such that (f (xn)) diverges. For instance, let f: (0, 1] R where f(x) = 1/x and let (xn) = (1/n). Then f is continuous and (1/n) is a Cauchy sequence in the interval (0, 1], but sequence (f(1/n)) = (1/(1/n)) = (n) diverges. Definition. We say that a function\u0007X: E R is an extension of a function f: D R is if D E and \u0007X\b = \u0007\b for all x in D. (Th. 3.4.6, Lebl, page 117) *Theorem. A function f: (a, b) \tY\tis\tuniformly continuous on (a, b) iff it can be extended to a function JZ that is continuous on [a, b]. Example: f (x) = sin (1/x) is not uniformly continuous on the interval (0, 1/): \u0016 Since lim\u0004' sin \u0004 does not exist (page 4 of these notes), it is not possible for f (x) = sin (1/x) to be extended to a function that is continuous on [0, 1/]. [See Theorem(d) on page 6 of these notes]. Therefore, by Theorem* above, f is not uniformly continuous on the interval (0, 1/). -------------------------------------------Limits at Infinity Definition. Let f: (b, ) R where b R. We say that L R is the limit of f as x , written lim \u0007\b = \u0004 provided that for each > 0 there exists a real number N > b such that x > N implies that | f(x) - L | < . Definition. Let f: (b, ) R where b R. We say that f tends to as x , written lim \u0007\b = \u0004 provided that for each R there exists a real number N > b such that x > N implies that f(x) > . Page 10 of 10 Logic and Proofs \"Logic Logic is the anatomy of thought. thought.\" - John Locke (1632-1704) Section 1: Logical Connectives A statement is a sentence that is unambiguously TRUE or FALSE. For example, Barack Obama is President of the U.S U.S. is a true statement, John McCain is President of the U.S U.S. is a false statement, and He is President of the U.S.. is a sentence but not a statement, unless we all know precisely who He is. We can denote a statement by a letter (typically letters such as p, q, or r). Compound statements combine individual simple statements using logical connectives. Type of Logical Connective Associated Connecting Words and or not if, then Conjunction Disjunction Negation Implication (Conditional) Equivalence (Biconditional) Symbol ~ , if and only if , Sample Symbolic Statement Form Sample Statement Form, in words pq pq ~p pq p is called the antecedent or hypothesis and q is called the consequent or conclusion. pq p and q. p or q (or both). not p. Alternative wording: If p,, then q. p implies q. p only if q. q if p. p is sufficient for q. q is necessary for p. p if and only if q p iff q The English expression "but" is a conjunction, can be replaced by ""and"" and translates to "" in logic. The English expression "neither p nor q" means "not p and not q" which is ~p ~q. Order of Precedence Expressions in parentheses are considered first. The order of precedence for logical connectives is ~ , , , , , Carry out ~ first (left to right in a logical expression), then ,, and so on. Parentheses can be inserted to specify the order. A truth table for a compound statement displays the possible truth values (T or F) of the compound statement, based on the truth values of the co component simple statements. Negation p T F ~p F T Conjunction p T T F F q T F T F pq T F F F Disjunction p T T F F q T F T F pq T T T F Implication p T T F F q T F T F pq T F T T Equivalence (biconditional) pq p q T T T T F F F T F F F T Negation: ~ reverses the truth value value--if p is true, ~p is false; if p is false, ~p is true. Conjunction: p q is true only in the case where both p and q are true; otherwise p q is false. Disjunction: p q is true when p is true or q is true; p q is false only in the case where both p and q are false. Implication: p q is false only in the case where the hypothesis p is true but the conclusion q is false. Notice that for p true and q true, p q is true. In the cases where the hypothesis p is false, we define p q to be (vacuously) true. Equivalence: p q is true where the truth values of p and q match, and false where they differ. Page 1 of 9 A tautology is a compound statement whose truth value is T for all cases (rows) of its truth table. For instance ~(p q) ~p ~q is a tautology, as shown below: (1) (2) p T T F F q T F T F (3) = (1) (2) (4) = ~(3) (5) =~(1) (6) =~(2) (7) = (5) (6) pq T T T F ~(p q) F F F T ~p F F T T ~q F T F T ~p ~q F F F T (8) = (4) (7) ~(p q) T T T T ~p ~q Note that column (8) is all T's because columns (4) and (7) are identical. In general, saying that A B is a tautology is the same as saying that the columns for A and B are identical, and we say that A and B are logically equivalent. Very Important Tautologies (Logical Equivalences): De Morgan's Laws: ~ (p q) ~ p ~q. Note that it's on the left side expression but on the right. ~ (p q) ~ p ~q. Note that it's on the left side expression but on the right. Implications: ~ (p q) p ~q. (This means the negation of p q is true only when p is true and q is false) (p q) ~p q . (Can also be derived by taking the negation of left side and the right side of the previous tautology and using De Morgan's Laws) Section 2: Quantifiers Consider the sentence "x is odd." We could label the sentence P(x). It is called a predicate. It is not a statement -- we cannot determine whether P(x) is true or false without first specifying x. For instance, P(3) is true since 3 is odd, but P(4) is false, since 4 is even. What about P(0.75)? In this case the sentence doesn't make sense, because the idea of odd applies only to integers. Given a predicate P(x), we typically restrict the set of values that may be substituted for x, and we call this set the domain, and often label it D. For our example, we could specify D to be the set of all integers. The truth set of a predicate P(x) is the set of all elements x of D for which P(x) is true. For our example, the truth set = {1, -1, 3, -3, 5, -5,...} In our real analysis course, if a domain is not explicitly stated, then we assume it to be the set of real numbers. In many situations we are interested in judging whether a predicate is true for every element in the domain. That is, we would like to judge whether a given predicate is universally true. Page 2 of 9 Suppose we have a predicate P(x) and a domain D. A universal statement is a statement of the form x in D, P(x). The symbol is read "for all" or "for every" or " for each" or given any". A universal statement is TRUE if and only if the predicate P(x) is TRUE for every x in the domain D. Example: x , x2 0. "For all real numbers x, the square of x is greater than or equal to 0." More concisely, "The square of any real number is nonnegative." A universal statement is FALSE if and only if the predicate is FALSE for at least one element of the domain D. Such an element is called a counterexample. \u0001 Example: x , \u0002 \u0003 0. "For all real numbers x, the reciprocal of the square of x is nonnegative." This is \u0001 \u0001 false because there is a real number, 0, for which \u0003 is not nonnegative. (In fact, \u0003 does not exist for x = \u0002 \u0002 0). Frequently, we are interested in judging whether a predicate is true for at least one element in the domain. That is, we would like to judge whether there exists an element of the domain for which the predicate is true. Suppose we have a predicate P(x) and a domain D. An existential statement is a statement of the form x in D P(x). The symbol is read "there exists" or "there is at least one" or "there is some". The symbol is just shorthand for "such that." An existential statement is TRUE if and only if the predicate is TRUE for at least one element in the domain D. Example: x x2 = 1. "There is a real number whose square is 1." (In fact, there are two possibilities, 1 and 1.) An existential statement is FALSE if and only if the predicate is FALSE for every element of the domain D. Example: x x2 = 1. "There is a real number whose square is 1." (False; if the domain had been complex numbers, then the statement would be true.) NEGATION The negation of a universal statement is an existential statement. ~( x in D, P(x)) x in D ~P(x). Note that the negation of "All ___ are" is "Some ____ are not". The negation of an existential statement is a universal statement. ~( x in D P(x)) x in D, ~P(x). Note that the negation of "Some____ are" is "No ____ is." TIP: To negate a quantified English sentence, it is a good idea to first write it formally with quantifiers, then write a formal negation, and then write the equivalent informal negation. Example: Every basketball player is tall and thin. Formal version: basketball players x, x is tall and x is thin. Negation, formal version: basketball player x such that ~(x is tall and x is thin), which is equivalent to: basketball player x such that x is not tall or x is not thin. (De Morgan). Negation, informal version: Some basketball player is not tall or not thin. Page 3 of 9 Negation of a universal implication: ~(x, P(x) Q(x)) x P(x) ~ Q(x). Here we are using the logical equivalence for implications on page 2. Example: If a polygon has four sides, then it