Economic

Methods of Proof

Dr Damien S. Eldridge

Australian National University

7 February 2021

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 1 / 28

Reading Guide

Banks, J, G Elton, and J Strantzen (2009), Topology and analysis: Unit text for MAT3TA (2009 and 2010 edition), Department of Mathematics and Statistics, La Trobe University, Bundoora, February.

Corbae, D, MB Stinchcombe, and J Zeman (2009), An introduction to mathematical analysis for economic theory and econometrics, Princeton University Press, USA: Notation and Chapter 1 (pp. xix-xxi and 1-14).

Kolmogorov, AN, and SV Fomin (1970), Introductory real analysis (revised English edition), Translated and Edited by RA Silverman, Dover Publications, USA: Chapter 1 (pp. 1-36)

Mas-Colell, A, MD Whinston, and JR Green (1995), Microeconomic theory, Oxford University Press, USA.

Simon, CP, and L Blume (1994), Mathematics for economists, WW Norton and Company, USA: Appendix A1 (pp. 847-858).

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 2 / 28

Logical Reasoning in Economics

Much of modern economics is founded on the use of logical reasoning to establish the validity of some set of propositions (B) when some other set of well-defined assumptions (A) are satisfied.

Typically, a fixed set of rules that are accepted as being valid are applied in various ways to show that if the assumptions in set A are satisfied then the conclusions in set B must be true. Such an argument is known as a “proof”.

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 3 / 28

A Taxonomy of Proof Methods

There are four basic methods of proof and one basic method of disproof that are frequently employed.

These are:

Proof by Deduction; Proof by Induction; Proof by Contradiction; Proof by Contraposition; and Disproof by Counter-Example.

Note that:

Proof by deduction and proof by induction are direct methods of proof; while Proof by contradiction and proof by contraposition are indirect methods of proof.

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 4 / 28

Some Useful Notation Part 1

=⇒: “Implies” or “if, then”. A =⇒ B means “A implies B” or “if A is true, then B must also be true”.

⇐=: “Implied by” or “will be true if”. A ⇐= B means “A is implied by B” or “A will be true if B is also be true”.

⇐⇒: “Implies and is implied by” or “if and only if (which is sometimes abbreviated as iff)” or “is equivalent to”.

A ⇐⇒ B means “A both implies and is implied by B” or “if A is true iff B is also be true” or “A is equivalent to B”.

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 5 / 28

Some Useful Notation Part 2

∧: “And”. A∧B means “A and B”.

∨: “Or”. A∨B means “A or B”.

¬: “Not”. ¬A means “not A”.

∃: “There exists”. ∀: “For all”.

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 6 / 28

Proof by Deduction

Suppose that we wanted to prove that, if A is true, then so is B by deduction.

We would need to find a sequence of axioms or theorems that are already accepted as being true such that

A =⇒ P1 =⇒ P2 · · · =⇒ Pn =⇒ B

In some situations, it might be convenient to break one of the steps up into an exhaustive collection of cases and then establish its validity for each of these cases.

In effect, you would establish the validity of Pk by showing that Pk = P

1 k ∧P

2 k ∧·· ·∧P

m k and also showing that each of the individual

cases, Pik for i ∈{1, 2, · · · , m}, are true.

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 7 / 28

Proof by Deduction Example

This example comes from Simon and Blume (1994, pp. 852-853).

We want to show that if m is an even integer and p is any integer, then m×p is an even integer. The proof proceeds as follows.

We are told that m is an even integer. (Given in the claim we are attempting to prove.) This means that m = 2 ×q for some integer q. (Definition of an even integer) This means that m×p = (2 ×q)×p. (Post-multiplication of both sides of an equation by p.) This means that m×p = 2 × (q ×p). (Associativity of multiplication over the set of integers.) This means that m×p = 2 ×z where z = q ×p is an integer. (Closure of the set of integers under multiplication.) This means that m×p is an even integer. (Definition of an even integer.)

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 8 / 28

Proof by Induction Part 1

Suppose that we have a claim that can be indexed by the set of natural numbers (N = {1, 2, · · · , n, · · ·}) and we want to prove that this claim is true for all n ∈ N. Denote the nth case of this claim by An. A proof of the claim by deduction might proceed as follows:

A1 ∧A2 ∧A3 · · ·∧An ∧·· · =⇒ A.

