Lecture Notes on Mathematics for Economists

lecture notes in economics and mathematical systems and mathematics for economists an introductory textbook pdf free download
DanialOrton Profile Pic
DanialOrton,Hawaii,Professional
Published Date:09-07-2017
Your Website URL(Optional)
Comment
1 Lecture Notes on Mathematics for Economists by Takashi Kunimoto First Version: August 9, 2007 This Version: May 18, 2010 Summer 2010, Department of Economics, McGill University August 16 - 27 (tentative): Monday - Friday, 10:00am - 1:00pm; at TBA Instructor: Takashi Kunimoto Email: takashi.kunimotomcgill.ca Class Web: http://people.mcgill.ca/takashi.kunimoto/?View=Publications Office: Leacock 438 COURSE DESCRIPTION: This course is designed to provide you with mathematical tools that are extensively used in graduate economics courses. The topics which will be covered is • Sets and Functions; • Topology in the Euclidean Space; • Linear Algebra • Multivariate Calculus; • Static Optimization; • (Optional) Correspondences and Fixed Points; and • (Optional) The First-Order Differential Equations in One Variable. A good comprehension of the material covered in the notes is essential for successful graduate studies in economics. Since we are seriously time constrained – which you might not believe –, it would be very useful for you to carry one of the books provided below as a reference after you start to study in graduate school in September. READING: The main textbook of this course is “Further Mathematics for Economic Analysis.” I mostly use this book for the course. However, if you don’t find the main textbook helpful enough, I strongly recommend you that you should buy at least one of the other books I listed below as well as “Further Mathematics for Economic Analysis.” Of course, you can buy any math book which you find useful. 1 I am thankful to the students for their comments, questions, and suggestions. Yet, I believe that there are still many errors in this manuscript. Of course, all remaining ones are my own. 1• “Further Mathematics for Economic Analysis,” by Knut Sydsaeter, Peter Ham- mond, Atle Seierstad, and Atle Strom, Prentice Hall, 2005 (Main Textbook.If you don’t have any math book or are not confident about your math skill, this book will help you a lot.) • “Mathematical Appendix,” in Advanced Microeconomic Theory, Second Edition, by Geoffrey A. Jehle and Philip J. Reny, (2000), Addison Wesley (Supplementary. This is the main textbook for Econ 610 but the mathematical appendix of this book is too concise in many times) • “Mathematics for Economists,” by Simon and Blume, Norton, (1994). (Supple- mentary. This book is a popular math book in many Ph.D programs in economics. There has to be a reason for that, although I don’t know the true one.) • “Fundamental Methods of Mathematical Economics,” by A. Chiang, McGraw-Hill. (more elementary and supplementary) • “Introductory Real Analysis,” by A. N. Kolmogorov and S.V. Fomin, Dover Publi- cations (very very advanced and supplementary. If you really like math, this is the book for you.) OFFICE HOURS: Wednesday and Friday, 2:00pm - 3:00pm PROBLEM SETS: There will be several problem sets. Problem sets are essential to help you understand the course and to develop your skill to analyze economic problems. ASSESSMENT: No grade will be assigned. However, you are expected to do the problem sets assigned. 2Contents 1 Introduction 6 2 Preliminaries 9 2.1 Logic . . . .... ... .... ... ... .... ... .... ... ... .. 9 2.1.1 Necessity and Sufficiency . . . . .... ... .... ... ... .. 9 2.1.2 Theorems and Proofs . . . . . . .... ... .... ... ... .. 10 2.2 Set Theory . . . . . . .... ... ... .... ... .... ... ... .. 11 2.3 Relations .... ... .... ... ... .... ... .... ... ... .. 13 2.3.1 Preference Relations . . . . . . . .... ... .... ... ... .. 13 2.4 Functions .... ... .... ... ... .... ... .... ... ... .. 14 2.4.1 Least Upper Bound Principle . . .... ... .... ... ... .. 15 n 3 Topology in R 17 3.1 Sequences on R . ... .... ... ... .... ... .... ... ... .. 17 3.1.1 Subsequences . .... ... ... .... ... .... ... ... .. 18 3.1.2 Cauchy Sequences . . . . . . . . .... ... .... ... ... .. 19 3.1.3 Upper and Lower Limits . . . . . .... ... .... ... ... .. 20 3.1.4 Infimum and Supremum of Functions . . . . .... ... ... .. 21 3.1.5 Indexed Sets . .... ... ... .... ... .... ... ... .. 21 n 3.2 Point Set Topology in R .. ... ... .... ... .... ... ... .. 21 3.3 Topology and Convergence . . . . . . . .... ... .... ... ... .. 23 n 3.4 Properties of Sequences in R ... ... .... ... .... ... ... .. 24 3.5 Continuous Functions .... ... ... .... ... .... ... ... .. 26 4 Linear Algebra 29 4.1 Basic Concepts in Linear Algebra . . . . .... ... .... ... ... .. 29 4.2 Determinants and Matrix Inverses . . . .... ... .... ... ... .. 32 4.2.1 Determinants . .... ... ... .... ... .... ... ... .. 32 4.2.2 Matrix Inverses .... ... ... .... ... .... ... ... .. 32 4.2.3 Cramer’s Rule .... ... ... .... ... .... ... ... .. 33 4.3 Vectors . .... ... .... ... ... .... ... .... ... ... .. 34 4.4 Linear Independence . .... ... ... .... ... .... ... ... .. 35 4.4.1 Linear Dependence and Systems of Linear Equations . . . . . . . . 36 4.5 Eigenvalues . . . . . . .... ... ... .... ... .... ... ... .. 37 34.5.1 Motivations . . .... ... ... .... ... .... ... ... .. 37 4.5.2 How to Find Eigenvalues . . . . .... ... .... ... ... .. 39 4.6 Diagonalization . . . . .... ... ... .... ... .... ... ... .. 40 4.7 Quadratic Forms . . . .... ... ... .... ... .... ... ... .. 42 4.8 Appendix 1: Farkas Lemma . . . . . . . .... ... .... ... ... .. 44 4.8.1 Preliminaries . .... ... ... .... ... .... ... ... .. 45 4.8.2 Fundamental Theorem of Linear Algebra . . .... ... ... .. 46 4.8.3 Linear Inequalities . . . . . . . . .... ... .... ... ... .. 47 4.8.4 Non-Negative Solutions . . . . . .... ... .... ... ... .. 47 4.8.5 The General Case . . . . . . . . .... ... .... ... ... .. 49 4.9 Appendix 2: Linear Spaces . . . . . . . .... ... .... ... ... .. 49 4.9.1 Number Fields .... ... ... .... ... .... ... ... .. 49 4.9.2 Definitions . . .... ... ... .... ... .... ... ... .. 51 4.9.3 Bases, Components, Dimension . .... ... .... ... ... .. 52 4.9.4 Subspaces . . . .... ... ... .... ... .... ... ... .. 53 4.9.5 Morphisms of Linear Spaces . . . .... ... .... ... ... .. 54 5 Calculus 55 5.1 Functions of a Single Variable . . . . . . .... ... .... ... ... .. 55 5.2 Real-Valued Functions of Several Variables . . . . . .... ... ... .. 56 5.3 Gradients .... ... .... ... ... .... ... .... ... ... .. 56 5.4 The Directional Derivative . . . . . . . . .... ... .... ... ... .. 57 5.5 Convex Sets . . . . . . .... ... ... .... ... .... ... ... .. 58 5.5.1 Upper Contour Sets . . . . . . . .... ... .... ... ... .. 59 5.6 Concave and Convex Functions . . . . . .... ... .... ... ... .. 59 2 5.7 Concavity/Convexity for C Functions . .... ... .... ... ... .. 60 5.7.1 Jensen’s Inequality . . . . . . . . .... ... .... ... ... .. 63 5.8 Quasiconcave and Quasiconvex Functions . . . . . . .... ... ... .. 64 5.9 Total Differentiation . .... ... ... .... ... .... ... ... .. 68 5.9.1 Linear Approximations and Differentiability . .... ... ... .. 69 5.10 The Inverse of a Transformation . . . . .... ... .... ... ... .. 72 5.11 Implicit Function Theorems . . . . . . . .... ... .... ... ... .. 73 6 Static Optimization 77 6.1 Unconstrained Optimization . . . . . . . .... ... .... ... ... .. 77 6.1.1 Extreme Points .... ... ... .... ... .... ... ... .. 77 6.1.2 Envelope Theorems for Unconstrained Maxima . . . . . . . . . . . 78 6.1.3 Local Extreme Points . . . . . . .... ... .... ... ... .. 79 6.1.4 Necessary Conditions for Local Extreme Points . . . . . . . . . . . 80 6.2 Constrained Optimization . . . . . . . . .... ... .... ... ... .. 81 6.2.1 Equality Constraints: The Lagrange Problem .... ... ... .. 81 6.2.2 Lagrange Multipliers as Shadow Prices . . . . .... ... ... .. 84 6.2.3 Tangent Hyperplane . . . . . . . .... ... .... ... ... .. 84 6.2.4 Local First-Order Necessary Conditions . . . .... ... ... .. 85 46.2.5 Second-Order Necessary and Sufficient Conditions for Local Ex- treme Points . .... ... ... .... ... .... ... ... .. 85 6.2.6 Envelope Result for Lagrange Problems . . . .... ... ... .. 87 6.3 Inequality Constraints: Nonlinear Programming . . . .... ... ... .. 88 6.4 Properties of the Value Function . . . . .... ... .... ... ... .. 90 6.5 Constraint Qualifications . . . . . . . . .... ... .... ... ... .. 91 6.6 Nonnegativity Constraints . . . . . . . . .... ... .... ... ... .. 94 6.7 Concave Programming Problems . . . . .... ... .... ... ... .. 95 6.8 Quasiconcave Programming . . . . . . . .... ... .... ... ... .. 96 6.9 Appendix: Linear Programming . . . . . .... ... .... ... ... .. 96 7 Differential Equations 97 7.1 Introduction . . . . . . .... ... ... .... ... .... ... ... .. 97 8 Fixed Point Theorems 98 8.1 Banach Fixed Point Theorem . . . . . . .... ... .... ... ... .. 98 8.2 Brouwer Fixed Point Theorem . . . . . .... ... .... ... ... .. 99 9 Topics on Convex Sets 102 9.1 Separation Theorems . .... ... ... .... ... .... ... ... .. 102 9.2 Polyhedrons and Polytopes . . . . . . . .... ... .... ... ... .. 104 9.3 Dimension of a Set . . .... ... ... .... ... .... ... ... .. 105 9.4 Properties of Convex Sets . . . . . . . . .... ... .... ... ... .. 105 5Chapter 1 Introduction I start my lecture with Rakesh Vohra’s message about what economic theory is. He is a 1 professor at Northwestern University. All of economic theorizing reduces, in the end, to the solution of one of three problems. Given a function f and a set S: 1. Find an x such that f(x)is in S. This is the feasibility question. 2. Find an x in S that optimizes f(x). This is the problem of optimality. 3. Find an x in S such that f(x)= x, this is the fixed point problem. These three problems are, in general, quite difficult. However, if one is prepared to make assumptions about the nature of the underlying function (say it is linear, convex or continuous) and the nature of the set S (convex, compact etc.) it is possible to provide answers and very nice ones at that. I think this is the biggest picture of economic theory you could have as you go along this course. Whenever you are at a loss, please come back to this message. We build our theory on individuals. Assume that all commodities are traded in the centralized markets. Throughout Econ 610 and 620, we assume that each individual (consumer and firm) takes prices as given. We call this the price taking behavior assump- tion. You might ask why individuals are price takers. My answer would be “why not?” Let us go as far as we can with this behavioral assumption and thereafter try to see the limitation of the assumption. However, you have to wait for Econ 611 and 621 for how to relax this assumption. So, stick with this assumption. For each consumer, we want to know 1. What is the set of “physically feasible bundles? Is there any such a bundle at all (feasibility)? We call this set the consumption set. 1 See Preface of Advanced Mathematical Economics by Rakesh V. Vohra. 62. What is the set of “financially feasible bundles? Is there any such a bundle at all (feasibility)? We call this set the budget set. 3. What is the best bundle to the consumer among all feasible bundles (optimality)? We call this bundle the consumer’s demand. We can make the exact parallel argument for the firm. What is the set of “technically” feasible inputs (feasibility)? We call this the production set of the firm. What is the best combination of inputs to maximize its profit (optimality)? We call this the firm’s supply. Once we figure out what are feasible and best choices to each consumer and each firm under any possible circumstance, we want to know if there is any coherent state of affairs where everybody makes her best choice. In particular, all markets must clear. We call this coherent state “competitive (Walrasian) equilibrium.” (a fixed point). If we move from microeconomics to macroeconomics, we must pay special attention to time. Now, each individual’s budget set does depend upon time. At each point in time, he can change his asset portfolio so that he smoothes out his consumption plan and/or production plan over time. If you know exactly when you die, there is no problem. Because you just leave no money when you die, unless you want to leave some money to your kids (i.e., altruistic preferences). This is called the finite time horizon problem. What if you might live longer than you expected with no money left? Then, what do you do? So, in reality, you don’t know exactly when you die. This situation can be formulated as the infinite time horizon problem. Do you see why? To deal with the infinite horizon problem, we use the transversality condition as the terminal condition of the feasible set. Moreover, his optimization must be taken into account time. You can also analogously define a sequence of competitive equilibria of the economy. How can we summarize what we discussed above? Given a (per capita) consump- ∞ ∞ tion streamc , (per capita) capital accumulationk , (per capita) GDP stream t t t=0 t=0 ∞ f(k ) , capital depreciation rate δ, the population growth rate n, (per capita) con- t t=0 sumption growth g, instantaneous utility function of the representative consumer u(·), the effective discount rate of the representative consumerβ 0, (per capita) wage profile ∞ ∞ w , and capital interest rate profiler : t t t=0 t=0 ∞ ˙ 1. Find a c such that k = f(k )− c − (δ + g + n)k holds at each t≥ 1 and t t t t t t=0 k 0 is exogenously given. This is the feasibility question. Any suchc is called 0 t a feasible consumption stream.  ∞ ∞ −βt 2. Find a feasible consumption stream c that maximizes V = e u(c )dt. t 0 t t=0 0 This is the problem of optimality. I assume that V ∞. 0 ∞ 3. Find a r ,w such that V (the planner’s optimization) is sustained through t t 0 t=0 ˙ market economies where k =(r − n− g)k + w − c holds at each t ≥ 1 and t t t t t −βt another condition lim λ e k = 0 holds. This latter condition is sometimes t→∞ t t called the transversality condition. This is the fixed point problem. This, in fact,   can be done by choosing r = f (k )− δ and w = f(k )− f (k )k at each t≥ 1. t t t t t t t 7With appropriate re-interpretations, the above is exactly what we had in the begin- ning except the transversality condition, which is a genuine feature of macroeconomics. 8Chapter 2 Preliminaries 2.1 Logic Theorems provide a compact and precise format for presenting the assumptions and important conclusions of sometimes lengthy arguments, and so help identify immediately the scope and limitations of the result presented. Theorems must be proved and a proof consists of establishing the validity of the statement in the theorem in a way that is consistent with the rules of logic. 2.1.1 Necessity and Sufficiency Consider any two statements, p and q. When we say “p is necessary for q,” we mean that p must be true for q to be true. For q to be true requires p to be true, so whenever q is true, we know that p must also be true. So we might have said, instead, that “p is true if q is true,” or simply that “p is implied by q”(p⇐ q). Suppose we know that “p⇐ q” is a true statement. What if p is not true? Because p is necessary for q, when p is not true, then q cannot be true, either. But doesn’t this just say that “q not true” is necessary for “p not true”? Or that “not-q” is implied by “not-p”(¬q⇐¬p). This latter form of the original statement is called the contrapositive form. Let’s consider a simple illustration of these ideas. Let p be the statement, “x is an integer less than 10.” Let q be the statement that “x is an integer less than 8.” Clearly, p is necessary for q (q⇒ p). If we form the contrapositive of these two statements, the statement ¬p becomes “x is not an integer less than 10,” and “x is not an integer less than 8.” Then, observe that¬q⇐¬p. However,¬p⇐¬q is false. The value of x could well be 9. The notion of necessity is distinct from that of sufficiency. When we say “p is sufficient for q,” we mean that whenever p holds, q must hold. We can say, “p is true only if q is true,” or that “p implies q”(p⇒ q). Once again, whenever the statement 9“p⇒ q” is true, the contrapositive statement, “¬q⇒¬p” is also true. Two implications, “p ⇐ q” and “p ⇒ q,” can both be true. When this is so, I say that “p is necessary and sufficient for q,” or “p is true if and only if q is true,” or “p iff q.” When “p is necessary and sufficient for q,” we say that the statements p and q are equivalent and write “p⇔ q.” To illustrate briefly, suppose that p and q are the following statements: • p≡ “X is yellow,” • q≡ “X is a lemon.” Certainly, if X is a lemon, then X is yellow. Here, p is necessary for q. At the same time, just because X is yellow does not mean that it must be a lemon. It could be a banana. So p is not sufficient for q. 2.1.2 Theorems and Proofs Mathematical theorems usually have the form of an implication or an equivalence, where one or more statements are alleged to be related in particular ways. Suppose we have the theorem “p ⇒ q.” Here, p is the assumption and q is the conclusion. To prove a theorem is to establish the validity of its conclusion given the truth of its assumption, and several methods can be used to do that. 1. In a constructive proof, we assume that p is true, deduce various consequences of that, and use them to show that q must also hold. This is also sometimes called a direct proof, for obvious reasons. 2. In a contrapositive proof, we assume that q does not hold, then show that p cannot hold. This approach takes advantage of the logical equivalence between the claims “p⇒ q” and “¬q⇒¬p” noted earlier, and essentially involves a constructive proof of the contrapositive to the original statement. 3. In a proof by contradiction, the strategy is to assume that p is true, assume that q is not true, and attempt to derive a logical contradiction. This approach relies on the fact that p⇒ q or¬q always is true and if “p⇒¬q” is false, then p⇒ q must be true. 4. In a proof by mathematical induction, I have a statement H(k) which does depend upon a natural number k. What I want to show is that a statement H(k) is true for each k=1,2,... . First, I show that H(1) is true. This step is usually easy to establish. Next, I show that H(k)=⇒ H(k +1), i.e., if H(k) is true, then H(k+1) is also true. These two steps allows me to claim that I am done. If I assert that p is necessary and sufficient for q, or that “p⇔ q,” we must give a proof in “both directions.” That is, both “p ⇒ q” and “q ⇒ p” must be established before a complete proof of the assertion has been achieved. 10It is important to keep in mind the old saying that goes, “Proof by example is no proof.” Suppose the following two statements are given: • p≡ “x is a student,” • q≡ “x has red hair.” Assume further that we make the assertion “p⇒ q.” Then clearly finding one student with red hair and pointing him out to you is not going to convince you of anything. Examples are good for illustrating but typically not for proving. Finally, a sort of converse to the old saying about examples and proofs should be noted. Whereas citing a hundred examples can never prove that a certain property always holds, citing one solitary counterexample can disprove that the property always holds. For instance, to disprove the assertion about the color of students’ hair, you need simply point out one student with brown hair. A counterexample proves that the claim cannot always be true because you have found at least one case where it is not. 2.2 Set Theory A set is any collection of elements. Sets of objects will usually be denoted by capital letters, A,S,T for example, while their members by lower case, a,s, t for example (English or Greek). A set S is a subset of another set T if every element of S is also an element of T. We write S⊂ T.If S⊂ T, then x∈ S⇒ x∈ T. The set S is a proper subset of T if S⊂ T and S = T; sometimes one writes S  T in this case. Two sets are equal sets if they each contain exactly the same elements. We write S = T whenever x∈ S⇒ x∈ T and x ∈ T ⇒ x ∈ S. The number of elements in a set S, its cardinality, is denoted S. The upside down “A,”∀, means “for all,” while the backward “E,”∃ means “there exists.” A set S is empty or is an empty set if it contains no elements at all. It is a subset 2 of “every” set. For example, if A = x x =0,x 1, then A is empty. We denote the empty set by the symbol ∅. The complement of a set S in a universal set U is the c set of all elements in U that are not in S and is denoted S . For any two sets S and T in a universal set U, we define the set difference denoted S\T, as all elements in the set c S that are not elements of T. Thus, we can think S = U\S. The symmetric difference ST =(S\T)∪ (T\S) is the set of all elements that belong to exactly one of the sets S and T. Note that if S = T, then ST =∅. For two sets S and T, we define the union of S and T as the set S∪T≡x x∈Sor x∈ T. We define the intersection of S and T as the set S∩ T≡x x ∈ S and x∈ T. Let Λ≡1,2,3,... be an index set. In stead of writing S ,S ,S ,..., we can write 1 2 3  S . We would denote the union of all sets in the collection by S , and the λ λ∈Λ λ λ∈Λ  intersection of all sets in the collection as S . λ λ∈Λ 11The following are some important identities involving the operations defined above. • A∪ B = B∪ A, (A∪ B)∪ C = A∪ (B∪ C),A∪∅ = A • A∩ B = B∩ A, (A∩ B)∩ C = A∩ (B∩ C),A∩∅ =∅ • A∪(B∩C)=(A∪B)∩(A∪C),A∩(B∪C =(A∩B)∪(A∩C) (Distribute laws) • A\(B∪ C)=(A\B)∩ (A\C),A\(B∩ C)=(A\B)∪ (A\C) (De Morgan’s laws) • AB = BA, (AB)C = A(BC),A∅ = A The collection of all subsets of a set A is also a set, called the power set of A and denoted byP(A). Thus, B∈P(A)⇐⇒ B⊂ A. Example 2.1 Let A =a,b,c. Then,P(A)=∅,a,b,c,a,b,a, c,b, c,a,b,c. The previous argument reveals its stance that the order of the elements in a set specification does not matter. In particular,a,b =b,a. However, on many occasions, one is interested in distinguishing between the first and the second elements of a pair. One such example is the coordinates of a point in the x− y-plane. These coordinates are given as an ordered pair (a,b) of real numbers. The important property of ordered pairs is that (a,b)=(c,d) if and only if a = c and b = d. The product of two sets S and T is the set of “ordered pairs” in the form (s,t), where the first element in the pair is a member of S and the second is a member of T. The product of S and T is denoted S× T≡(s,t) s∈ S, t∈ T. The set of real numbers is denoted by the special symbol R and is defined as R≡x−∞x∞. Any n-tuple, or vector, is just an n dimensional ordered tuple (x ,... ,x ) and can 1 n be thought of as a “point” in n dimensional Euclidean space. This space is defined as the set product n R ≡ R×···× R≡(x ,... ,x ) x ∈ R,i=1,... ,n. 1 n i    n times n Often, we want to restrict our attention to a subset of R , called the “nonnegative n orthant” and denoted R , where + n n R ≡(x ,... ,x ) x ≥ 0,i=1,... ,n⊂ R . 1 n i + n Furthermore, we sometimes talk about the strictly “positive orthant” of R n n R ≡(x ,... ,x ) x 0,i=1,... ,n⊂ R . 1 n i ++ + 122.3 Relations Any ordered pair (s,t) associates an element s∈ S to an element t∈ T.Any collection of ordered pairs is said to constitute a binary relation between the sets S and T. Many familiar binary relations are contained in the product of one set with itself. For example, let X be the closed unit interval, X =0,1. Then the binary relation≥ consists of all ordered pairs of numbers in X where the first one in the pair is greater than or equal to the second one. When, as here, a binary relation is a subset of the product of one set X with itself, we say that it is a relation on the set X. A binary relation R on X is represented by the subset of X× X, i.e.,R⊂ X× X. We can build more structure for a binary relation on some set by requiring that it possesses certain properties. Definition 2.1 A relation R in X is reflexive if xRx for all x∈ X. For example,≥ and = on R are reflexive, while is not. Definition 2.2 A relationR on X is complete if, for all elements x and y in X, xRy or yRx. For example, ≥ on R is complete, while and = are not. Note that R on X is reflexive if it is complete. Definition 2.3 A relation R on X is transitive if, for any three elements x,y, and z∈ X, xRy and yRz implies xRz. For instance, all≥,=, on R are transitive. Definition 2.4 A relation R on X is symmetric if xRy implies yRx and it is anti- symmetric if xRy and yRx implies x = y. For example, = is symmetric, while≥ and are not. However,≥ is anti-symmetric, while is not as well. A relationR is said to be a partial ordering on X if it is reflexive, transitive, and anti-symmetric. If a partial ordering is complete, it is called a linear ordering. For instance, the relation≥ in R is a linear ordering. n For n ≥ 2, the less-than-or-equal-to relation ≥ on R is defined by (x ,... ,x ) ≥ 1 n (y ,... ,y ) if and only if x ≥ y for k =1,... ,n. There is also a strict inequality 1 n k k relation , which is given by (x ,... ,x ) (y ,... ,y ) if and only if x y for all 1 n 1 n k k k=1,... ,n. 2.3.1 Preference Relations I now talk a little bit about economics. Here I apply the concept of relations to the consumer choice problem. The number of commodities is finite and equal to n. Each n commodity is measured in some infinitely divisible units. Let x =(x ,... ,x ) ∈ R 1 n + n be a consumption bundle. Let R be a consumption set that is the set of bundles the + consumer can conceive. We represent the consumer’s preferences by a binary relation, 13 n , defined on the consumption set, R .If x x , we say that “x is at least as good as +  x ,” for this consumer. Definition 2.5 The binary relation  on X is said to be strict preference relation    if, x x if and only if x x but x  x. Definition 2.6 The binary relation ∼ on X is said to be indifference relation if,    x∼ x if and only if x x and x  x. Exercise 2.1 Show the following: n 1.  on R is reflexive if it is complete. + n 2.  on R is not symmetric. + n 3. ∼ on R is symmetric. + 2.4 Functions A function is a relation that associates each element of one set with a single, unique element of another set. We say that the function f is a mapping, map,or transformation from one set D to another set R and write f : D → R. We call the set D the domain and the set R the range of the mapping. If y is the point in the range mapped into by the point x in the domain, we write y = f(x). In set-theoretic terms, f is a relation from D to R with the property that for each x∈ D, there is exactly one y∈ R such that xfy (x is related to y via f). The image of f is that set of points in the range into which some point in the domain is mapped, i.e., I≡y y = f(x) for some x∈ D⊂ R. The inverse image of a set of points S⊂ I is defined as −1 f (S)≡x x∈ D, f(x)∈ S . The graph of the function f is the set of ordered pairs G≡(x,y) x∈ D, y = f(x). If f(x)= y, one also writes x→  y. The squaring function s : R→ R, for example, 2 can then be written as s : x→ x . Thus, →  indicates the effect of the function on an element of the domain. If f : A→ B is a function and S⊂ A, the restriction of f to S is the function f defined by f (x)= f(x) for every x ∈ S. There is nothing in the S S definition of a function that prohibits more than one element in the domain from being mapped into the same element in the range. If, however, every point in the range is assigned to “at most” a single point in the domain, the function is said to be one-to-one, 14   that is, for all x,x ∈ D, whenever f(x)= f(x ), then x = x . If the image is equal to the range - if for every y ∈ R, there is x ∈ D such that f(x)= y, the function is said to be onto. If a function is one-to-one and onto (sometimes called bijective), then an −1 inverse function f : R→ D exists that is also one-to-one and onto. The composition of a function f : A→ B and a function g : B → C is the function g◦ f : A→ C given by (g◦ f)(a)= g(f(a)) for all a∈ A. 2 Exercise 2.2 Show that f(x)= x is not a one-to-one mapping. 2.4.1 Least Upper Bound Principle A set S of real numbers is bounded above if there exists a real number b such that b≥ x for all x∈ S. This number b is called an upper bound for S. A set that is bounded above ∗ has many upper bounds. A least upper bound for the set S is a number b that is an ∗ upper bound for S and is such that b ≤ b for every upper bound b. The existence of a least upper bound is a basic and non-trivial property of the real number system. Fact 2.1 (Least Upper Bound Principle) Any nonempty set of real numbers that is bounded above has a least upper bound. This principle is rather an axiom of real numbers. A set S can have at most one least ∗ ∗ ∗ ∗ upper bound, because if b and b are both least upper bounds for S, then b ≤ b and 1 2 1 2 ∗ ∗ ∗ ∗ ∗ b ≤ b , which thus implies that b = b . The least upper bound b of S is often called 2 1 1 2 ∗ ∗ the supremum of S. We write b = supS and b = sup x. x∈S Example 2.2 The set S =(0,5), consisting of all x such that 0 x 5, has many upper bounds, some of which are 100, 6.73, and 5. Clearly no number smaller than 5 can be an upper bound, so 5 is the least upper bound. Thus, supS =5. A set S is bounded below if there exists a real number a such that x≥ a for all x∈ S. The number a is a lower bound for S. A set S that is bounded below has a greatest ∗ ∗ ∗ lower bound a , with the property a ≤ x for all x∈ S, and a ≥ a for all lower bounds ∗ ∗ ∗ a. The number a is called the infimum of S and we write a = inf S or a = inf x. x∈S Thus, we summarize • supS = the least number greater than or equal to all numbers in S; and • inf S = the greatest number less than or equal to all numbers in S. ∗ ∗ Theorem 2.1 Let S be a set of real numbers and b a real number. Then supS = b if and only if the following two conditions are satisfied: ∗ 1. x≤ b for all x∈ S. ∗ 2. For each ε 0, there exists an x∈ S such that xb − ε. 15∗ Proof of Theorem 2.1:(=⇒) Since b is an upper bound for S, by definition, ∗ property 1 holds, that is, x≤ b for all x∈ S. Suppose, on the other hand, that there ∗ ∗∗ ∗ is some ε 0 such that x ≤ b − ε for all x ∈ S. Define b = b − ε. This implies ∗∗ ∗∗ ∗ that b is also an upper bound for S and b b . This contradicts our hypothesis that ∗ ∗ b is a least upper bound for S.(⇐=) Property 1 says that b is an upper bound for ∗ S. Suppose, on the contrary, that b is not a least upper bound. That is, there is some ∗ ∗ other b such that x ≤ b b for all x ∈ S. Define ε = b − b. Then, we obtain that ∗ x≤ b − ε for all x∈ S. This contradicts property 2.  16Chapter 3 n Topology in R 3.1 Sequences on R A sequence is a function k →  x(k) whose domain is the set 1,2,3,... of all pos- itive integers. I denote the set of natural numbers by N = 1,2,.... The terms x(1),x(2),... ,x(k),... of the sequence are usually denoted by using subscripts: x ,x ,... ,x ,... . 1 2 k ∞ We shall use the notationx , or simplyx , to indicate an arbitrary sequence of k k k=1 real numbers. A sequencex of real numbers is said to be k 1. nondecreasing if x ≤ x for k=1,2,... k k+1 2. strictly increasing if x x for k=1,2,... k k+1 3. nonincreasing if x ≥ x for k=1,2,... k k+1 4. strictly decreasing if x x for k =1,2,... k k+1 A sequence that is nondecreasing or nonincreasing is called monotone. A sequence x is said to converge to a number x if x becomes arbitrarily close to x for all k k sufficient large k. We write lim x = x or x → x as k→∞. The precise definition k→∞ k k of convergence is as follows: Definition 3.1 The sequence x converge to x if for every ε 0, there exists a k natural number N such that x − x ε for all k N . The number x is called ε k ε the limit of the sequence x .A convergent sequence is one that converges to some k number. Note that the limit of a convergent sequence is unique. A sequence that does not converge to any real number is said to diverge. In some cases we use the notation lim x even if the sequencex is divergent. For example, we say that x →∞ as k→∞ k k k k→∞. A sequencex is bounded if there exists a number M such thatx≤ M for k k all k =1,2,... . It is easy to see that every convergent sequence is bounded:If x → x, k by the definition of convergence, only finitely many terms of the sequence can lie outside the interval I =(x− 1,x + 1). The set I is bounded and the finite set of points from the 17sequence that are not in I is bounded, sox must be bounded. On the other hand, is k k every bounded sequence convergent? No. For example, the sequencey =(−1) is k bounded but not convergent. Theorem 3.1 Every bounded monotone sequence is convergent. Proof of Theorem 3.1: Suppose, without loss of generality, that x is nonde- k ∗ creasing and bounded. Let b be the least upper bound of the set X =x k=1,2,..., k and letε 0 be an arbitrary number. Theorem 2.1 already showed that there must be a ∗ term x of the sequence for which x b − ε. Because the sequence is nondecreasing, N N ∗ ∗ b −εx ≤ x for all kN. But the x are all less than or equal to b because of N k k ∗ ∗ boundedness, so we have b −ε x ≤ b . Thus, for any ε 0, there exists a number k ∗ ∗ N such thatx − b ε for all kN. Hence,x converges to b .  k k Theorem 3.2 Suppose that the sequences x and y converge to x and y, respec- k k tively. Then, 1. lim (x ± y )= x± y k→∞ k k 2. lim (x · y )= x· y k→∞ k k 3. lim (x /y )= x/y, assuming that y =0 for all k and y =0. k→∞ k k k Exercise 3.1 Prove Theorem 3.2. 3.1.1 Subsequences Letx be a sequence. Consider a strictly increasing sequence of natural numbers k k k k ··· 1 2 3 ∞ and form a new sequence y , where y = x for j =1,2,... . The sequence j j k j=1 j y =x is called a subsequence ofx . j j k j k j Theorem 3.3 Every subsequence of a convergent sequence is itself convergent, and has the same limit as the original sequence. Proof of Theorem 3.3: It is trivial.  Theorem 3.4 If the sequence x is bounded, then it contains a convergent subse- k quence. Proof of Theorem 3.4: Since x is bounded, we can assume that there exists k some M ∈ R such that x≤ M for all k ∈ N. Let y = supx k ≥ n for n ∈ N. n k k By construction, y is a nonincreasing sequence because the set x k ≥ n shrinks n k as n increases. The sequence y is also bounded because −M ≤ y ≤ M. Theorem n n 3.1 already showed that the sequence y is convergent. Let x = lim y . By the n n→∞ n 18definition of y , we can choose a term x n from the original sequencex (with k ≥ n) n k k n satisfyingy − x 1/n. n kn x− x =x− y + y − x ≤x− y +y − x x− y +1/n. k n n k n n k n n n n This shows that x → x as n→∞.  k n 3.1.2 Cauchy Sequences I have defined the concept of convergence of sequences. Then, a natural question arises as to how we can check if a given sequence is convergent. The concept of Cauchy sequence, indeed, enables us to do so. Definition 3.2 A sequence x of real numbers is called a Cauchy sequence if for k every ε 0, there exists a natural number N such thatx − x ε for all m,n N . ε m n ε The theorem below is a characterization of convergent sequences. Theorem 3.5 A sequence is convergent if and only if it is a Cauchy sequence. Proof of Theorem 3.5:(=⇒) Suppose that x converges to x. Given ε 0, k we can choose a natural number N such that x − x ε/2 for all nN. Then, for n m,n N, x − x =x − x + x− x ≤x − x +x− x ε/2+ ε/2= ε. m n m n m m Therefore, x is a Cauchy sequence. (⇐=) Suppose that x is a Cauchy sequence. k k First, we shall show that the sequence is bounded. By the Cauchy property, there is a number M such thatx −x 1 forkM. Moreover, the finite setx ,x ,... ,x k M 1 2 M−1 is clearly bounded. Hence, x is bounded. Theorem 3.4 showed that the bounded k sequencex has a convergent subsequencex . Let x = lim x . Becausex is a k k j k k j j Cauchy sequence, for everyε 0, there is a natural number N such thatx −x ε/2 m n for all m,n N. If we take J is sufficiently large, we havex − xε/2 for alljJ. k j Then for kN and j maxN,J, x − x =x − x + x − x≤x − x +x − xε/2+ ε/2= ε k k k k k k k j j j j Hence x → x as k→∞.  k Exercise 3.2 Consider the sequence x with the generic term k k 1 1 1 1 x = + +··· + = k 2 2 2 2 1 2 k i i=1 19Prove that this sequence is a Cauchy sequence. Hint: 1 1 1 + +··· + 2 2 2 (n+1) (n+2) (n + k) 1 1 1 + +··· + n(n+1) (n + 1)(n+2) (n + k− 1)(n + k) 1 1 1 1 1 1 = − + − +··· + − n n+1 n+1 n+2 n + k− 1 n + k Exercise 3.3 Prove that a sequence can have at most one limit. Use proof by contra- diction. Namely, you first suppose, by way of contradiction, that there are two limit points. 3.1.3 Upper and Lower Limits Let x be a sequence that is bounded above, and define y = supx k ≥ n for k n k n =1,2,... . Each y is a finite number and y is a nonincreasing sequence. Then n n either lim y exists or is−∞. We call this limit the upper limit (or lim sup) of the n→∞ n sequencex , and we introduce the following notation: k lim supx = lim (supx k≥ n) k k n→∞ k→∞ If x is not bounded above, we write lim sup x = ∞. Similarly, if x is k k k k→∞ bounded below, its lower limit (or lim inf, is defined as lim inf x = lim (infx k≥ n) k k n→∞ k→∞ Ifx is not bounded below, we write lim inf x =−∞. k k→∞ k Theorem 3.6 If the sequence x is convergent, then k lim supx = lim inf x = lim x . k k k k→∞ k→∞ k→∞ On the other hand, if lim supx = lim inf x , then x is convergent. k→∞ k k→∞ k k I omit the proof of Theorem 3.6. Exercise 3.4 Determine the limsup and lim inf of the following sequences. k 1. x =(−1) k k 2. x = (−1) (2 + 1/k)+1 k 20