Lecture 2: Logic, Sets, and Topology
Advanced Microeconomics I
Yosuke YASUDA
National Graduate Institute for Policy Studies
October 8, 2013
Announcement
Course website You can find my corse websites from the link below: https://sites.google.com/site/yosukeyasuda/Home/teaching
Lecture slides Uploaded on the website after the lecture. Textbooks There are two main textbooks:
JR Jehle and Reny, Advanced Microeconomic Theory, 3rd.
→ The copies of related chapters will be distributed in class. NS Nicholson and Snyder, Microeconomic Theory: Basic
Principles and Extensions, 11th (older versions would be OK). Symbols that we use in lectures
✞
✝
☎
Ex : Example,✆ ✞
✝
☎
Fg : Figure,✆ ✞
✝
☎
Rm : Remark,✆ ✞
✝
☎
Q : Question,✆ Def : Definition, Thm : Theorem, ...
Introduction
The main focus of Advanced Microeconomics I is to study individual economic decisions and their aggregate consequences. To this end, we rely on powerful mathematical methods that help extend our insights into areas beyond the reach of our intuition and experience.
✞
✝
☎
Rm Economic theory differs substantially from pure mathematics:✆ combination of a mathematical model and its interpretation.
◮ Many of important ideas in economics literature are stated in the form of theorems.
◮ We shall first study some of the basic languages and simple rules of logic, which are necessary to understand/prove theorems.
Logic: Consider any two statements, A and B.
A is necessary for B Whenever B is true, A must also be true.
◮ A is true if B is true.
◮ A is implied by B (A ⇐ B).
A is sufficient for B Whenever A is true, B must also be true.
◮ A is true only if B is true.
◮ A implies B (A ⇒ B).
A is necessary and sufficient for B A ⇐ B and A ⇒ B.
◮ A is true if and only if (often written as iff) B is true.
◮ A and B are equivalent (A ⇐⇒ B).
The contrapositive of “A ⇒ B” is “not B ⇒ not A.”
→ The contrapositive is equivalent to the original statement.
Theorem and Proof
Mathematical theorems usually have the form of implication (⇒) or an equivalence (⇔).
To prove a theorem is to establish the validity of its conclusion.
✞
✝
☎
Q How to prove a theorem, say “A ⇒ B”?✆ 1. Constructive proof (direct proof)
Assume that A is true, deduce various consequences of that, and use them to show that B must also hold.
2. Contrapositive proof
Assume that B does not hold, then show that A cannot hold. 3. Proof by contradiction
Assume that A is true and that B is not true, and attempt to derive a logical contradiction.
✞
✝
☎
Rm To prove an equivalent statement “A ⇔ B,” we can simply✆ give a proof in both directions (A ⇒ B and A ⇐ B), separately.
Examples
✞
✝
☎
Ex1 A is a statement “x is an integer less than 4,” and B is a✆ statement “x is an integer less than 6.”
1. x is either 1, 2 or 3, each of which must be smaller than 6. 2. Suppose x is greater than or equal to 6. Then, clearly, it must
be greater than or equal to 4.
3. Suppose x is smaller than 4. Clearly, it cannot be the case that x is greater than or equal to 6.
✞
✝
☎
Ex2 A = “y is a number which is multiple of 4”; B = “y is an✆ even number.”
✞
✝
☎
Ex3 A = “z is a student”; B = “z has black hair.”✆
◮ Proof by example is no proof.
◮ Counter example can disprove that property always holds.
Set (1)
How to describe sets
◮ A set is any collection of elements, e.g., S = {2, 4, 6, 8} or S = {x|x is an even integer greater than 0 and less than 10}.
◮ To denote inclusion in a set, we use the symbol ∈, e.g., 4 ∈ S.
◮ A set is empty (or an empty set denoted by φ) if it contains no element at all.
Relationship between sets
◮ A set S is a subset of another set T if every element of S is also an element of T .
◮ S is contained in T (or, T contains S), and write S ⊂ T .
◮ That is, if S ⊂ T , then x ∈ S ⇒ x ∈ T .
Set (2)
◮ Two sets are equal sets (S = T ) if they each contain exactly the same elements.
◮ The set difference, S \ T or S − T , is a set of elements in the set S that are not elements of T .
◮ The complement of a set S in a universal set U is the set of all elements in U that are not in S, i.e., U \ S, denoted Sc.
✞
✝
☎
Fg Venn Diagrams: Figure A1.1 (see JR, pp.498)✆
There are two basic operations on sets: union and intersection. They correspond to logical notion of “or” and “and,” respectively.
◮ Union of S and T : S ∪ T := {x|x ∈ S or x ∈ T }
◮ Intersection of S and T : S ∩ T := {x|x ∈ S and x ∈ T }
Set (3)
◮ The (Cartesian) product of two sets S and T , denoted by S× T , is the set of (all) ordered pairs in the form (s, t).
◮ First element in the pair is a member of S and the second is T .
◮ S× T := {(s, t)|s ∈ S, t ∈ T }
◮ The set of (all) real numbers is denoted by R.
◮ R := {x| − ∞ < x < ∞}
◮ In later lectures, we often restrict our attention to a subset of Rn(:= R × R × · · · × R
ntimes
), called the nonnegative orthant.
◮ Rn
+:= {(x1, ..., xn)|xi≥ 0, i = 1, ..., n} ⊂ Rn
◮ For any two vectors x and y in Rn, we say that
◮ x≥ y iff xi≥ yi, i= 1, ..., n.
◮ x≫ y iff xi > yi, i= 1, ..., n.
Mapping (1)
Def A function is a relation that associates each element of one set with a single, unique element of another set. If more than one point is assigned, then such a relation is called a correspondence.
◮ Function f is mapping from one set D to another set R in which D is called the domain and R is the range.
◮ We write such function as f : D → R .
◮ The graph of function f is the set of ordered pairs: G:= {(x, y)|x ∈ D, y = f (x)}
✞
✝
☎
Fg Figure A1.8 (see JR, pp.505)✆
→ Definitions of image and inverse image will be given later.
Mapping (2)
Several mappings
◮ If every point in range is assigned to at most a single point in the domain, the function is called one-to-one. That is, f : D → R is a one-to-one function (or injection) if f(x) = f (y) implies that x = y.
◮ If every point in the range is mapped into by some point in the domain, the function is said to be onto. That is, f : D → R is an onto function (or surjection) if for every y∈ R there is an x ∈ D such that f (x) = y.
◮ If the function f : D → R is a one-to-one and onto function (or bijection, or one-to-one correspondence) if for every y∈ R there is a unique x ∈ D such that f (x) = y.
✞
✝
☎
Ex Counter examples: Figure A1.7 (see JR, pp.504).✆
Topology and Space
Def Topology is the study of fundamental properties of sets and mappings. A metric is simply a measure of distance.
A metric space is just a set with notion of distance defined among the points within the set.
◮ Euclidean metricon Rn is defined as follows. For x1 and x2 in Rn,
d(x1, x2) :=p(x1− x2) · (x1− x2)
= q
(x11− x21)2+ (x12− x22)2+ · · · + (x1n− x2n)2.
◮ The metric space Rn that uses the Euclidean metric as the measure of distance is called Euclidean space.
Open Set and Closed Set (1)
How to define open or closed sets
◮ The open ε-ball with center x0 and radius ε > 0 is the subset of points in Rn:
Bε(x0) := {x ∈ Rn|d(x0, x)<ε}
◮ The closed ε-ball with center x0 and radius ε > 0 is the subset of points in Rn:
Bε∗(x0) := {x ∈ Rn|d(x0, x)≤ε}
◮
✞
✝
☎
Fg A1.10 (see JR, pp.508)✆
◮ S ⊂ Rn is an open set if, for all x ∈ S, there exists some ε >0 such that Bε(x) ⊂ S.
◮ S is a closed set, if its compliment, Sc, is an open set.
Open Set and Closed Set (2)
Boundary and interior
◮ A point x is called a boundary point of a set S in Rnif every ε-ball centered at x contains points in S as well as points not in S. The set of all boundary points of a set S is called boundary, and is denoted ∂S .
◮ A point x is called an interior point of S if there is some ε-ball centered at x is entirely contained within S, or if there exist some ε > 0 such that Bε(x0) ⊂ S. The set of all interior points of a set S is called interior, and is denoted intS .
◮ A set is open if it contains nothing but interior points, or if S = intS . A set is closed if it contains all its interior points plus all its boundary points, or if S = intS ∪ ∂S .
✞
✝
☎
Fg Figure A1.13 (see JR, pp.512)✆
Open Set and Closed Set (3)
Thm A1.2 The followings sets are open sets. 1. The empty set, φ.
2. The entire space, Rn. 3. The union of open sets.
4. The intersection of any finite number of open sets. Thm A1.4 The following sets are closed sets.
1. The empty set, φ. 2. The entire space, Rn.
3. The union of any finite collection of closed sets. 4. The intersection of closed sets.