The (countably) infinite number of cases that would need to be verified for such a proof by deduction to be implemented make it unfeasible.

Instead, a proof by induction might be appropriate in such cases.

A proof by induction makes use of the “principle of mathematical induction”, which is one of the three Peano axioms that are sometimes used to construct the set of natural numbers.

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 9 / 28

The Peano Axioms

This material is drawn from Banks et al (2009, pp. 2-13).

The following three axioms are sometimes used to formally construct the set of natural numbers. They are known as the Peano axioms because they were developed by Guiseppe Peano.

The Peano axioms are as follows.

(PA1): There is a non-empty set of natural numbers N, and a one-to-one function s : N −→ N called the successor function. (PA2): N has an element 1 that satisfies s(n) 6= 1 for all n ∈ N. (PA3) (The Principle of Mathematical Induction): If X ⊆ N has the following properties: (a) 1 ∈ X and (b) s(n) ∈ X for all n ∈ X ; then X = N.

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 10 / 28

Proof by Induction Part 2

Suppose that we have a claim that can be indexed by the set of natural numbers (N = {1, 2, · · · , n, · · ·}) and we want to prove that this claim is true for all n ∈ N. Denote the nth case of this claim by An.

A proof of this claim by induction proceeds as follows:

A1 ∧ (∀n ∈ N)(An =⇒ A(n+1)) =⇒ A.

In effect, proofs by mathematical induction proceed as follows. Step 1: Show that the claim is true when n = 1. Step 2: Assume that the claim is true for the arbitrary case of n = k (this is known as the inductive assumption) and show that, if this inductive assumption is is true, then the claim must also be true for the case of n = (k + 1). Note that it is imperative that the inductive assumption be used in the process of showing that the claim is true for n = (k + 1). Step 3: Apply the principle of mathematical induction to conclude that the claim is true for all n ∈ N.

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 11 / 28

Proof by Induction Part 3

The logic underlying a proof by induction is very intuitive. It basically establishes that the claim is true for n = 1, and that if the claim is true for n = 1, then it must also be true for n = 2, which means it must also be true for n = 3, which means it must also be true for n = 4, and so on and so forth, ad infinitum.

The validity of the method of proof by induction can be established through a proof by contradiction, as we will see shortly.

The method of proof by induction can be extended beyond the set of natural numbers to any “well-ordered set”, where “well-ordered” has a very precise mathematical meaning. This extended version of proof by induction is known as “proof by transfinite induction”. See Kolmogorov and Fomin (1970, pp. 28-29) for details.

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 12 / 28

Proof by Induction Example 1 Part 1

This example comes from Simon and Blume (1994, pp. 856-857).

We want to show that ∑nx=1 x = n(n+1)

2 for all n ∈ N.

The proof proceeds as follows.

Note that ∑1x=1 x = 1 and 1(1+1)

2 = 2 2 = 1. Thus the claim is true for

n = 1. Assume that the claim is true for n = k. In other words, assume that

∑kx=1 x = k(k+1)

2 .

The proof is continued on the next slide.

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 13 / 28

Proof by Induction Example 1 Part 2

This proof is continuing from the previous slide.

Consider the case of n = (k + 1).

Note that ∑k+1x=1 x = (∑ k x=1 x) + (k + 1) =

k(k+1) 2 + (k + 1) by our

inductive assumption.

Note that k(k+1)

2 + (k + 1) = k(k+1)

2 + 2(k+1)

2 = (k+2)(k+1)

2 .

Note that (k+2)(k+1)

2 = ((k+1)+1)(k+1)

2 = (k+1)((k+1)+1)

2 . Thus we have shown that, if the claim is true for n = k, then it must also be true for n = (k + 1). Since (a) the claim is true for n = 1, and (b) if the claim is true for n = k, then it is also true for n = (k + 1), we can conclude by the principle of mathematical induction that the claim is true for all n ∈ N.

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 14 / 28

Proof by Induction Example 2 Part 1

This example comes from Exercise A.1.7 in Simon and Blume (1994, p. 858).

We want to show that n < 2n for all n ∈ N. The proof proceeds as follows.

Note that 1 < 21 = 2, so the claim is true when n = 1. Assume that the claim is true when n = k. This means that k < 2k . Consider the case of n = (k + 1). If we add 1 to both sides of the inequality in our inductive assumption, we obtain k + 1 < 2k + 1. Since k > 1, we know that 1 < 2 = 21 6 2k . This means that 1 6 2k .

