BECC-102 Mathematical Methods for Economics-I PDF

BECC-102 MATHEMATICAL METHODS FOR ECONOMICS-I School of Social Sciences Indira Gandhi National Open University EXPERT COMMITTEE Prof. Indrani Roy Choudhary Prof. M.S. Bhatt Ms. Nit...

BECC-102 MATHEMATICAL METHODS FOR ECONOMICS-I School of Social Sciences Indira Gandhi National Open University EXPERT COMMITTEE Prof. Indrani Roy Choudhary Prof. M.S. Bhatt Ms. Niti Arora Professor, Jawaharlal Nehru University Prof. Jamia Millia Islamia Assistant Professor New Delhi New Delhi Mata Sundri College, DU Prof. S. K. Singh Prof. Anup Chatterjee Prof. Narayan Prasad Retd. Professor of Economics Rtd. Associate Professor Professor of Economics IGNOU, New Delhi. ARSD College, New Delhi IGNOU, New Delhi Prof. G. Pradhan Dr. Surajit Das Prof. Kastuva Barik Rtd. Professor of Economics Associate Professor, JNU Professor of Economics IGNOU, Maidan Garhi, New Delhi New Delhi IGNOU, New Delhi Dr. S.P. Sharma Dr. Manjula Singh Prof. B.S. Prakash Associate Professor, Economics Associate Professor Professor of Economics Shyam Lal Coolege, DU University of Delhi, Delhi IGNOU, New Delhi Prof. Atul Sharma Shri B.S. Bagla Shri Saugato Sen Institute of Human Development Associate Professor of Economics Associate Professor of Economics PGDAV College, Delhi University IGNOU, New Delhi COURSE PREPARATION TEAM Block /Units Unit Writer Block 1 Preliminaries Unit 1 Sets and Set Operations Shri Anup Chatterjee, Associate Professor (Retd) ASRD College Unit 2 Relations and Functions Shri Anup Chatterjee, Associate Professor (Retd) ASRD College Unit 3 Logic Shri Saugato Sen, Associate Professor of Economics, IGNOU, New Delhi Block 2 Functions of One Independent Variable Unit 4 Elementary Types of Functions Shri Saugato Sen, Associate Professor of Economics, IGNOU, New Delhi Unit 5 Analytical Geometry Shri Saugato Sen, Associate Professor of Economics, IGNOU, New Delhi Unit 6 Sequences and Series Shri Saugato Sen, Associate Professor of Economics, IGNOU, New Delhi Block 3 Differentiation Unit 7 Limits Shri Anup Chatterjee, Associate Professor (Retd) ASRD College Unit 8 Continuity Shri Anup Chatterjee, Associate Professor (Retd) ASRD College Unit 9 First Order Derivatives Shri Saugato Sen, Associate Professor of Economics, IGNOU, New Delhi Unit 10 Higher Order Derivatives Shri Saugato Sen, Associate Professor of Economics, IGNOU, New Delhi Block 4 Single-Variable Optimization Unit 11 Concave and Convex Functions Unit 12 Optimization Method Shri Saugato Sen, Associate Professor of Economics, IGNOU, New Delhi Block 5 Integration Unit 13 Indefinite Integrals Shri Saugato Sen, Associate Professor of Economics, IGNOU, New Delhi Unit 14 Definite Integrals Shri Saugato Sen, Associate Professor of Economics, IGNOU, New Delhi Block 6 Difference Equations Unit 15 Linear Difference Equations Shri Jagmohan Rai, Associate Professor, PGDAV College Unit 16 Non-Linear Difference Equations Shri Saugato Sen & Chetali Arora COURSE COORDINATOR: Shri Saugato Sen GENERAL EDITOR: Shri Saugato Sen and Ms. Chetali Arora Print Production Mr. Manjit Singh Section Officer (Pub.), SOSS, IGNOU, New Delhi April, 2019 © Indira Gandhi National Open University, 2019 ISBN: All rights reserved. No part of this work may be reproduced in any form, by mimeography or any other means, without permission in writing from the Indira Gandhi National Open University. Further information on the Indira Gandhi National Open University courses may be obtained from the University’s Office at Maidan Garhi, New Delhi-110 068 or visit our website: http://www.ignou.ac.in Printed and published on behalf of the Indira Gandhi National Open University, New Delhi, by Director, School of Social Sciences. Laser Typeset by : Tessa Media & Computers, C-206, A.F.E.-II, Okhla, New Delhi Printed at :  Course Contents Page No. BLOCK 1 PRELIMINARIES 7 Unit 1 Sets and Set Operations 9 Unit 2 Relations and Functions 23 Unit 3 Logic 37 BLOCK 2 FUNCTIONS OF ONE INDEPENDENT VARIABLE 53 Unit 4 Elementary Types of Functions 55 Unit 5 Analytical Geometry 73 Unit 6 Sequences and Series 91 BLOCK 3 DIFFERENTIATION 115 Unit 7 Limits 117 Unit 8 Continuity 139 Unit 9 First Order Derivatives 155 Unit 10 Higher Order Derivatives 177 BLOCK 4 SINGLE-VARIABLE OPTIMIZATION 193 Unit 11 Concave and Convex Functions 195 Unit 12 Optimization Method 211 BLOCK 5 INTEGRATION 227 Unit 13 Indefinite Integrals 229 Unit 14 Definite Integrals 255 BLOCK 6 DIFFERENCE EQUATIONS 273 Unit 15 Linear Difference Equations 275 Unit 16 Non-Linear Difference Equations 296 GLOSSARY 313 SUGGESTED READINGS 319. 4 COURSE INTRODUCTION Welcome to this course on ‘Elementary Mathematical Methods in Economics’. Economics has consistently utilised mathematics for explanation, exploration and exposition. Mathematics has provided concepts, techniques and methods that have allowed students and practitioners of economics to think about, and understand, economic ideas. The main reasons for this are that economic concepts are in many cases quantifiable, and that mathematics helps us to understand interrelationships among economic variables. Mathematics is a language, and as students of economics you should acquire proficiency in expressing economic ideas in this language. The objective of the present course is precisely this: to familiarise you with concepts from mathematics that are the building blocks of the framework of economic analysis. The course aims to not only give you the concepts but also their applications in several areas of economics. So while studying the course you will constantly be presented mathematical concepts, and also, you will learn to think of economic concepts and immediately have an idea as to which mathematical concept is to be drawn upon to understand the economic concept at hand. The Course has six blocks. The first block, Block 1, titled Preliminaries, sets the ball rolling by discussing some simple but essential concepts like sets and set operations, as well as relations and functions. The block also has a solid discussion of key concepts and techniques of symbolic logic. This Block introduces concepts from set theory, and explains how sets with their elements, along with operations on sets may be thought of something like letters, words and punctuations of a language. The block also deals with product of sets, and how subsets of product of sets may be considered as relations, and how certain relations meeting certain requirement, may be considered as functions. The concepts discussed in this block make up the basic foundations upon which concepts and ideas presented in subsequent blocks are built. The grounding in logic provided in this block will enable you, in your subsequent study to acquire skills in understanding mathematical definitions, arguments, proofs etc. You will know how to combine mathematical statements and how to proceed from one step to the next in mathematical argument. Block 2, titled Functions of One Independent Variable, discusses specific types of functions, both algebraic as well as non-algebraic. You will be familiarized with the idea of a polynomial, as well as with linear, quadratic and cubic functions. Non-algebraic functions like logarithmic and exponential, as also hyperbolic and trigonometric functions are discussed, too. The block also discusses analytical geometry, also known as coordinate geometry, that combines basic geometrical figures like straight lines, circles, parabolas and hyperbolas and tries to express these as equations. You also learn to take an equation, and see what kind of geometrical figure would depict that equation in a diagram. Doubtless, this is very useful thing to know when studying economics and knowing how to express economic relationship among variables both as equations as well as corresponding diagrams. The second Block also discusses sequences, which are a particular kind of function. Series are also discussed, where a series is the sum of various terms of a sequence. Needless to say, economic applications of sequences and series are discussed. 5  In Block 3, the topic is Differentiation, which is one of the central mathematical tool in economics, and helps us to understand how, in a situation where one variable (dependent variable) depends on another variable (independent variable), we can determine how much the dependent variable changes when the independent variable is increased incrementally, by an infinitesimally small amount (‘infinitesimally small’ suitably defined). For this the Block has a discussion on the concept of limits where a sequence or a function approaches a certain ‘limiting value’ without actually reaching that value. Limits are a first step, an essential technique, to obtain the ‘derivative’ of a function by ‘differentiating’ it. Now for a function to be differentiable it must be ‘continuous’ in the sense that you could draw the diagram of the function over the relevant range without lifting your pencil. Of course, a much more rigorous discussion of continuity is discussed in Block 3. Continuous as well as discontinuous functions are discussed, with applications. The Block discusses first-order, as well as higher-order derivatives. How the limiting value of the slope of a tangent line is interpreted as a derivative. The Block discusses rules of differentiability and convexity. Discussion of each topic is accompanied by economic applications. Blocks 4, titled Single Variable Optimisation, explains what optimization means. Optimisation is one of the central organizing principle for discussing economic decision-making, by consumers or producers, or any economic agent for that matter. Every economic decision involves optimization of some objective function by the economic agent. The block discusses optimization of a function where the dependent variable is a function of a single independent variable. The Block also discusses in depth the nature of concave and convex functions—their characteristics and geometric properties, as well as several applications. The fifth Block, Block 5, titled Integration, discusses a branch of calculus called integral calculus. Integrating a function can be seen as the reverse of differentiating it, and the solution which results from integrating a function is called an integral. The integral is also called the anti-derivative. This integration leads to is what is called an indefinite integral. The unit also discusses definite integral. This can be seen as the difference between the values of the integral computed at given upper and lower limits of the independent variable. Integration finds widespread applications in economics. Several applications are discussed in the block. The final block of this course, Block 6, titled Difference Equations introduces you to mathematical concepts that, when applied to economics, allow you to understand economic processes that are dynamic, that is, processes that take place over time. Difference equations deal with situation where time is measured in discrete units. Both linear and non-linear difference equations are discussed along with some applications in economics. 6  BLOCK 1 PRELIMINARIES 7  BLOCK 1 INTRODUCTION The first Block in the course, titled Preliminaries contains three units that deal with such topics as to make it easier for you to follow subsequent units and blocks in this course. The concepts that you will learn in the three units of this Block will enable you to understand the concepts that follow. These initial concepts lay the foundation for the whole course. The first unit, Sets and Set Operations, begins by carefully defining a set and states the various ways of depicting a set. You learn about subsets, supersets and power sets, as well as various operations on sets like union, intersection, difference, as so on. The second unit, Relations and Functions, begins by defining the product of sets. This product is called Cartesian product. Then the concept of a relation as a subset of a Cartesian product is introduced. Subsequently the unit goes on to discuss functions and mappings. You also learn about real-valued functions, correspondences and set functions. Unit 3, title simply Logic, takes you on a journey of acquiring skills in thinking deductively. You learn about statements, predicates, as well as implications and truth tables. You understand the meaning of a proof and see that there are several types of proof. 8  Sets and Set Operations UNIT 1 SETS AND SET OPERATIONS* Structure 1.0 Objectives 1.1 Introduction 1.2 The Concept of a Set 1.3 Subsets, Supersets and Power Sets 1.3.1 Subsets and Supersets 1.3.2 Power Sets 1.4 Operations on Sets 1.4.1 Union of Sets 1.4.2 Intersection of Sets 1.4.3 Difference of Sets 1.4.4 Partition of a Set 1.5 Let Us Sum Up 1.6 Answers/Hints to Check Your Progress Exercises 1.0 OBJECTIVES After going through this unit, you will be able to: define a set; explain the concept of subsets, supersets and power sets; describe set-operations like union, intersection, difference, etc; discuss how sets can be used as the foundation for further ideas in mathematical economics; and analyse ideas in economics using concepts from set theory. 1.1 INTRODUCTION Applications of some of the concepts developed in mathematics, in discussing and developing themes in economic theory have been found handy over the years. In this unit, therefore, we introduce the basic concepts that help develop the building blocks of analysing and understanding economic theory. The compact and precise way of presenting ideas can be understood well when we learn the basic mathematical language and presentation methods. The following discussion attempts to expose you to the preliminary ideas of a set, which is the basic building block of much of mathematical analysis. Once you do this unit, you will be in a position to derive a better understanding of the material in the subsequent units. The name of this course has the term mathematical methods, and you will quickly discover that the subject-matter of this unit is the foundation of all the mathematical methods that follow in this course. Set theory is the basis of the mathematical language, of trying to think in a mathematical way. You will discover that you can translate concepts that you learn in other courses in economics into this language, which may appear abstract, but nevertheless will help you to develop skills in thinking and reasoning about economic concepts. *Contributed by Shri Anup Chatterjee 9 Preliminaries The unit is organised as follows. The next section explain the concepts of sets in a general way but also gives a precise definition and ways to represent sets. This section also discusses when two sets can be considered equal and what is meant by a complement of a set. The section after that describes how sets can contain or be within other sets and what these formations are: These are used to explain concepts and ideas about smaller and larger collections of objects, since, as you will know, sets are nothing but collection of well defined objects. This section thus discusses what are called subsets, supersets and power sets. The subsequent section discusses some fundamental set operations, particularly the union of sets, intersection of sets and difference of sets. The final sub- section discusses partitions of sets, and how these partitions can be used as concepts. Throughout the unit, an attempt has been made to provide examples to facilitate understanding. 1.2 THE CONCEPT OF A SET Definition of a Set A well-defined collection or an aggregate of objects of any kind such as books, people, numbers, etc. is defined as a set. Thus, anything can be considered a set. For example, you may have a set of: even numbers {2,4,6,…}; your favourite food items {bread, rice, curd, mixed vegetable} or, jewellery {gold chain, ear-ring}. We can speak of the set of the board of directors of a company, the set of trustees of an institution, the set of employees of a firm, the set of suppliers of a manufacturer, the set of consumers of a product, the set of accounts of a firm, so on. But the objects contained in a set need not be as concrete as the ones already mentioned. They can be abstract concepts such as the set of positive integers, the set of real numbers, etc. But remember that a set is a well-defined collection of distinct objects. Suppose we want a set of tall people living near your home. Unless we define ‘tall’ and ‘near’, we will not be able to correctly specify such a set. It is customary to require that all members of a set be distinct; thus when describing a set by listing its members, all duplications should be deleted. Elements of a Set An object which belongs to, or is a member of, or is contained in a set is said to be the element or a member of the set. Thus we write "a is an element of the set of letters of the English alphabet" or "3 is not an element of the set of even numbers". While writing sets we use curly brackets ("{"and"}"), with their elements listed in between and separated by comma (,). For example, a set of even numbers could be presented as {2, 4, 6, 8, 10,...}. Note that the dots at the end of this example indicate that the set goes on infinitely. In a set you can have as many elements as you would like. For instance, put the letters of the English alphabet {a, b, c, d, e,…} in a set, so that you have 26 elements or, keep vowels {a, e, i, o, u} only to form a set of 5 elements. Cardinality of a Set The number of elements in a set may be finite or infinite. Sets such as the set of employees of a firm, the set of suppliers of a manufacturer, and other examples from the business world are finite, because we can enumerate the 10 elements of each set in some order, by counting its elements one by one until a Sets and Set Operations last element is reached. On the other hand, the set of positive integers {1, 2, 3,….,} is infinite because the process of counting can never end. Practical business problems may involve infinite sets.The number of elements of a set is called its cardinality. If A is a set and has n members, then n is the cardinality of set A. The cardinality of a set A is sometimes denoted |A|. Thus if A is the set of letters of the English alphabet, then |A| =26. If X is the set of vowels of the English alphabet, then its cardinality is 5, i.e., |X| =5. Notations 1) Sets are usually denoted by capital letters i.e., A, B, C,...etc. 2) The elements of set are usually denoted by small letters a, b, c,... Therefore, if X is a set and x is an element of X, we write x ∈ X , i.e., x belongs to X. 3) If X is a set and y is not an element of X, we write y ∉ X , i.e., y does not belong to X. We shall follow the general practice of denoting sets with capital letters. Lowercase letters will be used to denote elements of a set. For example, let x be Mr. Sumant and J the set of directors on the board of Mega International Ltd. Then x∈J indicates that Mr. Sumant is a member of the board of directors of Mega International Ltd. and x∉ J indicates that he is not. Specifying a Set We mentioned above briefly how a set is defined in terms of its members and its cardinality. To repeat, sets can be described by listing its members within curly brackets or braces { } with a comma separating the members. This method of specifying a set is called the Roster or Tabular method. The roster method consists of enclosing in braces a list of the elements in the set.Here we merely list the elements of a set. However, the order in which the elements are listed does not matter. For instance, in the set of vowels, it does not matter whether within the curly brackets we write a, e, i, o, u or u, a, o, e, i. Example: Let a, b, c, d, e and f be the elements of a set P representing the different products manufactured by a company R. By the roster method this set may be denoted by P = {a, b, c, d, e, f } However, this method of specifying a set may not always be easy, particularly if the number of elements in a set is large (or infinite! It is difficult to specify the set of natural numbers in this manner). So another method is usually used and you will come across this way of specifying sets in Economics. This method is called the Set-builder or Defining-property method. The set-builder method consists of stating in braces the rule or condition on the basis of which it can be determined whether or not a given object is an element of the set. This consists of denoting a generic element of the set, then putting a colon (:) or a vertical bar “|” and after the colon or vertical bar, writing the basic property or characteristic of the generic element of the set. The colon or vertical bar stands for “such that” or “for which.” Example: Consider the previously specified set P of products manufactured by a company R. As per the set-builder method, set P may be specified as follows: 11 Preliminaries P = {x|x is a product manufactured by the company R} It is read as “P is the set of those elements x such that x is a product manufactured by the company R.” The symbol x denotes any one element of set P. Example: {x | x is a letter in the word stock} is read “the set of all x such that x is a letter in the word stock.” This set can also be described by listing its elements as {s, t, o, c, k}. Examples of Sets 1) N = {1, 2, 3,….} , the set of all natural numbers; 2) Z = {0, − 1, + 1, − 2, + 2,...} , the set of all integers; 3) Q = {p/q :p, q∈ Z} , the set of all rational numbers; Q+ = {r ∈ Q : r > 0} , the set of all positive rational numbers; 4) R = {x :x is a real number}, the set of all real numbers; + R = { x ∈ R : x > 0} , the set of all positive real numbers; 5) C = {x :x is a + ib, a, b∈ },the set of all complex numbers. There are some sets which are used repeatedly in Mathematics and symbols N, Z, Q, Q+, R, R+ and C are standard symbols. We will make use of them in further discussion. Empty Set A set with no element in it is called an empty set or the null set or the void set, and is denoted by the symbol ɸ. Example, A = {x: x ∈ N and 2 2) in a similar way. 2) For A × A we often write A2 , and similarly, An stands for A × A ×... × A. n 2.3 RELATIONS Any subset of a Cartesian product of sets is called a relation. That is, a relation is a set of ordered pairs. If X and Y are two non-empty sets and there is a set ρ such that ρ ⊆X×Y, we say that ρ is a relation from X to Y (we can also say that ρ is a relation between the elements of X and Y). If ρ ⊆X×X, we say that ρ is a relation in X. ExampleLet X = {1,3,5} and Y = {2, 4, 6} , and S be the Cartesian product of set X and set Y. Then, S = {(1, 2 ) ; (1, 4 ) ; (1, 6 ) ; ( 3, 2 ) ; ( 3, 4 ) ; ( 3, 6 ) ; ( 5, 2 ) ; ( 5, 4 ) ; ( 5, 6 )}. 25 Preliminaries Our objective is to get the relation ( ρ ) from S. For this, by imposing one of the following restrictions, we pick up a subset of S. i) ( x + y ) is an exact multiple of 3 ii) ( x + y) ≤ 7 iii) x > y For these three cases we define the relations as i) (1, 2) ; ( 3, 6) ; ( 5, 4) ii) (1, 2) ; (1, 4) ; (1,6) ; (3, 2); (3, 4); (5, 2) iii) ( 3, 2) ; ( 5, 2) ; ( 5, 4) Examples of some Relations 1) The relation of equality in a nonempty set X. ρ1 = {( x, x ) : x ∈ X }. Thus (x, y) ∈ 1⊆X×X if and only if x = y. 2) The relation of divisibility in N. 2 = {(m, n) ∈N×N :∃k∈ Nn = k. m} Thus, (m, n) ∈ 2⊆ N×N iff m | n , that is n can be divided by m without remainder (n is divisible by m). Note:∃ symbol stands for “there exists (at least one)” 3) The relation of ‘is less than’ in R. = {(x, y) ∈R×R : y , we found that there were 3 ordered pairs, viz., {( 3, 2 ) ; ( 5, 2 ) ; ( 5, 4 )} to satisfy the specified relation. See that a single value of x , i.e. x = 5 , has been associated with 2 values of y , viz., 2 and 4. Observe from the above examples that when the value of x is given, it may not always be possible to determine a unique y from a relation. However, if a relation exists such that for each value of x there exists a unique corresponding value of y , then y is said to be a function of x , denoted as y = f ( x ). A function is also referred to as a transformation. It is usually denoted by f :X →Y (reads as f is a function from X to Y). Symbolically, let X and Y be two nonempty sets, then, a relation f⊆X×Y is called a function from X to Y if (i) D ( f ) = X (ii) ∀x ∈ X the set { y ∈Y : ( x, y ) ∈ f } has exactly one element, i.e., ∀x ∈ X there exists exactly one element y ∈ Y such that ( x, y ) ∈ f. Note: The notations y = f ( x ) implies "y is a function of x", and X →Y mean that ( x, y ) ∈ f. f ( x ) is the element associated with x. It is also known as the image of x under f or the value of f at x. When we write a function as y = f ( x ) , x is referred to as the argument of the function, and y is called the value of the function. In Economics, we often use x as the independent variable while y as dependent variable. 2.4.1 Domain, Range, Target and Codomain of a Function Let X and Y be two nonempty sets and y = f ( x ) be a function. According to the definitions for relations, D (f) is the domain of the function f and R (f) = {f(x) :x∈D (f)} is the range of the function f. If X⊆ W, we can also write f :W⊃ →Y, which means that D (f) ⊆ W. Y is then called the target of the function f. The codomain of a function f : X → Y is the set Y. Since the range of f is the set f ( X ) defined as { f ( x ) : x ∈ X } , it follows that the range of f is always a subset of the codomain of f. 29 Preliminaries Restrictions of Functions Let X , Y , A be nonempty sets such that, A⊆ X,and f : X → Y be a function. The function g : A → Y , g ( x ) = f ( x ) is called the restriction of f to A, and we use the notation f|A = g. 2.4.2 Injective, Surjective, Bijective Functions Let X , Y be two nonempty sets and f : X → Y be a function. 1) Injective function: f is injective if ∀for all x, z ∈ X , f ( x ) = f ( z ) implies x = z , i.e., x ≠ z implies f ( x ) ≠ f ( z ). We also say that f is an injection, or a one-to-one correspondence. Thus, a function is one-to-one, if image of each distinct element in its domain under f are distinct. 2) Surjective function: f is surjective if ∀y ∈ Y , there exists x ∈ X such that f ( x ) = y, that is R ( f ) = Y. We also say that f is a surjection, or f is a map onto Y. Thus, a function is surjective (onto) if every element in Y under f is the image of some element in X. Equivalently, the range of the function is equal to its codomain. 3) Bijective function: f is bijective if it is both injective and surjective. We also say that f is a bijection or one-to-one and onto. Thus, a function is bijective if for every y in Y there is exactly one x in X such that f ( x ) = y. Equality of Functions Let f and g be two functions. f and g are said to be equal (i.e.f = g), iff (i) D (f) = D (g) and (ii) ∀x∈ X, f(x) = g(x). Inverse Function Consider a bijective function f : X → Y , so that R(f) = Y. The relation f −1⊆ R(f) ×X is a function that we call the inverse function of f. That is the inverse function of f is the function f −1 defined by f −1:R(f)→X, f −1(y) = x, where x is the unique element of X such that f ( x ) = y. Composition of Functions Let f :X →Y and g : Y →Z be functions. We define the composition of f and g, denoted by g o f, as a function g o f :X →Z, given as g o f (x) = g (f (x)), ∀x ∈X. Moreover, we can also have formulations with f ( x ) = ( x1 , x2...) i.e., more than 30 one independent variables related to the dependent variable. 2.4.3 Image and Inverse Image of Sets under Functions Relations and Functions Let f : X → Y be a function and A, B be any sets. 1) Image of set A under f : We define the set f ( A) := { f ( x ) : x ∈ A} and call f ( A) the image of set A under the function f. Note that f ( A) = f ( A ∩ X ) ⊂ f ( X ) = R ( f ) ⊂ Y. 2) Inverse image of set B under f : We define the set f −1 ( B ) := { x ∈ X : f ( x ) ∈ B} and call f −1 ( B ) the inverse image of set B under the function f. Note that f −1 ( B ) = f −1 ( B ∩ Y ) ⊂ f −1 (Y ) = f −1 ( R ( f ) ) = X. It is important to see that the set f −1 ( B ) can be defined for any set B, even if f is not injective (thus, the inverse function of f does not exist). The notation f −1 in " f −1 ( B ) " does not mean the inverse function of f. However, we can −1 easily prove that if f is injective, then for any set B, f (B) is the image of B under the inverse function of f. Check Your Progress 2 1) What is the definition of a function? …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. 2) Give an example of Surjective function. …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. 31 Preliminaries 3) Define an Inverse function. …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. 2.5 REAL SPACE AND POINT-SETS We have seen what are sets, relations and functions. Think of the number-line, with zero in the middle and the line extending on either side to infinity. This line depicts the set of real numbers, denoted by R. Now think of an interval [a, b] which contains all real numbers between a andb, including a and b. This interval can be thought to be a subset of R. So now you understand the concept of a set of real numbers. Measurements in Economics are usually done using subsets of real numbers, so you must realize this set of real numbers is very important. We can think of these sets as set of points, because these are depicted as points on the number line. We can call these sets as point-sets. The number line depicting the real numbers is called the real line. Let us now make some use of the concept of the Cartesian product of sets. We have this set of real numbers, R. Can we have a Cartesian product of this set with some other set? Of course, we can. What about if the other set is also R, that is R is multiplied by itself? Then we get a set R×R that can be denoted by R2. What are the elements of this set? This set consists of all ordered pairs. How do we depict this set graphically? This is usually depicted by the usual x-y axes that you are familiar with. The x-axis depicts real numbers from minus infinity to plus infinity. That is one R. But so does the y-axis. The y-axis also depicts numbers from minus infinity to plus infinity, just that these are depicted in a vertical manner. So the four quadrants that emerge consist of ordered pairs of numbers, the first number represents the number on the x-axis and the second number, the y-axis. The ordered pairs are written (x, y), that is within parentheses, separated by a comma. However, take care not to confuse an ordered pair with an open interval which is also depicted in the same way. Thus every ordered pair of real numbers is a member of R2. R2 is also a point- set. Think of a consumer who consumes only apples and oranges. Various combinations of apples and oranges are pairs of numbers. Each of this pair is a member of R2. But for this, we have to write one of the commodities first, and the other commodity later. For example, let the x-axis measure units of apples, and the y-axis measure units of oranges. Then (x, y)= (3,4) would denote a bundle consisting of three apples and four oranges. Of course, we are measuring non-negative quantities of apples and oranges. So it is the north-east quadrant from the four quadrants formed by the intersection of the x and y- 32 axes, which is of relevance here. The north-west quadrant is a collection of ordered pairs of which x is the negative number, and y the positive number; in Relations and Functions the south-west quadrant, both numbers are negative and in the south-east quadrant x is positive and y is negative. In any of the quadrants, the points are ordered pairs. Thus the set R2 is also a point-set, that is, a set of points, with each point being an ordered pair. Keep in mind therefore, that although each ordered pair is a collection of two numbers, the ordered pair itself is a single point and thus a single element in the set R2. So R2 is a set with ordered pairs as elements; each of these ordered pairs is a point, and thus R2 is a point-set (a set of points). We have talked of two special point-sets, where the points are real numbers (the set is R) and where the points are ordered pairs of real numbers (the set is R2). Can we extend the idea to sets whose elements are such that each element has more than two numbers? Certainly we can. We have already multiplied R with itself and got the set R2. Let us multiply R with R2. Then we will get R3. This is R × R × R. Each element of this set is an ordered triple (x, y, z). So suppose we have three axes x-axis, y-axis and z-axis, then one element of the set R3 will have a component of x and y and z. The entire set R3 is a three dimensional structure unlike R2, which is a plane and R, which is a line. But elements of each of these sets are points. You can conceptualise R3 by thinking that our consumer consumes bananas along with apples and oranges. So each good (fruit) is now measured along an axis, and because there are three fruits, we need three axes to depict these. Now think that there are n commodities (n> 3). Since we measure quantities of each commodity along an axis, we will need n-axes! How will we obtain n- axes? By having a Cartesian product of R with itself n times. So we have R × R × R × …× R (n times). We will get a new set Rn. What is a typical element of this set? Each element of this set is an ordered profile of n numbers. We can denote this by (x1, x2, x3… xn). This is called an-tuple. It would definitely be difficult (actually impossible) to draw a diagram depicting n-axes! But you can think of it in an abstract manner. Thus whether we consider R or R2 or R3 or Rn, all of these sets have points as elements and are called point-sets. The elements of Rn, the n-tuples are also called vectors (even ordered pairs and ordered triples are vectors). We will make great use of vectors in the second course on mathematical methods in economics, which you will study in the next semester. Vectors play a very important role in Economics, as we shall see. 2.6 CORRESPONDENCE AND SET FUNCTIONS In an earlier section of the unit you were familiarised with the concept of a function. Let us review what the ingredients of a function are: you need two sets — a domain and a range, and a rule. This rule takes an element of the domain and ‘transforms’ it or ‘sends’ it or ‘maps’ it to an element in the range. This element in the range is called its image. We can say that a function is a rule according to which each element in the domain is associated with an element in the range. 2.6.1 Correspondence Consider a set A. Let it be the domain. Now consider a set B as the codomain. This set can have several subsets. Think of a new set D which has as its members or elements various subsets of B. Let D be the range. So the range has 33 Preliminaries as its elements some subsets. A mapping from elements of A to elements of D is a correspondence. An ordinary function maps an element of the domain to a single element in the range. Therefore, an ordinary function is called a single valued function. A correspondence, on the other hand, since it maps one element of the domain to an element, which is itself a subset and hence has several items, is called a multi-valued function. Let us try to explain the concept with an example. Let = {2,7,9,11,14} and = {!, ", #, $, %, &, ', ℎ, )}. Now comes the important part: consider a set D which has as its elements some subset of B. In other words, D is actually a family of sets. Let D = {{!, #, &}, {", !, $}, {), #, ℎ, ', $}}. Now think of a mapping from the elements of A to elements of D. Suppose the element 9 of set A maps into the element {b, a, d} of set D and the element 14 of set A maps into the element {a, c, f} of the set D. Now understand the concept of correspondence, and why it is called multi-valued. In this example the single element 9 maps into the single element {b, a, d}, but this single element itself has three values. Thus, a correspondence maps an element into a subset of a set. The elements of set A map into elements of set D, which are subsets of set B. 2.6.2 Set-Functions For a correspondence, we asked you to think of a set and its subsets, and we constructed a set whose elements were some (or all) of the subsets of this original set. This new set, the elements of which are the subsets of the original set, we considered as the range. Now we want you to consider a set, and think of a set whose elements are some or all of the subsets of this set. But now we want to take it as the domain. So suppose there is a set + = {12, 17, 3, 9, 8, 6}. Think of a set J with some of the subsets of H as its elements. Let J={{12, 17, 8}, {17, 9, 3}, {17, 12, 6, 9}}. Now think of a mapping from J into some set M = {a, b, c, d}. This function or mapping would be an example of what is called a set-function. Let the element {17, 12, 6, 9} map into b of the set M. This function would be single-valued no doubt because each element of the domain would map into one element of the range. But each element of the domain itself is a subset of some set (here set H) in our example. So each element of the domain of the set J is a set (remember we are considering a mapping from set J to set M, not set H to set M). This kind of mapping where elements that are themselves sets are mapped into single-valued elements in the range is called a set-function. Check Your Progress 3 1) What do you understand by a set of points? What does ‘point’ mean in this context? ……………………………………………………………………………………... ……………………………………………………………………………………... ……………………………………………………………………………………... …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. 34 …………………………………………………………………………….. 2) Explain the concept of: Relations and Functions a) Correspondence ……………………………………………………………………………………... ……………………………………………………………………………………... ……………………………………………………………………………………... ……………………………………………………………………………………... b) Set-function ……………………………………………………………………………………... ……………………………………………………………………………………... ……………………………………………………………………………………... ……………………………………………………………………………………... 2.7 LET US SUM UP Building on the set operations, we extended the discussion to the idea of relations as subsets of ordered pairs, and have prepared the background of formulating functions specific relation. The concept of function, its presentation and commonly encountered forms have been discussed. The unit began by giving a detailed explanation of a Cartesian product of sets, and how a Cartesian product of two sets has ordered pairs as its elements. The unit subsequently went on to discuss the very important concept of relations as subsets of Cartesian products. Following this, you were familiarised with functions. You are perhaps accustomed to thinking that a function depicts how a variable depends on another variable. Here we explain functions as mappings or transformations or association between elements of a set called the domain with the elements of another set called the range. You came to learn how a function is again a subset of a relation, that is, how certain conditions imposed on a relation can make it a function. So we see that a relation is a subset of a Cartesian product, and a function is a subset of a relation. The unit went on to discuss various types of mappings like injective, bijective and surjective. After this the unit discussed the set of real numbers and real space, and their importance in Economics. In doing so, the unit also explained to you the important idea of a set of points, or point-sets. Finally, the unit discussed about special mappings, where the range or the domain has as their elements, some or all subsets of some other set. These are correspondence, or multi-valued functions, which are called correspondence; and set-functions, where the domain has as its elements subsets of another set. 2.8 ANSWERS/HINTS TO CHECK YOUR PROGRESS EXERCISES Check Your Progress 1 1) Any subset of a Cartesian product of sets is called a relation. In other words, a relation is a set of ordered pairs. (Refer section 2.3 to explain further) 35 Preliminaries 2) A relation ρ is an equivalence relation if it is reflexive, symmetric and transitive. 3) Domain is the set of all first elements in a relation ρ. Whereas, range is the set of all second elements called images of a relation ρ. Check Your Progress 2 1) A relation ρ from set X to Y where every element of X has a unique image in Y is defined as a function from X to Y. 2) A function f : X → Y is surjective, or onto function if the range of f equals the codomain of f. For example, f = {(1,0),(2,0),(3,5)}, where X = {1,2,3} and Y = {0,5} is a surjective function. Similarly, other examples can be framed. 3) Refer section 2.4 to answer. Check Your Progress 3 1) See section 2.5 to answer. 2) See section 2.6 to answer. 36  Logic UNIT 3 LOGIC* Structure 3.0 Objectives 3.1 Introduction 3.2 Statements 3.2.1 Statement and Negation of a Statement 3.2.2 Truth Tables 3.2.3 Connectives Using Conjunctions (‘and’) 3.2.4 Connectives Using Disjunctions (‘or’) 3.3 Implications 3.3.1 Assumption and Conclusion 3.3.2 Necessary and Sufficient Conditions 3.3.3 Inverse and Converse 3.3.4 Contrapositive 3.4 Quantifiers 3.4.1 Universal Quantifiers 3.4.2 Existential Quantifiers 3.5 Theorems and Proofs 3.6 Varieties of Proof 3.6.1 Direct Proofs 3.6.2 Proof by Contradiction 3.6.3 Proof by Induction 3.6.4 Proof using the Contrapositive Method 3.7 Let Us Sum Up 3.8 Answers/ Hints to Check Your Progress Exercises 3.0 OBJECTIVES This is a crucial unit in the course because it makes you familiar with the language used in mathematical economics. You will learn to think in an abstract manner. After the first unit that dealt with sets and set-operations, and the second unit, which built upon set-theoretic principles to discuss the important concepts and tools of relation and functions, this unit builds deals with the language and techniques of argumentation and proofs. After going through the unit, you will be able to: define a statement and its negation; identify connectives using conjunctions and disjunctions; construct truth tables and work with them; explain the concept of implications; discuss the meaning of necessary and sufficient conditions; describe the characteristics of quantifiers; discuss the concepts of theorems and proofs; and discuss the various types of proofs. * Contributed by Shri Saugato Sen, SOSS, IGNOU 37 Preliminaries 3.1 INTRODUCTION This unit deals with what can be called the language of Mathematics. Its aim is to familiarise you with the way we make statements in mathematics, and what might be the negation of such statements. It discusses how every sentence is not a statement. The unit discusses many terms that you must have come across in your school mathematics like theorem, axiom, lemma, and so on. You will learn what makes arguments valid, and which arguments can be considered invalid. What is an assumption? You will read about the concept of an assumption, and recognise whether in an argument, the path has been validly traversed from assumption to conclusion. A word you will hear all the time is ‘proof’. What exactly do we understand by a proof? When do we know that a theorem has been proved in a valid manner? What are the different types of proof that are used? The content of this unit will also come in useful for understanding the structure of economic theory, in particular, Microeconomics and Macroeconomics. You are studying Principles of Microeconomics in this semester, and will study the Principles of Macroeconomics in the next semester. You will also continue the study of micro- and macroeconomics in the subsequent semesters. Understanding logic will help you to grasp the structure of economic theory: what are assumptions, and why they are made; how to go from assumptions to conclusions; what we understand by ‘necessary and/or sufficient conditions’; what do implications mean; what are theorems; how do we prove propositions or theorems; what are axioms; what are conditions and bi-conditionals; what do the terms ‘there exists’ and ‘for all’ mean; and so on. Having grounding in logic will help you to both understand arguments and reasoning in Economics, as well as enabling you to reason yourself. Moreover, this unit will make it easier for you to understand and appreciate subsequent units of this course. Since this course will provide tools and techniques from Mathematics that will help you to understand Economic theory, if you understand this unit well, you will be able to get a better idea of how the other tools are put to use to help explain Economic theory. You will derive greater benefits from the rest of this course, as well as other courses in your study. The unit is organised as follows. The next section begins with defining the most fundamental unit of our study, the statement. The section explains the negation of a statement. Then you are introduced to truth tables, which will help you infer the status of the negation of a statement, if the statement is true or if the statement is false. The tool of truth tables is further used to see the truth or falsehood of combinations of statement via conjunction (‘and’) and disjunction (‘inclusive or’). Thus this section discusses connectives of statements. Section 3.3 discusses implications. It discusses what assumptions mean and what we understand by conclusions? This section explains the concept of necessary and sufficient conditions. In other words, you will understand the meaning of the conditions— ‘if’, ‘only if’ and ‘if and only if’. This section also explains the meaning of inverse of a statement, the converse of a statement and contrapositive of a statement. The subsequent section deals with quantifiers. The section explains the existential quantifier ‘there exists’ and the universal quantifier ‘for all’. The next section, section 3.5 discusses the very important concept of a theorem. The section also explains the concepts of an axiom and a lemma. You will also come to learn about the concept of a proof. What exactly is a proof, and what we mean when we say that we have 38 begun from axioms and assumptions to construct a proof? Finally section 3.6 Logic discusses a variety of ways that proofs are constructed, such as direct proof, proof by contradiction, proof by induction, and proof using the contrapositive. 3.2 STATEMENTS 3.2.1 Statement and the Negation of a Statement We will begin with the basic idea of a statement. We know there are many kinds of sentences in everyday language, for instance declarative sentences, like “Two is greater than five”, imperative sentences (commands), or exclamations. Of these, only the declarative sentence is considered a statement. A statement is a sentence that is either true or false – but not both. The following two sentences show, as we mentioned, ‘every sentence is not a statement’: i) ‘Open the door!’ ii) ‘X is an odd number.’ The first is a command and is obviously not a statement.The next sentence ‘X is an odd number’ depends on X, so we cannot decide if it is true or false without further information. If X =13, then the sentence is true. But if X = 90, then sentence is false. We need to know something more about X. Because there is a condition attached to the X,we call this a conditional statement. Technically speaking a conditional statement is not a statement. The negation of statement A is the statement that is false when A is true. Negation of a statement, say, p is called ‘not p’. Negation is denoted by the symbol “ ¬ ”. Thus the negation of p is denoted by ¬ p. 3.2.2 Truth Tables Truth tables are extremely useful when learning logic. The idea is to summarise in a table all possibilities for the truth or otherwise of a statement. The truth table for ‘not’ is particularly simple: p ¬p T F F T Here, T means True and F means False. The information is read along the rows. So in the second row we see that, if statement p is True (given by T), then ¬ p(not p)is False (given by F). In the third row we can see that if p is false then¬ p(not p)is true. We can view the first column as the input and the second column as the output. If we put in F, we get out a T. An important part of the definition is that statements are either true or false – there is no in- between. This is known in technical language as the law of the excluded middle. That is, the idea of something lying between true and false is excluded from being a possibility. We can build up statements using the English words ‘and’ and ‘or’. Since they connect statements, they are called connectives. 39 Preliminaries 3.2.3 Connectives using Conjunctions (‘and’) The ‘and’ connective is easiest as it corresponds to the standard English usage. In logic, usually the symbol “ ˄ ”is used to denote ‘and’. Another word used for ‘and’ in logic, that you may sometimes come across, is ‘conjunction’. To construct a truth table for ‘and’, let us take two simple statements p and q. Since each statement can, independently, be true or be false, we have four possibilities: Both false, p false and q true, p true and q false, and finally, both true. The truth table for ‘and’ using statements p and q is the following: p q p˄q F F F F T F T F F T T T As you can see, if just one of statements p or q is false, then the statement ‘p and q’ is false. We need both to be true. Here, the first two columns are the inputs and the last column is the output. Also, note that if we had three inputs, then we have 23= 8 different possibilities for the statements being true or false. Now we can use truth tables to analyse complicated expressions. For example, when is ‘p and ¬ q’ true? We can take the component parts p, q, and ¬ q, and build them up into the statement we want. p q ¬q p ˄ ¬q F F T F F T F F T F T T T T F F Note that we have created column 3 as ¬ q (not q), by using the truth table for ‘not’. We then created the final column using the truth table for ‘and’ applied to ‘p’ and ‘¬ q’, i.e., to columns1and 3. 3.2.4 Connectives Using Disjunction (‘or’) In contrast to ‘and’, the use of ‘or’ is slightly different than how it is used in standard English usage. For example, the statement ‘Arun or Amit is going to the meeting’ will usually mean that only one of them is going to the meeting— not both. This type of ‘or’is called exclusive or. The idea is that one part being true excludes the other being true. In logic, the above statement would mean at least one is going— maybe both. This is called inclusive or. The inclusive or is also called disjunction, denoted by the symbol “ ˅ ”. The truth table for disjunction is as follows: 40  Logic p q p˅q T T T T F T F T T F F F So we see that in the case of disjunction, even if one of the statements p or q is true, then p ˅q is true. Check Your Progress 1 1) Construct truth tables for the following: a) not(pand q), ………………………………………………………………………... ………………………………………………………………………... b) not(p or q), ………………………………………………………………………... ………………………………………………………………………... c) (notp)or (not q), ………………………………………………………………………... ………………………………………………………………………... d) por (not q), ………………………………………………………………………... ………………………………………………………………………... e) (notq)or q, ………………………………………………………………………... ………………………………………………………………………... f) (notq)and q. ………………………………………………………………………... ………………………………………………………………………... 2) Negate the following: a) A is true or B is false. ………………………………………………………………………... ………………………………………………………………………... ………………………………………………………………………... b) A is false and B is true. ………………………………………………………………………... ………………………………………………………………………... ………………………………………………………………………... 41 Preliminaries c) A is true or B is true. ………………………………………………………………………... ………………………………………………………………………... d) A is true and B is true. ………………………………………………………………………... ………………………………………………………………………... 3) Construct a truth table to show that ‘not (por q)’ is equivalent to ‘(not p) and (not q)’. ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… 3.3 IMPLICATIONS In Mathematics and even in Economics, we often use statements of the type ‘statement p implies statement q’. That is, we have ‘If statement p is true, then statement q is also true.’ The basic structure of how this is so, may be hidden, but much of economic analysis involves statement of this type. This type of statement is called an implication. We say p implies q and sometimes write →. 3.3.1 Assumption and Conclusion In an implication → there are two parts: Statement p is called the hypothesis or assumption, and Statement q is called the conclusion. Thus, we are saying ‘If the hypothesis is true, then the conclusion is true.’ Sometimes statement p will be made up of a number of sentences and so we refer to them as the hypotheses, assumptions and also call them conditions. Remember that → says nothing about the truth or otherwise of p or q. Supposing that → is true, we have three possibilities: i) p is true and q is true. ii) p is false and q is false. iii) p is false and q is true. We cannot have p is true and q is false, because → means that if p is true, then q is true. Truth table for → How do you think the truth table for implication looks like? It is the following: 42  Logic p q p→q T T T T F F F T T F F T Let us try to understand the above. Consider the last two rows. If p is allowed to be false, then whatever q is, the implication will be true! If p is true and q is false, then it goes against the basic definition of implication, and hence the implication is false. The top row is self-explanatory. 3.3.2 Necessary and Sufficient Conditions The concepts of necessary and sufficient conditions are often employed in Mathematics and Economics. Let us try to understand their meaning by considering the following table: Statement p Statement q 1. A gets First Division (p1). A passes the examination (q1). 2. A gets First Division (p2). A gets 70 percent marks in aggregate (q2). 3. A gets First Division (p3). A gets atleast 60 percent marks in aggregate (q3). In the table, the first column contains a statement called p (property) and the second column contains another statement called q (condition). We are considering the relationship between p and q. There are three different cases (we are assuming that a minimum of 60 percent marks in aggregate constitutes First Division). In the first case, the statement ‘A passes the examination’ is a logical consequence of the statement ‘A gets First Division’. So we can say, statement p1 implies statement q1. Symbolically, p1→q1.Considering the third case, we find that the statement ‘A gets atleast 60 percent marks in aggregate’ is again a logical consequence of the statement ‘A gets First Division’. So in this case, statement p3 implies statement q3. In terms of symbol, p3→q3.Thus, in the first case and the third case, statement q is a logical consequence of the statement p. In such a situation we say, q is a necessary condition for p. However in the second case, the statement ‘A gets 70 percent marks in aggregate’ is not a logical consequence of the statement ‘A gets First Division’. Therefore in this case, q is not a necessary condition for p. Let us now examine the cases from the opposite side. In the second case, the statement ‘A gets First Division’ is a logical consequence of the statement ‘A gets 70 percent marks in aggregate’. Hence in this case, statement q2 implies statement p2. Symbolically, p2←q2.Similarly in the third case, the statement ‘A gets First Division’ is a logical consequence of the statement ‘A gets atleast 60 percent marks in aggregate’. So in this case, statement q3 implies statement p3. Symbolically, p3←q3.Thus we find that in the second case and the third case, statement p is a logical consequence of the statement q. In such a situation we say, q is a sufficient condition for p. But in the first case, the statement ‘A gets 43 Preliminaries First Division’ is not a logical consequence of the statement ‘A passes the examination’. Here, therefore, q is not a sufficient condition for p. In the third case, earlier we have seen that q3is a necessary condition for p3 and now we find that q3 is also a sufficient condition for p3. So combining these two statements, for the third case we can say, q3 is a necessary and sufficient condition for p3. Symbolically, p3⇔q3. Thus, from the above three cases we find, p1→ q1 q1is a necessary condition for property p1 p2← q2 q2 is a sufficient condition for property p2 p3⇔q3 q3 is a necessary and sufficient condition for property p3. 3.3.3 Inverse and Converse Let us put forward a thought: we know implications, that is, we know statements of the form p → q. What would be the negation of implication? We might be tempted to think that it would be p does not imply q. It is actually (not p) implies (not q). This makes us think what would be the situation if we take the implications dealing with (not p) or (not q) or we consider q implies p. This leads us to the concepts of inverse and converse, and also contrapositive. We shall deal with the last of these in the subsequent subsection. Let us consider inverse first. Suppose an economist says “if it does not rain, the crop production will be bad.” We implicitly assume that she means that “if it rains, the crop production will be good.” However, it does not necessarily follow. In spite of the rain, the crop production may be bad due to other reasons. Thus, when “if it rains” is p and “the crop production will be good” is q, then “if it does not rain” is (not p) and “crop production will be bad” is (not q). The inverse of if p then q is if (not p) then (not q). In symbols, the inverse of p → q is (¬ p) → (¬ q). So, using the above example we are saying that if p→ q is true, then it does not necessarily follow that ¬ p → ¬ q will be true. p → q is not equivalent to (¬ p) → ( ¬ q). In general the truth of p → q says nothing about the truth of (¬p) → (¬q). Now we come to the converse. The converse of p → q is q → p. Usually, in logic and Economics, you will find that when we are presented with an implication, we want to find out if the converse is true. If an implication and its converse are both true, then we say the statements are equivalent. That is, if p → q and q → p are both true, then we say that p and q are equivalent. 3.3.4 Contrapositive If we have p → q, then ¬ q → ¬ p is called its contrapositive. We saw earlier that p → q is not equivalent to ¬p → ¬q. However, it turns out that p → q is equivalent to ¬ q → ¬ p. So any implication is necessarily equivalent to its contrapositive. Now let us briefly summarise what we have discussed about inverse, converse and contrapositives of implications: Using statements p and q, we can combine ¬ (not) and → (implies) in four ways: i) p→q 44 ii) q→ p, the converse;  iii) ¬p →¬q, the inverse; Logic iv) ¬q →¬p, the contrapositive. The results we have are: If p → q is true, then the contrapositive is true. If p → q is true, then the inverse and converse may be true, or they may be false. If p → q and q → p, then we say that p and q are equivalent and write ⇔. 3.4 QUANTIFIERS In this section we introduce ways to talk about a group of elements in a set, either all of them, or the fact that property exists for at least one of them. In such cases, we use words like ‘all’ and ‘some’. Suppose we have a statement “x is an even number.” This is a conditional statement. We want to quantify x so that it fulfills the property in general. In other words we want to see how many x’s fulfill this property. So we say we are looking for ‘quantifiers’. 3.4.1 Universal Quantifiers The phrase ‘for all’ is the universal quantifier. It is denoted by∀ ∀. Let us consider an example using terms and concepts introduced in the previous two units, “for all x ∈ R, x2≥ 0.” This says that the square of a real number is non-negative. For all can be written as ∀. To take another example, we can make a statement, let O be the set of odd numbers. “For all x ∈O, x2+ 1 is odd” (this is of course, false, but we just constructed a statement using the universal quantifier). Now let us introduce another quantifier. 3.4.2 Existential Quantifiers The phrase ‘there exists’ is the existential quantifier. It is denoted by∃ ∃. Consider some examples: i) “There exists x ∈Z such that x2= 4.” This is true as x = 2 satisfies x2= 4. Note that x = −2 also satisfies the equation. Thus, saying there exists an x does not mean that there is only one such x. ii) ‘There exists x ∈Z such that x2 = 5.’ This statement is not true. It is, of course, possible to combine the two quantifiers. To give an example, “for all x ∈Z there exists y ∈ Z such that y > x. This can be written in symbols as “∀x ∈Z∃y ∈Z|y > x.” This just says that for each integer, we can find a larger one. Note: In the above example, Z stands for the set of integers. We can also combine the quantifiers in providing definitions. Let us give such a definition: Let S be a non-empty subset of the real numbers R. We say that S has an upper bound if there exists u∈ R such that for all s ∈ S, s ≤ u. We can write this as “S has an upper bound if∃ u ∈ R:∀s ∈ S|s ≤ u.” This, of course requires you remember the content of units 1 and 2. 45 Preliminaries Check Your Progress 2 1) Explain the concept of a quantifier. Why are they needed? What is an existential quantifier? ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… 2) Distinguish between inverse and converse of an implication. ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… 3) Discuss the relationship among necessary and sufficient conditions, and if and only if statements. What can you say about the use of implications in explaining necessary and sufficient conditions? ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… 3.5 THEOREMS AND PROOFS In this section, we move beyond statements to look at claims and propositions and assertions, the ingredients of arguments and debate. These provide you with the tools of building theory, and also understand the structure of theory in Economics. We deal with terms like proposition, theorem and lemma, words that you would come across frequently in Mathematics and also in Economics. The words theorem, proposition, lemma and corollary denote statements that are true. Theorems and Propositions The most important mathematical statements are called theorems. Any result of importance will be called a theorem. We use proposition for statements that we think are of less importance but which are of some intrinsic interest. It is very difficult to give examples of the distinction between the concepts of theorem and proposition as different authors will put the same statement in different categories. Theorems can usually be written in the form‘a collection of assumptions imply some conclusion’. That is, they are in the form, ‘If …, then …’Identifying 46 precisely what these assumptions (recall your study of implications and of necessary and sufficient conditions) and conclusions are, is our first goal in Logic dealing with a theorem. We want to know how strong the assumptions and conclusions are. The best theorems have weak assumptions and strong conclusions. Lemmas A lemma is a statement that is a step on the road to proving another statement. Lemmas are considered to be less important than propositions and again the distinction between categories is not always clear. They sometimes turn out to be more useful than the statement they are used to prove. Corollaries A corollary is a statement of interest that is deduced from a theorem or proposition. Proofs Mathematicians solve problems – proof is the guarantee that our solutions are correct. A proof is an explanation of why a statement is true. Conjectures A conjecture is a statement which we believe to be true but for which we have no proof. Axioms An axiom is a basic assumption about a mathematical situation. Axioms can be considered facts that do not need to be proved (just to get us going in a subject) or they can be used in definitions. In Euclid’s work on geometry, he assumed five axioms— for example, between any two points one can draw a line — and from these axioms deduced theorems. The point is that these axioms were the only facts used without proof. Axioms are also used in definitions. 3.6 VARIETIES OF PROOF In the previous section, you were introduced to the very crucial components of logic, namely axioms, theorems, lemma, corollaries and so on. Here we focus on how to go from axioms and assumptions to the proof. Recall that implications were of the type if p then q. Theorems also make a claim. Consider it to be p. From p, we use convincing and logical arguments using certain techniques to reach and validate q. This is the nature of a proof. This section has the objective of familiarising you with various techniques of proof. 3.6.1 Direct Proofs In general, a theorem is a statement of the form p →q. The hypothesis p will likely be a compound statement, and some of its components might not even be explicitly stated. At the foundational level, our task in writing the proof of a theorem is to show that p → q is a tautology. However, the final product that is called a proof will be in sentence form, and not look anything like the manipulation of a series of symbols. In our first example, we employ the method of direct proof. The statement and proof of a theorem proved directly will always look something like the following: 47 Preliminaries Theorem: If p, then q. Proof: Suppose p. Then,.... Thus q. The ellipses (…) show the path that the arguments in the proof traverse. Writing a proof of the theorem is merely the construction of a logical bridge from the hypothesis to the conclusion. Our first method for proving theorems is the most straightforward and is called the direct method. Most statements can be broken down into smaller statements of the form ‘If p, then q.’ To prove p implies q directly you prove p implies p1, prove p1 implies p2, p2implies p3 and so on until you get pn implies q. Then you have proved p → q. Each implication should be in some sense obvious and be clear. 3.6.2 Proof by Contradiction Direct proofs and are effectively an effort to show that p →q is a tautology. Sometimes, however, it’s easier to prove p →q is a tautology by showing￢(p →q)is a contradiction. In order to construct a proof by contradiction, we first have to recall the negation of p → q. It is also helpful to remember that an if- then statement might sometimes be better stated using ￢and∨. That is to say p → q≡￢p∨q. Therefore negation of p → q will be: ￢(p →q)≡￢(￢p ∨q) = ￢(￢p) ∧￢q = p∧￢q [We have used rules of logic related to statements] Therefore for proving p → q by contradiction, we will need to show that p ∧￢q is absurd, that is, its truth value can never be true. The general form of proof by contradiction is as follows: Theorem :If p, then q. Proof:Suppose p and ￢q. Then.... This is a contradiction. Thus, p→q. The law of the excluded middle that we encountered at the beginning of the unit asserts that a statement is true or it is false, it cannot be anything in between. We can use this as another method of proof. We assume that the statement is false and proceed logically to show that this gives a statement that we definitely know is false such as— 1 = 0 or the Moon is made of cheese. Thus our assumption must be wrong, the statement can’t be false— it leads to something ridiculous— so the statement is true. Proof by contradiction is also known by the name reduction ad absurdum which when translated means reduction to the absurd. The structure of a proof by contradiction: i) First we state that we are assuming the statement is false. This is a hint to show that the proof will be by contradiction. ii) Next we write out what the statement being false means, using negation. iii) Proceed with what it implies until we find a contradiction. iv) Show that a contradiction has arisen. 48 3.6.3 Proof by Induction Logic Induction is a very powerful technique used regularly in Mathematics. It may appear misleading because it sometimes appears like we assume what is to be proved. The advantage of this method is that it is easy to recognise when to use, and also how to use and only two conditions are needed to be checked to apply it. With induction we don’t prove the statements directly. What we do is perhaps best described by analogy with cycles at a cycle stand. As you might understand, if you push the first cycle over, it knocks the second cycle over, that in turn knocks the third down, and so on. Provided the cycles happen to be kept in such a way that each knocks down the next, then all of them will fall. The process of induction is that we prove that ‘if the kth statement is true, then the (k+1)th statement is true’, i.e. the truth of one statement implies the truth of the next one. This is analogous to one cycle knocking down the next one. So, if the first statement is true (push the first cycle), then all the statements are true (all the cycles get knocked down).The power of induction is really an important tool in the toolkit of the student of logic who is keen to apply it to Economics. The Principle of Mathematical Induction The Principle of Mathematical Induction requires that we have a sequence of statements indexed by the natural numbers. Let A(n) be an infinite collection of statements with n∈ N. N here is the set of natural numbers. Suppose that, i) A(1) is true, and ii) A(k)→ A(k+ 1), for all k∈N. Then, A(n) is true for all n∈N. Checking condition (i) is called the initial step. Checking condition (ii) is called the inductive step. Assuming that A(k)is true for some k in (ii) is called the inductive hypothesis. The method for constructing a proof by induction is simple: i) We state that we are using induction; ii) Work out the initial case, for n = 1; iii) State that we are assuming that the statement is true for some k. Writing out thestatement to use it later is often helpful; iv) We utilise the truth of the statement for k in the proof of the statement for k +1. Often this requires breaking a mathematical expression into two pieces, one of which involves the case for k. We must be sure to indicate at which point we invoke the inductive hypothesis; and finally. v) We state the conclusion: “By the Principle of Mathematical Induction, the statement is true.”This helps to demonstrate that the proof is complete. 3.6.4 Proof Using the Contrapositive Method The technique of proving by using the contrapositive method uses the fact that the statement ‘p→ q’ is equivalent to ‘not q → not p’. The contrapositive of the 49 Preliminaries statement p→ q is ¬q → ¬p, as we have already seen. The contrapositive method is the use of this equivalence. It is an indirect method, wherein to prove ‘p → q’we start with ¬q(and proceed to show that not p is true). Thus, proof by contradiction involves the following: We know that p →q is logically equivalent to￢q →￢p.This suggests that a proof of a theorem of the form p → q might be approached contrapositively by showing ￢q → ￢p instead. To prove the latter is equivalent to proving the former. In general, a proof by contraposition will go something like this. Theorem: If p, then q. Proof: Suppose ￢q. Then,.... Thus ￢p. Whether it is better to attack a theorem directly or contrapositively we learn by tackling several theorems and trying to work out their proofs. Check Your Progress 3 1) Explain the concept of an axiom, a proposition and a corollary. …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. 2) What do you understand by a theorem? What constitutes a proof? …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. 3) Discuss the methods of proof by contradiction and proof by contrapositive. …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. …………………………………………………………………………….. 50 ……………………………………………………………………………..  Logic 3.7 LET US SUM UP This unit was concerned with familiarising you with the basic principles and methods of logic. As such, the unit continued from and supplemented the concepts and tools of the first two units. These three units are the foundation to help you to acquire the skill of abstract thinking. The unit also had the aim of helping you to think about Economic theory in an abstract manner. You will also be aided in learning to connect concepts and learn how to argue, keeping the validity of arguments in mind. The unit began with an explanation of a statement and the negation of a statement. It discussed truth tables and went on to describe truth tables, what they mean and how they are constructed. Following this, the unit discussed connectives of statements using conjunction and disjunction. Then the unit proceeded to discuss implications and conditionals. It discussed necessary and sufficient conditions and also biconditionals. After explaining the existential and universal quantifiers, the unit explained the concepts of axioms, theorems and proofs. Finally the unit described a variety of methods of furnishing a proof, such as the direct method, proof by contradiction, proof by induction, and proof using the contrapositive. 3.8 ANSWERS/HINTS TO CHECK YOUR PROGRESS EXERCISES Check Your Progress 1 1) a) p q p˄q Not (p ˄ q) F F F T F T F T T F F T T T T F c) p ¬p q ¬q ¬ p˅¬ q F T F T T F T T F T T F F T T T F T F F d) q ¬q ¬ q˅ q F T T T F T F T T T F T 51 Preliminaries 2) a) A is not true and B is not false. Generally, negation of "A or B" is the statement "Not A and Not B." b) A is not false or B is not true. Generally, negation of "A and B" is the statement "Not A or Not B." c) A is not true and B is not true. d) A is not true or B is not true. 3) See section 3.2.2 and answer. Check Your Progress 2 1) See section 3.4 and answer. 2) See section 3.3.3 and answer. 3) See section 3.3 and answer. Check Your Progress 3 1) See section 3.5 and answer. 2) See section 3.5 and answer. 3) See section 3.6 and answer. 52