1. 3. BIBLIOGRAPHY FOR CHAPTER 1 Proof. By contradiction. Suppose a is not Pareto efficient. Let a' be a feasible allocation that all agents prefer to a. Then by the definition of Walrasian equlibrium, we can sum(1. 14) across all individuals to obtain ∑(∑m)>∑(∑)∑m(∑)>∑m yi. k Since ar'is a feasible allocation, summing(1. 13)over all goods we have ∑∑m≤∑∑班k (1.16) k But(1.15) and(1.16)imply ∑∑mk>∑∑mk which is a contradiction. Here B is the statement"a is Pareto Efficient". So the proof by contra- diction assumes N B, which is"Suppose a is not Pareto Efficient". In that case. by definition 4. there's a preferred allocation r which is feasible. But if a' is preferred to a, then it must cost too much if it wasnt chosen in the first place(this is 1.14). But this contradicts that a' was feasible 1.3 Bibliography for Chapter 1 An excellent treatment of this material is in McAffee(1986, Economics 241 handout). See also Munkres(1975, P. 7-9)and Royden(1988, p 2-3)
1.3. BIBLIOGRAPHY FOR CHAPTER 1 19 Proof. By contradiction. Suppose x is not Pareto efficient. Let x0 be a feasible allocation that all agents prefer to x. Then by the definition of Walrasian equlibrium, we can sum (1.14) across all individuals to obtain X i ÃX k pkx0 i,k! > X i ÃX k pkyi,k! ⇔ X k pk ÃX i x0 i,k! > X k pk ÃX i yi,k! . (1.15) Since x0 is a feasible allocation, summing (1.13) over all goods we have X k X i pkx0 i,k ≤ X k X i pkyi,k. (1.16) But (1.15) and (1.16) imply X k X i pkyi,k > X k X i pkyi,k, which is a contradiction. Here B is the statement îx is Pareto Efficientî. So the proof by contradiction assumes ∼ B, which is îSuppose x is not Pareto Efficientî. In that case, by definition 4, thereís a preferred allocation x0 which is feasible. But if x0 is preferred to x, then it must cost too much if it wasnít chosen in the first place (this is 1.14). But this contradicts that x0 was feasible. 1.3 Bibliography for Chapter 1 An excellent treatment of this material is in McAffee (1986, Economics 241 handout). See also Munkres (1975, p. 7-9) and Royden (1988, p. 2-3)
20 CHAPTER 1. INTRODUCTION
20 CHAPTER 1. INTRODUCTION
Chapter 2 Set theory The basic notions of set theory are those of a group of objects and the idea of membership in that group. In what follows, we will fir a given universe(or space) X and consider only sets(or groups)whose elements(or members are elements of X. We can express the notion of membership by"E"so that “∈A” neans“ is an element of the set a”and“xgA” Imeans“ r is not an element of A". Since a set is completely determined by its elements, we usually specify its elements explicitly by saying "The set A is the set of all elements in X such that each a has the property A (i.e. that a(r)is true and write A= aE X: A(). This also makes it clear that we identify sets with statements Example 7 Agent i's budget set, denoted B(p, yi)=aiEX: i Ck PRUik], is the set of all consumption goods that can be purchased with endowments i DDefinition8 If eacha∈ A is also in the set B (i.e.x∈A→x∈B,then we say A is a subset of B(denoted A C B). If ACB and 3r E B such that E A, then A is a proper subset of B. If C B, then it is equivalent to say that B contains A(denoted B 5 A) Definition 9 A collection is a set whose elements are subsets of X. The power set of X, denoted P(X), is the set of all possible subsets of X(it has 2*(x) elements, where #(X) denotes the number of elements(or cardinality) IIn those instances where the space is understood, we sometimes abbreviate this as A={x:A(x)}
Chapter 2 Set Theory The basic notions of set theory are those of a group of objects and the idea of membership in that group. In what follows, we will fix a given universe (or space) X and consider only sets (or groups) whose elements (or members) are elements of X. We can express the notion of membership by ì∈ î so that ì x ∈ Aî means ìx is an element of the set Aî and ì x /∈ Aî means ìx is not an element of Aî. Since a set is completely determined by its elements, we usually specify its elements explicitly by saying ìThe set A is the set of all elements x in X such that each x has the property A (i.e. that A(x) is true)î and write A = {x ∈ X : A(x)}. 1 This also makes it clear that we identify sets with statements. Example 7 Agent i 0 s budget set, denoted Bi(p, yi) = {xi ∈ X : P k P pkxi,k ≤ k pkyi,k}, is the set of all consumption goods that can be purchased with endowments yi. Definition 8 If each x ∈ A is also in the set B (i.e. x ∈ A ⇒ x ∈ B), then we say A is a subset of B (denoted A ⊂ B). If A ⊂ B and ∃x ∈ B such that x /∈ A, then A is a proper subset of B. If A ⊂ B, then it is equivalent to say that B contains A (denoted B ⊃ A). Definition 9 A collection is a set whose elements are subsets of X. The power set of X, denoted P(X), is the set of all possible subsets of X (it has 2#(X) elements, where #(X) denotes the number of elements (or cardinality) 1In those instances where the space is understood, we sometimes abbreviate this as A = {x : A(x)}. 21
CHAPTER 2. SET THEORY of the set X). A family is a set whose elements are collections of subsets of Definition 10 Two sets are equal if (a c b)A(B C a)(denoted A=B) Definition 11 A set that has no elements is called empty( eno {x:x∈X:A(x)∧(~A(x)} The empty set serves the same role in the theory of sets as 0 serves in the counting numbers; it is a placeholder Example 12 Let the universe be given by X= a, b, c. We could let A=a, b,b=c be subsets of X, C=A, B1, D=0, P(X)= 0, a], 0, c, a,bf,a,c, b,c, x) be collections, and F= c) be family The next result provides the first example of the relation between set theory and logical rules we developed in Chapter 1. In particular, it relates ”c”and”→” as well as”=”and”台 Theorem 13 Let A=E X: A() and B=aEX: B()).Then(a) AcB分(Vx∈X)(A(x)→B(x)amd(b)A=B分(x∈X)(A(x)兮 Proof. Just use definition(8)in(a)AcB兮x∈A→∈B分A(x)→ B(x) and definition(10)in(b)A=B兮(AcB)∧(BCA)兮(vx∈ X)(A(x)分B(x) The following are some of the most important sets we will ence this book ·N={1,2,3,…} the natural or“ counting"numbers. ·z={…,-2,-1,0,1,2,…}, the integers.Z+={0,1,2,…}, the non negative integers ·Q={m:m,n∈Z,n≠0}, the rational numbers Chapter 3 will discuss the real numbers, which we denote R. This set just adds what are called irrational numbers to the above rationals
22 CHAPTER 2. SET THEORY of the set X). A family is a set whose elements are collections of subsets of X. Definition 10 Two sets are equal if (A ⊂ B) ∧ (B ⊂ A) (denoted A = B). Definition 11 A set that has no elements is called empty (denoted ∅). Thus, ∅ = {x : x ∈ X : A(x) ∧ (∼ A(x))}. The empty set serves the same role in the theory of sets as 0 serves in the counting numbers; it is a placeholder. Example 12 Let the universe be given by X = {a, b, c}. We could let A = {a, b}, B = {c} be subsets of X, C = {A, B}, D = {∅},P(X) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, X} be collections, and F = {C} be a family. The next result provides the first example of the relation between set theory and logical rules we developed in Chapter 1. In particular, it relates î⊂î and î⇒î as well as î=î and î⇔î. Theorem 13 Let A = {x ∈ X : A(x)} and B = {x ∈ X : B(x)}.Then (a) A ⊂ B ⇔ (∀x ∈ X)(A(x) ⇒ B(x)) and (b) A = B ⇔ (∀x ∈ X)(A(x) ⇔ B(x)). Proof. Just use definition (8) in (a) A ⊂ B ⇔ x ∈ A ⇒ x ∈ B ⇔ A(x) ⇒ B(x) and definition (10) in (b) A = B ⇔ (A ⊂ B) ∧ (B ⊂ A) ⇔ (∀x ∈ X)(A(x) ⇔ B(x)). The following are some of the most important sets we will encounter in this book: ï N = {1, 2, 3, ...},the natural or ìcountingî numbers. ï Z = {..., −2, −1, 0, 1, 2, ...}, the integers. Z+ = {0, 1, 2, ...},the nonnegative integers. ï Q = {m n : m, n ∈ Z, n 6= 0}, the rational numbers. ï Chapter 3 will discuss the real numbers, which we denote R. This set just adds what are called irrational numbers to the above rationals
2.1. SET OPERATIONS The are several important results you will see at the end of this chapter The first establishes that there are fundamentally different sizes of infinite sets. While some infinite sets can be counted others are uncountable. These results are summarized in Theorem 71 and Theorem 80. The second re- sult establishes that there always exists a smallest collection of subsets of a given set where all results of set operations(like complements, union, and intersection)remain in the collection(Theorem 87) 2.1 Set Operations The following operations help us construct new sets from old ones. The first three play the same role for sets as the connectives“~”,“∧",and”v" played for statements Definition 14 If A C X, we define the complement of A(relative to X)(denoted A) to be the set of all elements of X that do not belong to A That is,A={x∈X:xgA Definition 15 If A, BCX, we define their intersection( denoted AnB) to be the set of all elements that belong to both A and B. That is, Anb= {x∈X:x∈A∧x∈B} Definition 16 If A, b C X and Anb= 0, then we say a and b are disjoint. Definition 17 If A,B CX, we define their union( denoted Au B) to be the set of all elements that belong to A or B or both(i. e. or is inclusive That is,AUB={x∈X:∈Ax∈B Definition 18 If A,B CX, we define their difference(or relative com- lement of a in b)( denoted a\b) to be the set of all elements of a that do not belong to B. That is,A\B={x∈X:x∈A∧xgB Each of these definitions can be visualized in Figure 2. 1.1 through the use of Venn Diagrams. These definitions can easily be extended to arbitrary collections of sets. Let A be an index set(e.g. A= Nor a finite subset of N and let a,i∈ a be subsets of x. Then UiEAA2={x∈X:(3)(x∈A)} Indexed families of sets will be defined formally after we develop the notion of a function in Section 5.2
2.1. SET OPERATIONS 23 The are several important results you will see at the end of this chapter. The first establishes that there are fundamentally different sizes of infinite sets. While some infinite sets can be counted, others are uncountable. These results are summarized in Theorem 71 and Theorem 80. The second result establishes that there always exists a smallest collection of subsets of a given set where all results of set operations (like complements, union, and intersection) remain in the collection (Theorem 87). 2.1 Set Operations The following operations help us construct new sets from old ones. The first three play the same role for sets as the connectives ì∼î, ì∧î, and î∨î played for statements. Definition 14 If A ⊂ X, we define the complement of A (relative to X) (denoted Ac ) to be the set of all elements of X that do not belong to A. That is, Ac = {x ∈ X : x /∈ A}. Definition 15 If A, B ⊂ X, we define their intersection (denoted A ∩ B) to be the set of all elements that belong to both A and B. That is, A ∩ B = {x ∈ X : x ∈ A ∧ x ∈ B}. Definition 16 If A, B ⊂ X and A ∩ B = ∅,then we say A and B are disjoint. Definition 17 If A, B ⊂ X, we define their union (denoted A ∪ B) to be the set of all elements that belong to A or B or both (i.e. or is inclusive). That is, A ∪ B = {x ∈ X : x ∈ A ∨ x ∈ B}. Definition 18 If A, B ⊂ X, we define their difference (or relative complement of A in B) (denoted A\B) to be the set of all elements of A that do not belong to B. That is, A\B = {x ∈ X : x ∈ A ∧ x /∈ B}. Each of these definitions can be visualized in Figure 2.1.1 through the use of Venn Diagrams. These definitions can easily be extended to arbitrary collections of sets. Let Λ be an index set (e.g. Λ = N or a finite subset of N) and let Ai, i ∈ Λ be subsets of X. Then ∪i∈ΛAi = {x ∈ X : (∃i)(x ∈ Ai)}. Indexed families of sets will be defined formally after we develop the notion of a function in Section 5.2