The proof is continued on the next slide.

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 15 / 28

Proof by Induction Example 2 Part 2

This proof is continued from the previous page.

This means that 2k + 1 < 2k + 2k . Note that 2k + 2k = 2(2k) = 2k+1. This means that 2k + 1 < 2k+1. Since k + 1 < 2k + 1 and 2k + 1 < 2k+1, we know that (k + 1) < 2k+1. Thus, if the proposition is true when n = k, then it must also be true when n = (k + 1). Since (a) the claim is true for n = 1, and (b) if the claim is true for n = k, then it is also true for n = (k + 1), we can conclude by the principle of mathematical induction that the claim is true for all n ∈ N.

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 16 / 28

Proof by Contradiction

Suppose that we wanted to prove that “if A is true, then so is B” by contradiction.

This would involve us first identifying all of the potential alternatives to B and then showing that each of these cannot be true because they would contradict either A or something else that we know to be true.

In other words, a proof by contradiction of the claim that A =⇒ B takes the form

A∧¬B =⇒ C ∧¬C .

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 17 / 28

Proof by Contradiction Example 1 Part 1

This example is drawn from Kolmogorov and Fomin (1970, p. 28).

We want to show that the method of proof by induction is valid for propositions that can be indexed by the set of natural numbers.

In other words, we want to show that if (a) P(n) is a proposition that is formulated for all n ∈ N, (b) P(1) is true, and (c) the validity of P(k) for all k 6 n implies the validity of P(k + 1), then P(n) is true for all n ∈ N. This is a proposition of the form A =⇒ B, where A consists of statements (a), (b), and (c), and B consists of the concluding statement.

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 18 / 28

Proof by Contradiction Example 1 Part 2

The proof proceeds as follows.

Suppose that P(n) is not true for all n ∈ N. Let n̂ be the smallest natural number for which P(n) is not true. Since we are told that P(1) is true, we know that n̂ > 1. This means that (n̂− 1) ∈ N. Thus we know that P(n) is true for all k ∈{m ∈ N : m 6 n̂− 1} 6= ∅. Since we are told that if P(k) is true for all k 6 n, then P(n) is also true, this means that P(n̂) must be true. Contradiction. This means that our initial assertion in this proof must have been false. Thus we can conclude that the method of proof by induction is indeed valid for propositions that can be indexed by the set of natural numbers.

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 19 / 28

Proof by Contradiction Example 2 Part 1

This example is drawn from Simon and Blume (1994, p. 854-855).

We want to show that √

2 /∈ Q. In other words, we want to show that

√ 2 is not a rational number.

We will employ a proof by contradiction. As part of this proof, we will make use of the following two propositions which are true but we will not prove.

If a ∈ Z and a2 is even, then a is even as well. Suppose that a = pq is a rational number with p ∈ Z and q ∈ N. It is possible to choose p and q such that at most one of them is even.

The proof proceeds as follows.

Suppose that √

2 ∈ Q. Then

√ 2 = pq for some p ∈ Z and q ∈ N. (Definition of a rational

number.) Furthermore, either p is odd, or q is odd, or both are odd. (Assumed but unproven proposition 2.)

This proof is continued on the following slide.

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 20 / 28

Proof by Contradiction Example 2 Part 2

This proof is continued from the previous slide.

This means that √

2 × √

2 = pq × √

2. (Post-multiplication of both

sides of the equation by √

2.) This means that

√ 2 × √

2 = pq × p q . (Since

√ 2 = pq .)

This means that 2 = p 2

q2 . (Straightforward algebra.)

This means that 2 ×q2 = p2. (Straightforward algebra.) This means that p2 is even. (Definition of even.) This means that p is even. (Assumed but unproven proposition 1.) Thus p = 2 ×m for some m ∈ Z. (Definition of even.) This means that p ×p = (2m)×p. (Post-multiplication of both sides of the equation by p.) This means that p ×p = (2m)× (2m). (Since p = 2m.)

This proof is continued on the next slide.

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 21 / 28

Proof by Contradiction Example 2 Part 3

This proof is continued from the previous slide.

This means that p2 = (2m)× (2m). (Straightforward algebra.) This means that p2 = 2 × (2 × (m×m)). (Repeated application of the associative and commutative laws of multiplication.) This means that p2 = 2 × (2m2). (Straightforward algebra.) This means that 2 ×q2 = 2 × (2m2). (Since p2 = 2 ×q2.) Thus q2 = 2 ×m2. (Pre-multiplication of both sides of the equation by 12 , which is the multiplicative inverse for 2.)

