2.3. RELATIONS Definition 40 Let x be a partial ordering of X. An upper bound for a set A C X is an element u E X satisfying a x u, Vr E A. The supremum of a set is its least upper bound and when the set contains its supremum we call it a macimum. A lower bound for a set A C X is an element LE X satisfying I<, V E A. The infimum of a set is its greatest lower bound and when the set contains its infimum we call it a minimum Definition 41 A set s is bounded above if it has an upper bound; bounded below if it has a lower bound; bounded if it has an upper and lower bound unbounded if it lacks either an upper or a lower bound We define the operators Vy to denote the supremum and Ay the infimum of the two point set [ c, y. If X is a total order, then a and y are comparable, so that one must be bigger or smaller than the other in which case Vy= maxa, y and A y= min, y). However, if X is a partial order, then z and y may not be comparable but we can still find their supremum and infimum Definition 42 A lattice is a partially ordered set in which every pair of elements has a supremum and an infimum Exercise 2.3.4 Show that:(i)every finite set in a lattice has a supremum and an infimum; and (ii)if a latti tally ordered, then every pair of elements has a minimum and a marimum. Hint: (i) supa1, a2, I3] supisuP-T1, 25,L3 Exercise 2.3.5 Show that a totally ordered set L is always a lattice Next we give examples of partially oredered sets that are not totally rdered yet have a lattice structure. For any set X, an example is P(X)with C is a lattice where if A,B∈P(X), then AVB=A∪ B and A∧B=AnB. Example 43 Let X= a, b), so that P(X)=0, ta], b, a,b. Then, for instance, avb=a,b, aAb=o, aAa, b= a, and {a}={a} Here's another place where we don't have enough good symbols to go around. Dont confuse'V'and'A' here with the logical connectives in Chapter 1
2.3. RELATIONS 29 Definition 40 Let - be a partial ordering of X. An upper bound for a set A ⊂ X is an element u ∈ X satisfying x - u, ∀x ∈ A. The supremum of a set is its least upper bound and when the set contains its supremum we call it a maximum. A lower bound for a set A ⊂ X is an element l ∈ X satisfying l - x, ∀x ∈ A. The infimum of a set is its greatest lower bound and when the set contains its infimum we call it a minimum. Definition 41 A set S is bounded above if it has an upper bound; bounded below if it has a lower bound; bounded if it has an upper and lower bound; unbounded if it lacks either an upper or a lower bound. We define the operators x ∨ y to denote the supremum and x ∧ y the infimum of the two point set {x, y}. 6 If X is a total order, then x and y are comparable, so that one must be bigger or smaller than the other in which case x ∨ y = max{x, y} and x ∧ y = min{x, y}. However, if X is a partial order, then x and y may not be comparable but we can still find their supremum and infimum. Definition 42 A lattice is a partially ordered set in which every pair of elements has a supremum and an infimum. Exercise 2.3.4 Show that: (i) every finite set in a lattice has a supremum and an infimum; and (ii) if a lattice is totally ordered, then every pair of elements has a minimum and a maximum. Hint: (i) sup{x1, x2, x3} = sup{sup{x1, x2}, x3}. Exercise 2.3.5 Show that a totally ordered set L is always a lattice. Next we give examples of partially oredered sets that are not totally ordered yet have a lattice structure. For any set X, an example is P(X) with ⊂ is a lattice where if A, B ∈ P(X), then A∨B = A∪B and A∧B = A∩B.. Example 43 Let X = {a, b},so that P(X) = {∅, {a}, {b}, {a, b}}. Then, for instance, {a} ∨ {b} = {a, b}, {a} ∧ {b} = ∅, {a} ∧ {a, b} = {a}, and {a} ∨ ∅ = {a}. 6Hereís another place where we donít have enough good symbols to go around. Donít confuse ë∨í and í∧í here with the logical connectives in Chapter 1
CHAPTER 2. SET THEORY Example 44 R xr is a lattice with the ordering 1 The infimum and supremum of any two points y are given by Vy=(max1, y1, max-2, 321) and Ay=(min 1, 91, min c2, 321). See Figure 2.3.2 where we consider the noncomparable elements =(1, 0)and Example 45 The nect example shows that not every partially ordered set is a lattice. We show this by resorting to the following subset X=(1, 2)E R: a2+ 2<1. For <on X, sup(0, 1),(1,0) does not exist. See Figure While the next result is stated as a lemma, we will take it as an axiom. 7 It will prove useful in separation theorems which are used extensively economics Lemma 46(Zorn)If A is a partially ordered set such that each totally or- dered subset (a chain) has an upper bound in A, then a has a maximal element Example 47(1, 1)is the maximal element of 'on A=[0, 1]x0, 1].The upper bounds of each chain in A are given by the intersection of the lines (chains)with the x=l or y=1 ares. See Figure 2.3.4 ADD WELL ORDERING?? 2.4 Correspondences and Functions In your first economics classes you probably saw downward sloping demand and upward sloping supply functions, and perhaps even correspondences(e.g backward bending labor supply curves ). Given that we have already intro- duced the idea of a relation, here we will define correspondences and functions imply as a relation which has certain properties Definition 48 Let A and b be any two sets. A correspondence g, de noted G:A→→B, is a relation between A and p(B)(e.GcA×P(B) That is, G is a rule that assigns a subset G(a)c b to each element aE A It is can be shown to be equivalent to the Axiom of choice
30 CHAPTER 2. SET THEORY Example 44 R × R is a lattice with the ordering í¹1í. The infimum and supremum of any two points x, y are given by x∨y = (max{x1, y1}, max{x2, y2}) and x ∧ y = (min{x1, y1}, min{x2, y2}). See Figure 2.3.2 where we consider the noncomparable elements x = (1, 0) and y = (0, 1). Example 45 The next example shows that not every partially ordered set is a lattice. We show this by resorting to the following subset X = {(x1, x2) ∈ R : x2 1 + x2 2 ≤ 1}. For -1on X, sup{(0, 1),(1, 0)} does not exist. See Figure 2.3.3. While the next result is stated as a lemma, we will take it as an axiom.7 It will prove useful in separation theorems which are used extensively in economics. Lemma 46 (Zorn) If A is a partially ordered set such that each totally ordered subset (a chain) has an upper bound in A, then A has a maximal element. Example 47 (1, 1) is the maximal element of ë-1í on A = [0, 1]×[0, 1]. The upper bounds of each chain in A are given by the intersection of the lines (chains) with the x = 1 or y = 1 axes. See Figure 2.3.4. ADD WELL ORDERING??? 2.4 Correspondences and Functions In your first economics classes you probably saw downward sloping demand and upward sloping supply functions, and perhaps even correspondences (e.g. backward bending labor supply curves). Given that we have already introduced the idea of a relation, here we will define correspondences and functions simply as a relation which has certain properties. Definition 48 Let A and B be any two sets. A correspondence G, denoted G : A →→ B, is a relation between A and P(B) (i.e. G ⊂ A× P(B)). That is, G is a rule that assigns a subset G(a) ⊂ B to each element a ∈ A. 7It is can be shown to be equivalent to the Axiom of choice
2.4. CORRESPONDENCES AND FUNCTIONS 31 Definition 49 Let A and b be any two sets. A function(or mapping) f, denoted f: A-B, is a relation between A and B(i.e. fCAX B satisfying the following property: if (a, bEf and (a, b)E f, then b= 8 hat is, f is a rule that assigns a unique element f(a)e b to each a E A a is called the domain of f, sometimes denoted D(). The range of f, denoted R(),is{b∈B:∈ A such that(a,b)∈}. The graph of f is G()={(a,b)∈f:va∈A} Thus, a function can be thought of as a single valued correspondence. A function is defined if the following is given:(i) The domain D(f).(ii)An assignment rule a-f(a)=b, aE D(). Then R(f) is determined by these two. See Figure 2.4. la for a function and 2.4. 1b for a correspondence as well as Figure 2. 4. 2a and Figure 2.4.2b for another interpretation which emphasizes“ mapping Example 50 A sequence is a function f: N-B for some set B Definition 51 Let f be an arbitrary function with domain A and R()CB IfE C A, then the(direct)image of E under f, denoted f(E), is the subset ff(alaE EnDO)C R(). See Figure 2.4.3a Theorem 52 Let f be a function with domain A and R()C B and let E, FC A(a)IfEC F, then f(E)C f(F).(b)f(EnF)Cf(E)nf(F), (c)f(EU F)=f(E) f(F),(d)f(E\F)Cf(E) Proof.(a)Ifa∈E, then a∈Fsof(a)∈f(F). But this is true va∈E, hence f(E)Cf(F).■ Exercise 2.4.1 Finish the proof of Theorem 52 Definition 53 If H CB, then the inverse image of H under f, denoted f-(H), is the subset alf(aE C D(). See Figure 2.4.3b It is important to note that the inverse image is different from the inverse function(to be discussed shortly). The inverse function need not exist when the inverse image does. See Example 65 Theorem 54 Let G, H CB.(a)IfG C H,, then f-G)Cf-(H) f-I(GnH)=f-(G)nf-(H),(c)f(GUH)=f-I(G)Uf-(H) f-1(G\H)=f-1(G)f-1(H)
2.4. CORRESPONDENCES AND FUNCTIONS 31 Definition 49 Let A and B be any two sets. A function (or mapping) f, denoted f : A → B, is a relation between A and B (i.e. f ⊂ A × B) satisfying the following property: if (a, b) ∈ f and (a, b0 ) ∈ f, then b = b0 . That is, f is a rule that assigns a unique element f(a) ∈ B to each a ∈ A. A is called the domain of f,sometimes denoted D(f). The range of f, denoted R(f), is {b ∈ B : ∃a ∈ A such that (a, b) ∈ f}. The graph of f is G(f) = {(a, b)∈f : ∀a ∈ A}. Thus, a function can be thought of as a single valued correspondence. A function is defined if the following is given: (i) The domain D(f). (ii) An assignment rule a → f(a) = b, a ∈ D(f). Then R(f) is determined by these two. See Figure 2.4.1a for a function and 2.4.1b for a correspondence, as well as Figure 2.4.2a and Figure 2.4.2b for another interpretation which emphasizes ìmappingî. Example 50 A sequence is a function f : N → B for some set B. Definition 51 Let f be an arbitrary function with domain A and R(f) ⊂ B. If E ⊂ A,then the (direct) image of E under f, denoted f(E), is the subset {f(a)|a ∈ E ∩ D(f)} ⊂ R(f). See Figure 2.4.3a. Theorem 52 Let f be a function with domain A and R(f) ⊂ B and let E,F ⊂ A. (a) If E ⊂ F, then f(E) ⊂ f(F). (b) f(E ∩ F) ⊂ f(E) ∩ f(F), (c) f(E ∪ F) = f(E) ∪ f(F), (d) f(E\F) ⊂ f(E). Proof. (a) If a ∈ E,then a ∈ F so f(a) ∈ f(F). But this is true ∀a ∈ E, hence f(E) ⊂ f(F). Exercise 2.4.1 Finish the proof of Theorem 52. Definition 53 If H ⊂ B, then the inverse image of H under f, denoted f −1(H), is the subset {a|f(a) ∈ H} ⊂ D(f). See Figure 2.4.3b. It is important to note that the inverse image is different from the inverse function (to be discussed shortly). The inverse function need not exist when the inverse image does. See Example 65. Theorem 54 Let G, H ⊂ B. (a) If G ⊂ H,, then f −1(G) ⊂ f −1(H). (b) f −1(G ∩ H) = f −1(G) ∩ f −1(H), (c) f(G ∪ H) = f −1(G) ∪ f −1(H), (d) f −1(G\H) = f −1(G)\f −1(H)
CHAPTER 2. SET THEORY Proof.(a)Ia∈f-1(G), then f(a)∈G≌Hs0a∈f1(H).■ Exercise 2.4.2 Finish the proof of Theorem 54 Exercise 2.4.3 Let f: A-b be a function. Prove that the inverse images f-al) and f-a) are disjoint. FIX 2.4.1 Restrictions and extensions Example 55 Let A=RO and f(a)=. Then R()=R\O. See Figure 2.4 4a employ the idea of restricting or extending the function to a given sex e can To deal with the above"hole" in the domain of f in Example 55, we can Definition 56 Let C D(). The restriction of f to the set A, which we will denote升r△, is given by{(a,b)∈f:a∈}.Let△sD(f) he extension of f on the set A, which we will denote fleA, is given by f(a)a∈D(f) g(a)a∈△D(f) Example 57 See Figure 2.4.4b for a restriction of to A=R++ and Figure 2. 4.4c for an extension of i on A=R isb= Note that extensions are not generally unique 2.4.2 Composition of functions Definition 58 Let f: A-B and g: B-C. Let R(C B. The composition g o f is the function from a to C given by go f=l(a,c)E A×C:3b∈R(f)CB3(a,b)∈fand(b,c)∈g}. See Figure2.4.5 Note that order matters, as the next example shows Example 59 Let A C R, f(a)=2a, and g(a)=3a2-1. Then g o f 3(2a)2-1=12a2-1 while f o g=2(32-1)=6a2-2 s Alternatively, we create a new function h(a)=g(f(a))
32 CHAPTER 2. SET THEORY Proof. (a) If a ∈ f −1(G), then f(a) ∈ G ⊆ H so a ∈ f −1(H). Exercise 2.4.2 Finish the proof of Theorem 54. Exercise 2.4.3 Let f : A → B be a function. Prove that the inverse images f −1({a}) and f −1({a0 }) are disjoint. FIX 2.4.1 Restrictions and extensions Example 55 Let A = R\{0} and f(a) = 1 a. Then R(f) = R\{0}. See Figure 2.4.4a To deal with the above ìholeî in the domain of f in Example 55, we can employ the idea of restricting or extending the function to a given set. Definition 56 Let ∆ ⊂ D(f). The restriction of f to the set ∆, which we will denote f|r∆, is given by {(a, b) ∈ f : a ∈ ∆}. Let ∆ ⊃ D(f). The extension of f on the set ∆, which we will denote f|e∆, is given by ½ (a, b) : b = ½ f(a) a ∈ D(f) g(a) a ∈ ∆\D(f) æ . Example 57 See Figure 2.4.4b for a restriction of 1 a to ∆ = R++ and Figure 2.4.4c for an extension of 1 a on ∆ = R is ½ b = ½ 1 a a 6= 0 0 a = 0 æ . Note that extensions are not generally unique. 2.4.2 Composition of functions Definition 58 Let f : A → B and g : B0 → C. Let R(f) ⊂ B0 . The composition g ◦ f is the function from A to C given by g ◦ f = {(a, c) ∈ A × C : ∃b ∈ R(f) ⊂ B0 3 (a, b) ∈ f and (b, c) ∈ g}. 8 See Figure 2.4.5. Note that order matters, as the next example shows. Example 59 Let A ⊂ R, f(a)=2a, and g(a)=3a2 − 1. Then g ◦ f = 3(2a)2 − 1 = 12a2 − 1 while f ◦ g = 2(3a2 − 1) = 6a2 − 2. 8Alternatively, we create a new function h(a) = g(f(a))
2.4. CORRESPONDENCES AND FUNCTIONS 2.4.3 Injections and inverses Definition 60 f: A-B is one-to-one or an injection if whenever (a,b)∈fand(a',b)∈ f for a,d∈D(f), then a=a.9 Definition61 Let f be an injection.Jg={(b,a)∈B×A:(a,b)∈} then g is an injection with D(g)=R( and R(g= D(). The function g is called the inverse to f and denoted f-I. See Figure 2.4.6 2.4.4 Surjections and bijections Definition 62 If R(f=B, f maps A onto B (in this case, we call f a surjection ) See Figure 2. 4.7 Definition 63 f: A-B is a bijection if it is one-to-one and onto(or an injection and a surjection) Example 64 Let E=0,ICA=R, H=0, ICB=R, and f(a)=2a See Figure 2. 4.8. R()=R so that f is a surjection, the image set is f(E)=[0, 2 the inverse image set is f-(H)=[0, 3],f is an injection an has inverse f-(b)=5b, and as a consequence of being one-to-one and onto is a bijection. Notice that if F=[1,0, then f(F)n f(E)=10)and f(EnF)=f(0=01, so that in the special case of injections statement(b) of Theorem 52 holds with equality Example 65 Let E=0,ICA=R,H=0,1CB=R, and f(a)=a See Figure 2. 4.9. R(=R+ so that f is not a surjection, the image set is f(E)=0, 1, the inverse image set is f-(H)=[1,1, f is not an injection (since, for instance, f(1)=f(1)=1), and is obviously not a bijection However, the restriction of f to R+ or R-(in particalar, let += fR+ and f-≡fR-) is an injection and f.+()=√ while f.-1(b) b. finally notice that if F=[1, 0, then f(F)nf(E)=0, 1 but that f(En F) f(0)=0, which is why we cannot generally prove equality in statement(b)of Theorem 52 The next theorem shows that composition preserves surjection. It is useful to prove that statements about infinite sets. Alternatively, we can say f is one-to-one if f(a)=f(a) only when a =a
2.4. CORRESPONDENCES AND FUNCTIONS 33 2.4.3 Injections and inverses Definition 60 f : A → B is one-to-one or an injection if whenever (a, b) ∈ f and (a0 , b) ∈ f for a, a0 ∈ D(f), then a = a0 . 9 Definition 61 Let f be an injection. If g = {(b, a) ∈ B × A : (a, b) ∈ f}, then g is an injection with D(g) = R(f) and R(g) = D(f). The function g is called the inverse to f and denoted f −1. See Figure 2.4.6. 2.4.4 Surjections and bijections Definition 62 If R(f) = B, f maps A onto B (in this case, we call f a surjection). See Figure 2.4.7 Definition 63 f : A → B is a bijection if it is one-to-one and onto (or an injection and a surjection). Example 64 Let E = [0, 1] ⊂ A = R, H = [0, 1] ⊂ B = R, and f(a)=2a. See Figure 2.4.8. R(f) = R so that f is a surjection, the image set is f(E) = [0, 2],the inverse image set is f −1(H) = [0, 1 2 ], f is an injection and has inverse f −1(b) = 1 2 b, and as a consequence of being one-to-one and onto, is a bijection. Notice that if F = [−1, 0], then f(F) ∩ f(E) = {0} and f(E ∩F) = f(0) = {0},so that in the special case of injections statement (b) of Theorem 52 holds with equality. Example 65 Let E = [0, 1] ⊂ A = R, H = [0, 1] ⊂ B = R, and f(a) = a2. See Figure 2.4.9. R(f) = R+ so that f is not a surjection, the image set is f(E) = [0, 1],the inverse image set is f −1(H)=[−1, 1], f is not an injection (since, for instance, f(−1) = f(1) = 1), and is obviously not a bijection. However, the restriction of f to R+ or R− (in particular, let f+ ≡ f|rR+ and f− ≡ f|rR−) is an injection and f −1 + (b) = √ b while f −1 − (b) = − √ b. Finally, notice that if F = [−1, 0], then f(F) ∩ f(E) = [0, 1] but that f(E ∩ F) = f(0) = 0,which is why we cannot generally prove equality in statement (b) of Theorem 52. The next theorem shows that composition preserves surjection. It is useful to prove that statements about infinite sets. 9Alternatively, we can say f is one-to-one if f(a) = f(a0 ) only when a = a0