14 CHAPTER 1. INTRODUCTION obvious from the previous theorem. A Definition is a statement that is true by interpreting one of its terms in such a way as to make the statement true An Ariom or Assumption is a statement that is taken to be true without proof. A Tautology is a statement which is true without assumptions(for np ) A Contradiction is a statement that cannot be true(for example, A is true and A is false) There are other important logical connectives for statements be and“兮”:“∧” means“and”;“V" means“or';and“” means meaning of these connectives is given by a truth table, where"T" stands for a true statement and"F" stands for a false statement. One can consider the truth table as an axiom AB~ AAABJAVBJA→BA F he truth table a is true and i is fals Then n a is false since a is true.aab is false since b is. Vb is true since at least one statement(A)is true, A=B is false since A can't imply B when A is true and B isn't. Notice that if A is false, then a= B is always true since B can be anythin Manipulating these connectives, we can prove some useful tautologies The first set of tautologies are the commutative, associative, and distributive laws. To prove these tautologies, one can simply generate the appropriate truth table. For example, the truth table to prove (AV(BAC)+((avb)a (AVC) is ABCIBAC| AV(BACAVBJAVCI(A∨BA(A以 TITIT TFFFT TTTTTTFF TTTTTFTF TTTTTFFF FFIF F
14 CHAPTER 1. INTRODUCTION obvious from the previous theorem. A Definition is a statement that is true by interpreting one of its terms in such a way as to make the statement true. An Axiom or Assumption is a statement that is taken to be true without proof. A Tautology is a statement which is true without assumptions (for example, x = x). A Contradiction is a statement that cannot be true (for example, A is true and A is false). There are other important logical connectives for statements besides ì⇒î and ì⇔î: ì∧î means ìandî; ì∨î means ìorî; and ì∼î means ìnotî. The meaning of these connectives is given by a truth table, where ìTî stands for a true statement and ìFî stands for a false statement. One can consider the truth table as an Axiom. Table 1 A B ∼ A A ∧ B A ∨ B A ⇒ B A ⇔ B T T F T T T T T F F F T F F F T T F T T F F F T F F T T To read the truth table, consider row two where A is true and B is false. Then ∼ A is false since A is true, A ∧ B is false since B is, A ∨ B is true since at least one statement (A) is true, A ⇒ B is false since A canít imply B when A is true and B isnít. Notice that if A is false, then A ⇒ B is always true since B can be anything. Manipulating these connectives, we can prove some useful tautologies. The first set of tautologies are the commutative, associative, and distributive laws. To prove these tautologies, one can simply generate the appropriate truth table. For example, the truth table to prove (A∨(B∧C) ⇔ ((A∨B)∧ (A ∨ C)) is: A B C B ∧ C A ∨ (B ∧ C) A ∨ B A ∨ C (A ∨ B) ∧ (A ∨ C) T T T T T T T T T T F F T T T T T F T F T T T T T F F F T T T T F T T T T T T T F T F F F T F F F F T F F F T F F F F F F F F F
1. 1. RULES OF LOGIC Since every case in which A V (BAC)is true or false, so is(AVB)A(AvC) the two statements are equivalent Theorem 1 Let A, B, and c be any statements. Then (A∨B)分(BVA)and(A∧B)兮(B∧A) (1.1 (A∨B)∨C)兮(AV(BVC)and(A∧B)∧C)兮(A∧(B∧C)(1.2) (AV(B∧C)兮((AVB)∧(AVC)and(A∧(B∨C)兮(AAB)V(A∧C)(1.3) Exercise 1.1.1 Complete the proof of Theorem 1 The next set of results form the basis of the methods of logical reasoning we will be pursuing in this book. The first(direct) approach(1. 4)is the syllogism, which says that "if A is true and A implies B, then B is true". The second(indirect) approach(1.5) is the contradiction, which says in words that "if not a leads to a false statement of the form b and not b. then a is true. That is, one way to prove A is to hypothesize A, and show this leads to a contradiction. Another(indirect)approach(1.6)is the contrapositive which says that"A implies B is the same as whenever B is false, A is false Theorem 2 AA(A→B)→B (~A)→(B∧(~B))→A (A→B)兮(~B)→(~A)) (1.6) Proof. Before proceeding, we need a few results(we could have established these in the form of a lemma, but we 're just starting here). The first result we need is that (A→B)兮(~A)VB and the second is ~(~A)兮A The result follows from ABfA→Bry
1.1. RULES OF LOGIC 15 Since every case in which A ∨ (B ∧ C) is true or false, so is (A∨B)∧(A∨C), the two statements are equivalent. Theorem 1 Let A, B, and C be any statements. Then (A ∨ B) ⇔ (B ∨ A) and (A ∧ B) ⇔ (B ∧ A) (1.1) ((A ∨ B) ∨ C) ⇔ (A ∨ (B ∨ C)) and ((A ∧ B) ∧ C) ⇔ (A ∧ (B ∧ C)) (1.2) (A∨(B∧C) ⇔ ((A∨B)∧(A∨C)) and (A∧(B∨C)) ⇔ (A∧B)∨(A∧C)) (1.3) Exercise 1.1.1 Complete the proof of Theorem 1. The next set of results form the basis of the methods of logical reasoning we will be pursuing in this book. The first (direct) approach (1.4) is the syllogism, which says that ìif A is true and A implies B, then B is trueî. The second (indirect) approach (1.5) is the contradiction, which says in words that ìif not A leads to a false statement of the form B and not B, then A is true. That is, one way to prove A is to hypothesize ∼ A, and show this leads to a contradiction. Another (indirect) approach (1.6) is the contrapositive, which says that ìA implies B is the same as whenever B is false, A is falseî. Theorem 2 (A ∧ (A ⇒ B)) ⇒ B (1.4) ((∼ A) ⇒ (B ∧ (∼ B))) ⇒ A (1.5) (A ⇒ B) ⇔ ((∼ B) ⇒ (∼ A)). (1.6) Proof. Before proceeding, we need a few results (we could have established these in the form of a lemma, but weíre just starting here). The first result1 we need is that (A ⇒ B) ⇔ ((∼ A) ∨ B) (1.7) and the second is ∼ (∼ A) ⇔ A. (1.8) 1The result follows from A B A ⇒ B ∼ A ∨ B T T T T
16 CHAPTER 1. INTRODUCTION In the case of(.4,(A∧(A→B)当(AA(~A)∨B)(A A)V(A∧B)→ B by table1.1 In the case of (1.5),( A)+(BA( B)))2(AV(BA(B)))= by table 1.1 In the case of(1.6),(A=B)9(A)VB)+(BV(A)+ (~(~B)(~A)(~B)→(~A) Note that the contrapositive of“A→B” is not the same as the converse of“A→B”, which is“B→A Another important way to"construct"complicated statements from sim- le ones is by the use of quantifiers. In pal a quantifie statement A(a)to vary across elements .c in some universe U. For example, could be a price(whose universe is always positive)with the property that demand equals supply. When there is an a with the property a(a), we write C r)A() to mean that for some x in U, A(a) is true. 2 In the context of the previous example, this establishes there exists an equilibrium price. When ill a have the property a(), we write (Va)a() to mean that for all a, a() is true. There are obvious relations between“彐”and"v. In particular ~(x)A(x)分(x)(A(x) ~(x)A(x)兮(x)(A(x) (1.10) The second tautology is important since it illustrates the concept of a coun- tererample. In particular,(1.10)states"If it is not true that a(a) is tru for all a, then there must exist a counterexample(that is, an a satisfying A(a)), and vice versa. Counterexamples are an important tool, since while hundreds of examples do not make a theorem, a single counterexample kills one One should also note that the symmetry we experienced with""and A"in(1. 1)to(1.3)may break down with quantifiers. Thus while (x)(A(x)VB(x)兮(3(x)A(x)V(x)B(x) (1.11) can be expressed as a tautology (i.e. +") it's the case that ()(A(x)∧B(x)→(3(x)A(x)∧3(x)B(x) (1.12) Thus, we let“3” denote" for some”or” there exists a denote” for all
16 CHAPTER 1. INTRODUCTION In the case of (1.4), (A ∧ (A ⇒ B)) (1.7) ⇔ (A ∧ ((∼ A) ∨ B)) (1.3) ⇔ (A ∧ (∼ A)) ∨ (A ∧ B)) ⇒ B by table 1.1. In the case of (1.5), ((∼ A) ⇒ (B ∧ (∼ B))) (1.7) ⇔ (A ∨ (B ∧ (∼ B))) ⇒ A by table 1.1. In the case of (1.6), (A ⇒ B) (1.7) ⇔ ((∼ A) ∨ B) (1.1) ⇔ (B ∨ (∼ A)) (1.8) ⇔ (∼ (∼ B) ∨ (∼ A)) (1.7) ⇔ ((∼ B) ⇒ (∼ A)). Note that the contrapositive of ìA ⇒ Bî is not the same as the converse of ìA ⇒ Bî, which is ìB ⇒ Aî. Another important way to ìconstructî complicated statements from simple ones is by the use of quantifiers. In particular, a quantifier allows a statement A(x) to vary across elements x in some universe U. For example, x could be a price (whose universe is always positive) with the property that demand equals supply. When there is an x with the property A(x), we write (∃x)A(x) to mean that for some x in U, A(x) is true.2 In the context of the previous example, this establishes there exists an equilibrium price. When all x have the property A(x), we write (∀x)A(x) to mean that for all x, A(x) is true.3There are obvious relations between ì∃î and î∀î. In particular ∼ ((∃x)A(x)) ⇔ (∀x) (∼ A(x)) (1.9) ∼ ((∀x)A(x)) ⇔ (∃x) (∼ A(x)). (1.10) The second tautology is important since it illustrates the concept of a counterexample. In particular, (1.10) states ìIf it is not true that A(x) is true for all x, then there must exist a counterexample (that is, an x satisfying ∼ A(x)), and vice versa. Counterexamples are an important tool, since while hundreds of examples do not make a theorem, a single counterexample kills one. One should also note that the symmetry we experienced with ì∨î and î∧î in (1.1) to (1.3) may break down with quantifiers. Thus while (∃x) (A(x) ∨ B(x)) ⇔ (∃(x)A(x) ∨ ∃(x)B(x)) (1.11) can be expressed as a tautology (i.e. ì⇔î), itís the case that (∃x) (A(x) ∧ B(x)) ⇒ (∃(x)A(x) ∧ ∃(x)B(x)) (1.12) 2Thus, we let ì∃î denote îfor someî or îthere exists aî. 3Thus, we let ì∀î denote îfor allî
1. 2. TAXONOMY OF PROOFS cannot be expressed that way (i.e. it is only"="). To see why(.12)cannot hold as an" if and only ifstatement, suppose a is the set of countries in the world, A(r)is the property that a is above average gross domestic product and B() is the property that a is below average gross domestic product, then there will be at least one country above the mean and at least one country below the mean(i.e.((a)A()A3(a)B(a) is true), but clearly there cannot be a country that is both above and below the mean (i.e. 3r)(A()AB() is false) We can make increasingly complex statements by addir variables (e.g. the statement A(a, y) can vary across elements z and y in universe U ) For instance, when A(, y) states that "y that is larger than a"where and y are in the universe of real numbers, the statement (V )( y)(r< y says "for every t there is a y that is larger than " while the statement y)(Va)(ar y) says "there is a y which is larger than every a". Note, however the former statement is true. but the latter is false 1.2 Taxonomy of Proofs While the previous section introduced the basics of the rules of logic(how to manipulate connectives and quantifiers to establish the truth of statements) here we will discuss broadly the methodology of proofs you will frequently encounter in economics. The most intuitive is the direct proof in the form of A=B, discussed in(1.4). The work is to fill in the intermediate steps so that A→A1andA1→A2and..An-1→ B are all tautologies n some cases, it may be simpler to prove a statement like A= B by splitting B into cases. For example, if we wish to prove the uniqueness of the least upper bound of a set A C R, we can consider two candidate least upper bounds a, and t, in A and split B into the cases where we assume a1 is the least upper bound implying 1 2 and another case where we assume T2 s the least upper bound implying2≤x1,But(x1≤x2)∧(x2≤x1)→ (1=a2)so that the least upper bound is unique. In other instances, one might want to split A into cases(call them A and A2), show A+(AVA and then show A= A and A2=>A. For example, to prove (0≤x≤1)→(x2≤x) we can use the fact that ≤x≤1)分(x=0V0<x≤1)
1.2. TAXONOMY OF PROOFS 17 cannot be expressed that way (i.e. it is only î⇒î). To see why (1.12) cannot hold as an îif and only ifî statement, suppose x is the set of countries in the world, A(x) is the property that x is above average gross domestic product and B(x) is the property that x is below average gross domestic product, then there will be at least one country above the mean and at least one country below the mean (i.e. (∃(x)A(x) ∧ ∃(x)B(x)) is true), but clearly there cannot be a country that is both above and below the mean (i.e. (∃x) (A(x) ∧ B(x)) is false). We can make increasingly complex statements by adding more variables (e.g. the statement A(x, y) can vary across elements x and y in some universe Ue). For instance, when A(x, y) states that ìy that is larger than xî where x and y are in the universe of real numbers, the statement (∀x)(∃y)(x<y) says ìfor every x there is a y that is larger than xî, while the statement (∃y)(∀x)(x<y) says ìthere is a y which is larger than every xî. Note, however, the former statement is true, but the latter is false. 1.2 Taxonomy of Proofs While the previous section introduced the basics of the rules of logic (how to manipulate connectives and quantifiers to establish the truth of statements), here we will discuss broadly the methodology of proofs you will frequently encounter in economics. The most intuitive is the direct proof in the form of ìA ⇒ Bî, discussed in (1.4). The work is to fill in the intermediate steps so that A ⇒ A1 and A1 ⇒ A2 and ... An−1 ⇒ B are all tautologies. In some cases, it may be simpler to prove a statement like A ⇒ B by splitting B into cases. For example, if we wish to prove the uniqueness of the least upper bound of a set A ⊂ R, we can consider two candidate least upper bounds x1 and x2 in A and split B into the cases where we assume x1 is the least upper bound implying x1 ≤ x2 and another case where we assume x2 is the least upper bound implying x2 ≤ x1. But (x1 ≤ x2) ∧ (x2 ≤ x1) ⇒ (x1 = x2) so that the least upper bound is unique. In other instances, one might want to split A into cases (call them A1 and A2), show A ⇔(A1 ∨ A2) and then show A1 ⇒ A and A2 ⇒ A. For example, to prove (0 ≤ x ≤ 1) ⇒ ° x2 ≤ x ¢ we can use the fact that (0 ≤ x ≤ 1) ⇔ (x = 0 ∨ (0 < x ≤ 1))
18 CHAPTER 1. INTRODUCTION where the latter case allows us to consider the truth of B by dividing through Another direct method of proof, called induction, works only for the nat- al numbers N=0, 1, 2, 3, .. Suppose we wish to show (VnEN)A( true. This is equivalent to proving A(0)∧(wn∈N)(A(m)→A(n+1).This works since a(O) is true and a(0)→A(1)andA(1)→A(②2) and so on.In the next chapter, after we introduce set theory, we will show why induction work As discussed before, two indirect forms of proof are the contrapositive (1.6)and the contradiction(1.5). In the latter case, we use the fact that A→B)分(A∧(~B) and show(AA(~B) leads to a contradiction (BA( B)). Since direct proofs seem more natural than indirect proofs, we now give an indirect proof of the First Welfare Theorem, perhaps one of the most important things you will learn in all of economics. It is so simple, that it is hard to find a direct counterpart. 4 Definition 3 Given a finite vector of endowments y, an allocation a is fea sible if for each good k ≤k where the summation is over all individuals in the economy there is no feasible allocation r' such that all agents prefer r to. cation if Definition 4 A feasible allocation is a Pareto efficient all Definition 5 An allocation-price pair(, p) in a competitive erchange econ- omy is a Walrasian equilibrium if it is feasible and if i is preferred by to i, then each agent i is maximized in his budget set ∑xk>∑队k (i.e. i's tastes outweigh his pocketbook) Theorem 6( First Fundamental Theorem of Welfare Economics)If(a, p) is a walrasian equilibrium, then is Pareto efficient See Debreu(1959, p. 94)
18 CHAPTER 1. INTRODUCTION where the latter case allows us to consider the truth of B by dividing through by x. Another direct method of proof, called induction, works only for the natural numbers N ={0, 1, 2, 3, ...}. Suppose we wish to show (∀n ∈ N) A(n) is true. This is equivalent to proving A(0)∧(∀n ∈ N) (A(n) ⇒ A(n + 1)). This works since A(0) is true and A(0) ⇒ A(1) and A(1) ⇒ A(2) and so on. In the next chapter, after we introduce set theory, we will show why induction works. As discussed before, two indirect forms of proof are the contrapositive (1.6) and the contradiction (1.5). In the latter case, we use the fact that ∼ (A ⇒ B) ⇔ (A ∧ (∼ B)) and show (A ∧ (∼ B)) leads to a contradiction (B ∧ (∼ B)). Since direct proofs seem more natural than indirect proofs, we now give an indirect proof of the First Welfare Theorem, perhaps one of the most important things you will learn in all of economics. It is so simple, that it is hard to find a direct counterpart.4 Definition 3 Given a finite vector of endowments y, an allocation x is feasible if for each good k, X i xi,k ≤ X i yi,k (1.13) where the summation is over all individuals in the economy. Definition 4 A feasible allocation x is a Pareto efficient allocation if there is no feasible allocation x0 such that all agents prefer x0 to x. Definition 5 An allocation-price pair (x, p) in a competitive exchange economy is a Walrasian equilibrium if it is feasible and if x0 i is preferred by i to xi, then each agent i is maximized in his budget set X k pkx0 i,k > X k pkyi,k (1.14) (i.e. iís tastes outweigh his pocketbook). Theorem 6 (First Fundamental Theorem of Welfare Economics) If (x, p) is a Walrasian equilibrium, then x is Pareto efficient. 4See Debreu (1959, p.94)