This means that q2 is even. (Definition of even.) This means that q is even. (Assumed but unproven proposition 1.) But this means that if our initial assumption is true, then both p and q are even, which contradicts our assumed but unproven proposition 2. Thus our initial assumption must be false. This means that

√ 2 /∈ Q.

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 22 / 28

Proof by Contraposition

Suppose that we wanted to prove that, if A is true, then so is B.

Note that A =⇒ B means that, if A is true, then B must also be true.

This in turn means that if B is not true, then A cannot be true.

Note also that ¬B =⇒¬A means that, if B is not true, then neither is A.

This in turn means that if A is true, then B must also be true.

In other words, (A =⇒ B) ⇐⇒ (¬B =⇒¬A). The statement (¬B =⇒¬A) is the contra-positive version of the statement (A =⇒ B). Sometimes, it might be easier to prove that (A =⇒ B) by showing that (¬B =⇒¬A) than it is to prove it directly.

This indirect method of proof is known as a proof by contraposition.

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 23 / 28

Proof by Contraposition Example

Suppose that we want to show that if m×p is an odd integer whenever p is any type of integer, then m is not an even integer.

The contrapositive version of this claim is that if m is an even integer, then m×p must be an even integer whenever p is any type of integer. We have already proven this contrapositive version of the statement using a proof by deduction.

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 24 / 28

Disproof by Counter-Example

Suppose that we want to show that the claim that A =⇒ B is false. All we need to do is find a single example in which A is satisfied but B is violated.

Such an example is known as a counter-example.

Example: Suppose that we want to show that the following claim is false:

n

∑ x=1

x = n(n + 1) for all n ∈ N.

Consider the case where n = 3. We have ∑4x=1 x = 1 + 2 + 3 + 4 = 10. We also have 4(4 + 1) = 4 × 5 = 20. Note that 10 6= 20. Thus the claim is false.

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 25 / 28

An Example of a Proof in Economics Part 1

This example is drawn from Mas-Colell, Whinston and Green (1995, p. 9).

We want to prove that if a weak preference ordering can be represented by a utility function, then it must be rational.

Some preliminary definitions. Suppose that % is a weak preference relation defined on X ×X .

% is rational if it is both strongly complete and transitive. % is strongly complete if it is both weakly complete and reflexive. % is weakly complete if (∀(x, y) ∈ X ×X such that x 6= y) =⇒ (Either x % y or y % x or both). % is reflexive if (∀(x, x) ∈ X ×X such that x 6= y) =⇒ (x % y). % is strongly complete if (∀(x, y) ∈ X ×X) =⇒ (Either x % y or y % x or both). The function U : X −→ R is a utility function that represents the weak preference relation % if, for all (x, y) ∈ X ×X , we have

x % y ⇐⇒ U(x) > U(y).

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 26 / 28

An Example of a Proof in Economics Part 2

The proof proceeds as follows.

Suppose that U : X −→ R is a utility function that represents the weak preference relation %. We need to show that this implies that the weak preference ordering is both strongly complete and transitive. Strongly complete.

Note that U(x) ∈ R for all x ∈ X . Note also that > is strongly complete over R. This means that if (x, y) ∈ X ×X , then either U(x) > U(y) or U(y) > U(x) or both. Since U : X −→ R is a utility function that represents the weak preference relation %, this means that if (x, y) ∈ X ×X , then either x % y or y % x or both. Thus % is strongly complete.

This proof continues on the next slide.

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 27 / 28

An Example of a Proof in Economics Part 3

This proof is continued from the previous slide. Transitive.

Note that U(x) ∈ R for all x ∈ X . Note also that > is transitive over R. Suppose that (x, y, z) ∈ X ×X ×X such that x % y and y % z. Since U : X −→ R is a utility function that represents the weak preference relation %, this means that U(x) > U(y) and U(y) > U(z). The transitivity of > over R means that U(x) > U(z) Since U : X −→ R is a utility function that represents the weak preference relation %, this means that x % z. Thus % is transitive.

Since % is both strongly complete and transitive, it must be rational.

D. S. Eldridge (ANU) Methods of Proof 7 February 2021 28 / 28