Background Material on Sets and Real Analysis

MASSACHUSETTS INSTITUTE OF TECHNOLOGY 6.436J/15.085J Recitation 1 Fall 2018 BACKGROUND MATERIAL ON SETS AND REAL ANALYSIS 1 SETS A set is a collection of objects, which are the elements of the set. If A is a set and x is an element of A, we write x ∈ A. If x is not an element of A, we write x ∈ / A. A set can have no elements, in which case it is called the empty set, denoted by Ø. Sets can be specified in a variety of ways. If A contains a finite number of elements, say x1 , x2 , . . . , xn , we write it as a list of the elements, in braces: A = {x1 , x2 , . . . , xn }. For example, the set of possible outcomes of a die roll is {1, 2, 3, 4, 5, 6}, and the set of possible outcomes of a coin toss is {H, T }, where H stands for “heads” and T stands for “tails.” More generally, we can consider the set of all x that have a certain property P , and denote it by {x | x satisfies P }. (The symbol “ | ” is to be read as “such that.”) For example, the set of even integers can be written as {k | k/2 is integral}. Similarly, the set of all real numbers x in the interval [0, 1] can be written as {x | 0 ≤ x ≤ 1}. If A contains infinitely many elements x1 , x2 , . . ., that can be enumerated in a list (so that the elements are in a one-to-one correspondence with the positive integers), we write A = {x1 , x2 , . . .}, and we say that A is countably infinite. For example, the set of even integers can be written as {0, 2, −2, 4, −4, . . .}, and is countably infinite. The term countable is sometimes used to refer to a set which is either finite or countably infinite. A set which is not countable is said to be uncountable. If every element of a set A is also an element of a set B, we say that A is a subset of B, and we write A ⊂ B or B ⊃ A. If A ⊂ B and A ⊂ B, the two 1 sets are equal, and we write A = B.1 It is sometimes expedient to introduce a universal set, denoted by Ω, which contains all objects that could conceivably be of interest in a particular context. Having specified a context in terms of a universal set Ω, one then only considers sets A that are subsets of Ω. 2 SET OPERATIONS The complement of a set A, with respect to a universal set Ω, is the set {x ∈ Ω|x∈ / A} of all elements of Ω that do not belong to A, and is denoted by Ac . Note that Ωc = Ø. The union of two sets A and B is the set of all elements that belong to A or B (or both), and is denoted by A ∪ B. The intersection of two sets A and B is the set of all elements that belong to both A and B, and is denoted by A ∩ B. Thus, A ∪ B = {x | x ∈ A or x ∈ B}, and A ∩ B = {x | x ∈ A and x ∈ B}. We also define A \ B = A ∩ B c = {x | x ∈ A and x ∈ / B}, which is the set of all elements that belong to A but not in B. We will often deal with the union or the intersection of several, even infinitely many sets, defined in the obvious way. In particular, if I is a (possibly infinite) index set, and for each i ∈ I we have a set Ai , the union of these sets is defined as [ Ai = {x | x ∈ Ai for some i ∈ I}, i∈I and their intersection is defined as \ Ai = {x | x ∈ Ai for all i ∈ I}. i∈I In case we are dealing with the union or intersection of countably many sets Ai , ∞ the notation ∪∞ i=1 Ai and ∪i=1 Ai , respectively, is used. Two sets are said to be disjoint if their intersection is empty. More generally, several sets are said to be disjoint if no two of them have a common element. 1 Some texts use the notation A ⊆ B to indicate that A is a subset of B, and reserve the notation A ⊂ B for the case where A is a proper subset of B, i.e., a subset of B which is not equal to B. 2 Disjoint sets are also said to be mutually exclusive. A collection of sets is said to be a partition of a set A if the sets in the collection are disjoint and their union is A. 2.1 The Algebra of Sets Set operations have several properties, which are elementary consequences of the definitions. Some examples are: A∪B A ∪ (B ∪ C) A ∩ (B ∪ C) (Ac )c A∪Ω = = = = = B ∪ A, A∩B (A ∪ B) ∪ C, A ∩ (B ∩ C) (A ∩ B) ∪ (A ∩ C), A ∪ (B ∩ C) A, A ∩ Ac Ω, A∩Ω = = = = = B ∩ A, (A ∩ B) ∩ C, (A ∪ B) ∩ (A ∪ C), Ø, A. Two particularly useful properties are given by De Morgan’s laws which state that !c !c [ \ \ [ Ai = Aci , Ai = Aci . i∈I i∈I i∈I i∈I To establish the first law, suppose that x ∈ (∪i∈I Ai )c . Then, x ∈ / ∪i∈I Ai , which implies that for every i ∈ I, we have x ∈ / Ai . Thus, x belongs to the complement of every Ai , and x ∈ ∩i∈I Aci . This shows that (∪i∈I Ai )c ⊂ ∩i∈I Aci . The reverse inclusion is established by reversing the above argument, and the first law follows. The argument for the second law is similar. 3 NOTATION: SOME COMMON SETS We now introduce the notation that will be used to refer to some common sets: (a) R denotes the set of all real numbers; (b) R denotes R ∪ {−∞, ∞}, the set of extended real numbers. (c) Z denotes the set of all integers; (d) N denotes the set of natural numbers (the positive integers). Also, for any a, b ∈ R, we use the following notation: (a) [a, b] denotes the set {x ∈ R | a ≤ x ≤ b}; (b) (a, b) denotes the set {x ∈ R | a < x < b}; 3 (c) [a, b) denotes the set {x ∈ R | a ≤ x < b}; (d) (a, b] denotes the set {x ∈ R | a < x ≤ b}. We finally introduce some definitions related to products of sets. (a) The Cartesian product of n sets A1 , . . . , An , denoted by A1 × A2 × · · · × Q An , or ni=1 Ai for short, is the set of all n-tuples that can be formed by picking one element from each set, that is, n Y Ai = {(a1 , . . . , an ) | ai ∈ Ai , ∀ i}. i=1 The set A × A is also denoted by A2 . The notation An is defined similarly. Q (b) The Cartesian product ∞ i=1 Ai of an infinite sequence of sets Ai is defined as the set of all sequences (a1 , a2 , . . .) where ai ∈ Ai for each i. The simpler notation A∞ is used if Ai = A for all i. (c) The set of all subsets of a set A is denoted by 2A . (d) Given two sets A and B, AB stands for the set of functions from B to A. As defined above, a sequence (a1 , a2 , . . .) of elements of a set A belongs to A∞ . However, such a sequence can also be viewed as a function from N into A, which belongs to AN . Thus, there is a one-to-one correspondence between A∞ and AN . In the special case where A = {0, 1}, a sequence (a1 , a2 , . . .) can be identified with a subset of N, namely the set {n ∈ N | an = 1}. We conclude that there is a one-to-one correspondence between {0, 1}∞ , {0, 1}N , and 2N . 4 REMARKS ON THE CARDINALITY OF SETS For any finite set, its cardinality is intuitively defined as the number of elements in it. For infinite sets, one might be tempted to define their cardinality as infinity. However, not all infinite sets are created equal, so we need to find a way to differentiate them. We begin by defining a way to compare the cardinality of any two arbitrary sets A and B. 4 Definition 1. (a) We say that A and B have the same cardinality, denoted by |A| = |B|, if and only if there exists a bijective function f : A → B. (b) We say that A has cardinality smaller than or equal to B, denoted by |A| ≤ |B|, if and only if there exists an injective function g : A → B. (c) We say that A has cardinality bigger than or equal to B, denoted by |A| ≥ |B|, if and only if there exists an surjective function g : A → B. Using this definition, we define what it means for a set to be countable, or uncountable. Definition 2. (a) We say that a set is countable, if its cardinality is smaller than or equal to the set of natural numbers N. (b) We say that a set is uncountable, if its cardinality is strictly bigger than the cardinality of the natural numbers N. Since the continuum hypothesis (a set theoretic axiom) states that there is no set with cardinality between the cardinality of the natural numbers and the cardinality of the real numbers, uncountable sets can also be defined as the ones that have cardinality bigger than or equal to the cardinality of the real numbers. We collect here some facts that are useful in distinguishing countable and uncountable sets. 5 Theorem 1. (a) The union of countably many countable sets is a countable set. (b) If A is finite, of cardinality n, then 2A has cardinality 2n . (c) The Cartesian product of finitely many countable sets is countable. (d) The set of rational numbers is countable. (e) The set {0, 1}∞ is uncountable. (f) The Cartesian product of infinitely many sets (with at least two elements each) is uncountable. Proof. (a) Left as an exercise. (b) When choosing a subset of A, there are two choices for each element of A: whether to include it in the subset or not. Since there are n elements, with two choices for each, the total number of choices is 2n . (c) Suppose that A and B are countable sets, and that A = {a1 , a2 , . . .}, B = {b1 , b2 , . . .}. We observe that A×B = ∞ [
{ai } × B . i=1 For any i, there is a one-to-one correspondence between elements of B and elements of {ai } × B. Therefore {ai } × B is countable. Using part (a) of the theorem, it follows that A × B is countable. We continue by induction. We fix some k ≥ 2 and use the induction hypothesis that the Cartesian product of k or fewer countable sets is countable. Suppose that the sets A1 , . . . , Ak+1 are countable. We observe that the set A1 × · · · × Ak+1 is essentially the same as the set (A1 × · · · × Ak ) × Ak+1 , which is a Cartesian product of two sets. The first is countable, by the induction hypothesis; the second is countable by assumption. The result follows. (d) Left as an exercise. (e) Suppose, in order to derive a contradiction, that the elements of {0, 1}∞ (each of which is a binary sequences) can be arranged in a sequence s1 , s2 , . . .. Consider the binary sequence s whose kth entry is chosen to be different 6 from the kth entry of the sequence sk . This sequence s is certainly an element of {0, 1}∞ , but is different from each of the sequences sk , by construction. This means that the sequence s1 , s2 , . . . cannot exhaust all of the elements of {0, 1}∞ and therefore the latter set is uncountable. (f) Follows from (e) since 2A has at least as many elements as 2N , which can be identified with {0, 1}∞ . 5 SEQUENCES AND LIMITS Formally, a sequence of elements of a set A is a mapping f : N → A. Let ai = f (i). The corresponding sequence is often written as (a1 , a2 , . . .) or {ak } for short. Given a sequence {ak } and an increasing sequence of natural numbers {ki }, we can construct a new sequence whose ith element is aki . This new sequence is called a subsequence of {ak }. Informally, a subsequence of {ak } is obtained by skipping some of the elements of the original sequence. 7 Definition 3. (a) A sequence {xk } of real numbers (also called a “real sequence”) is said to converge to a real number x if for every  > 0 there exists some (positive integer) K such that |xk − x| <  for every k ≥ K. (b) A real sequence {xk } is said to converge to ∞ (respectively, −∞) if for every real number c there exists some K such that xk ≥ c (respectively, xk ≤ c) for all k ≥ K. (c) If a real sequence converges to some x (possibly infinite), we say that x is the limit of xk ; symbolically, limk→∞ xk = x. (d) A real sequence {xk } is called a Cauchy sequence if for every  > 0, there exists some K such that |xk − xm | <  for all k ≥ K and m ≥ K. (e) A real sequence {xk } is said to be bounded above (respectively, below) if there exists some real number c such that xk ≤ c (respectively, xk ≥ c) for all k. (f) A real sequence {xk } is called bounded if the sequence {|xk |} is bounded above. (g) A real sequence is said to be nonincreasing (respectively, nondecreasing) if xk+1 ≤ xk (respectively, xk+1 ≥ xk ) for all k. A sequence that is either nonincreasing or nondecreasing is called monotonic. The following result is a fundamental property of the real-number system, and is presented without proof. Theorem 2. Every monotonic real sequence converges to an extended real number. If the sequence is also bounded, then it converges to a real number. We continue with the definition of some key quantities associated with sets or sequences of real numbers. 8 Definition 4. (a) The supremum (or least upper bound) of a set A of real numbers, denoted by sup A, is defined as the smallest extended real number x such that x ≥ y for all y ∈ A. (b) The infimum (or greatest lower bound) of a set A of real numbers, denoted by inf A, is defined as the largest extended real number x such that x ≤ y for all y ∈ A. (c) Given a sequence {xk } of real numbers, the supremum of the sequence, denoted by supk xk , is defined as sup{xk | k = 1, 2, . . .}. The infimum of a sequence is similarly defined. (d) The upper limit of a real sequence {xk }, denoted by lim supk→∞ xk , is defined to be equal to limm→∞ sup{xk | k ≥ m}. (e) The lower limit of a real sequence {xk }, denoted by lim inf k→∞ xk , is defined to be equal to limm→∞ inf{xk | k ≥ m}. Remarks: (a) It turns out that the supremum and infimum of a set of real numbers is guaranteed to exist. This is a direct consequence of the way the real-number system is constructed (see, e.g., [R]). It can also be proved by building on Theorem 2. (b) The infimum or supremum of a set need not be an element of a set. For example, if A = {1/k | k ∈ N}, then inf A = 0, but 0 ∈ / A. (c) If sup A happens to also be an element of A, then sup A is the maximum (i.e., the largest element) of A, and in that case, it is also denoted as max A. Similarly, if inf A is an element of A, it is the minimum of A, and is denoted as min A. (d) If a set or a sequence of real numbers has arbitrarily large elements (that is, no finite upper bound), then the supremum is equal to ∞. Similarly, if it has arbitrarily small elements (that is, no finite lower bound), then the infimum is equal to −∞. (e) A careful application of the definitions shows that sup Ø = −∞ and inf Ø = ∞. On the other hand, if a set is nonempty, then inf A ≤ sup A. (f) A sequence need not have a limit (e.g., consider the sequence xn = (−1)n . On the other hand, the upper and lower limits of a real sequence are al9 ways defined. To see this, let ym = sup{xk | k ≥ m}. The sequence {ym } is nonicreasing and therefore has a (possibly infinite) limit. We have lim supm→∞ xk = limm→∞ ym , and the latter limit is guaranteed to exist, by Theorem 2. A similar argument applies to the lower limit. Theorem 3. Let {xk } be a real sequence. (a) There holds inf xk ≤ lim inf xk ≤ lim sup xk ≤ sup xk . k k→∞ k→∞ k (b) The sequence {xk } converges (to an extended real number) if and only if lim inf k→∞ xk = lim supk→∞ xk , and in that case, both of these quantities are equal to the limit of xk . The next definition refers to convergence of finite-dimensional real vectors. Definition 5. (a) A sequence {xk } of vectors in Rn is said to converge to some x ∈ Rn if the ith coordinate of xk converges to the ith coordinate of x, for every i. The notation limk→∞ xk = x is used again. (b) A sequence of vectors is called a Cauchy sequence (respectively, bounded) if each coordinate sequence is a Cauchy sequence (respectively, bounded). (c) We say that some x ∈ Rn is a limit point of a sequence {xk } in Rn if there exists a subsequence of {xk } that converges to x. (d) Let A be a subset of Rn . We say that x ∈ Rn is an limit point of A if there exists a sequence {xk }, consisting of elements of A, different from x, that converges to x. We summarize some key facts about convergence of vector-valued sequences, see, e.g., [R]. 10 Theorem 4. (a) A bounded sequence in Rn has at least one limit point. (b) A bounded sequence in Rn converges if and only if it has a unique limit point (in which case, the limit point is also the limit of the sequence). (c) A sequence in Rn converges to an element of Rn if and only if it is a Cauchy sequence. (d) Let {xk } be a real sequence. If lim supk→∞ xk (respectively, lim inf k→∞ xk ) is finite, then it is the largest (respectively, smallest) limit point of the sequence {xk }. 6 LIMITS OF SETS Consider a sequence {An } of sets. There are several ways of defining what it means for the sequence to converge to some limiting set. The definitions that will be most useful for our purposes are given below. Definition 6. (a) We define lim supn→∞ An as the set of all elements ω that belong to infinitely many of the sets An . Formally, lim sup An = n→∞ ∞  [ ∞ \ k=1  An . n=k The notation {An i.o.} = lim supn→∞ An is also used. (b) We define lim inf n→∞ An as the set of all ω that belong to all but finitely many of the sets An . Formally, lim inf An = n→∞ ∞ ∞  \ [ k=1  An . n=k (c) We say that A is the limit of the sequence An (symbolically, An → A, or limn→∞ An = A) if A = lim inf n→∞ An = lim supn→∞ An . Note that a sequence of sets An need not have a limit, but lim supn→∞ An and lim inf n→∞ An are always well defined. 11 In order to parse the above definitions, note that ω ∈ ∪∞ n=k An if and only if there exists some n ≥ k such that ω ∈ An . We then see that ω belongs to the ∞ intersection ∩∞ k=1 ∪n=k An if and only if for every k, there exists some n ≥ k such that ω ∈ An ; this is equivalent to requiring that ω belong to infinitely many of the sets An . ∞ Similarly, x ∈ ∪∞ k=1 ∩n=k An if and only if for some k, x belongs to ∞ ∩n=k An . Equivalently, for some k, x belongs to all of the sets Ak , Ak+1 , . . ., i.e., x belongs to all but finitely many of the sets An . When, the sequence of sets {An } is monotonic, the limits turn out to behave as expected. Theorem 5. (a) If An is an increasing sequence of sets (An ⊂ An+1 , for all n), then limn→∞ An exists and is equal to ∪∞ n=1 An . (b) If An is an decreasing sequence of sets (An ⊃ An+1 , for all n), then limn→∞ An exists and is equal to ∩∞ n=1 An . Reasoning about a sequence of functions is often easier than reasoning about the convergence of a sequence of sets. A link between the two notions of convergence is provided by the following. Definition 7. The indicator function IA : Ω → {0, 1} of a set A is defined by ( 1, if ω ∈ A, IA (ω) = 0, if ω ∈ / A. We then have the following result. Theorem 6. We have limn→∞ An = A if and only limn→∞ IAn (ω) = IA (ω) for all ω. Proof. To prove one direction of the result, we assume that limn→∞ An = A. Consider the two following cases: (i) Suppose that ω ∈ A. Since lim inf n→∞ An = A, ω belongs to all but 12 finitely many of the sets An , which implies that IAn (ω) = 1 for all but finitely many n. This establishes that limn→∞ IAn (ω) = 1 = IA (ω). (ii) Suppose now that ω ∈ / A. Since lim supn→∞ An = A, ω belongs to at most finitely many of the sets An , which implies that IAn (ω) = 0 for all but finitely many n. This establishes that limn→∞ IAn (ω) = 0 = IA (ω), and one direction of the desired result has been proved. To prove the reverse direction, we consider two cases. (i) The limit limn→∞ An exists, and is a set B different than A. Then either B \ A or A \ B is nonempty. Suppose B \ A is nonempty. Let ω ∈ B \ A. Then, by the part of the result that has already been established, limn→∞ IAn (ω) = IB (ω) = 1. However, ω ∈ / A and A = lim sup An , which means ω belongs to finitely many of the sets An . Thus, limn→∞ IAn (ω) = 0, which is a contradiction. Similarly, suppose A \ B is nonempty. Let ω ∈ A \ B. Then, by the part of the result that has already been established, limn→∞ IAn (ω) = IB (ω) = 0. However, ω ∈ A and A = lim inf An , which means ω belongs to all but finitely many of the sets An . Thus, limn→∞ IAn (ω) = 1, which is a contradiction. (ii) The limit limn→∞ An does not exist. In that case, we have lim inf n→∞ An < lim supn→∞ An . This implies that there exists some ω that belongs to infinitely many of the sets An , but also does not belong to infinitely many of those sets. In that case, IAn (ω) = 0, for infinitely many choices of n, and also IAn (ω) = 1, for infinitely many choices of n. This implies that the sequence IAn (ω) does not converge, and therefore the condition limn→∞ IAn (ω) = IA (ω), for every ω, cannot hold. 7 BOREL SETS We define the Borel σ-algebra in I = [0, 1] as the σ-algebra generated by the intervals of the form [a, b] = {x ∈ I | a ≤ x ≤ b}, where 0 ≤ a ≤ b ≤ 1. 13 Theorem 1. (a) {x} is a Borel set for any x ∈ I. (b) The set of rational numbers in [0, 1] is a Borel set. (c) All sets of the form (a, b] = {x ∈ I | a < x ≤ b} or (a, b) = {x ∈ I | a < x < b}, where 0 ≤ a < b ≤ 1, are Borel sets. (d) If S is an open set contained in I, then S is a Borel set. Proof. (a) This is because {x} is a set of the form [a, b] with a = b = x. Another interesting approach could also be used: for all x ∈ [0, 1), ∞ \ {x} = [x, x + (1/n)]. n=1 For x = 1, we write ∞ \ {1} = [1 − (1/n), 1]. n=1 (b) The set Q ∩ I of rational numbers in [0, 1] is countable, i.e., of the form {q1 , q2 , . . .}, where each qi is a different rational number. This set can therefore be written as the union of countably many sets of the form {qi }: Q∩I = ∞ [ {qi }. i=1 But a countable union of elements of a σ-algebra (in this instance, Borel sets) belongs to that σ-algebra. (c) Suppose that 0 ≤ a < b ≤ 1. Let k be a positive integer such that a + (1/k) < b − (1/k). Then, (a, b] = ∞ [ [a + (1/n), b]. n=k Similarly, (a, b) = ∞ [ [a + (1/n), b − (1/n)]. n=k 14 Note that we can also write (a, b) using complements of Borel sets:  c (a, b) = [0, a] ∪ [b, 1] . From this and part (a), we get (a, b] = (a, b) ∪ {b}. (d) A subset S of I is said to be open if for every x ∈ S, there exists an open interval (a, b) which is contained in S and which contains x. By assumption on S, every x ∈ S is contained in some interval (a, b) which is contained in S. Using the fact that rational numbers are dense in the reals, we can pick rational numbers qx and rx such that a < qx < x < rx < b. We see that any x ∈ S is contained in one of the above constructed intervals with rational endpoints. Therefore we can write S as the following union of (possibly uncountably many) open intervals: [ S= (qx , rx ). x∈S Since there are countably many rationals, the number of such intervals is countable. We conclude that S is a union of countably many intervals (which are Borel sets), and is therefore a Borel set. References [R] W. Rudin, Principles of Mathematical Analysis, McGraw Hill, 1976. 15