Mathematical methods for economic theory

1.1 Logic: basics and proof by induction

Basics

When making precise arguments, we often need to make conditional statements, like or These statements are instances of the statement where A and B stand for statements. We may alternatively write this general statement as or, using a symbol, as Yet two more ways in which we may write the same statement are and (Note that B comes first in the second of these two statements!)

Important note: The statement A ⇒ B does not make any claim about whether B is true if A is NOT true! It says only that if A is true, then B is true. While this point may seem obvious, it is sometimes a source of error, partly because in everyday communication we do not always adhere to the rules of logic. For example, when we say “if it's fine tomorrow then let's play tennis” we probably mean both “if it's fine tomorrow then let's play tennis” and “if it's not fine tomorrow then let's not play tennis” (and maybe also “if it's not clear whether the weather is good enough to play tennis tomorrow then I'll call you”). When we say “if you listen to the radio at 8 o'clock then you'll know the weather forecast”, on the other hand, we do not mean also “if you don't listen to the radio at 8 o'clock then you won't know the weather forecast”, because you might listen to the radio at 9 o'clock or check on the web, for example. The point is that the rules we use to attach meaning to statements in everyday language are subtle, while the rules we use in logical arguments are absolutely clear: when we make the logical statement “if A then B”, that's exactly what we mean—no more, no less.

We may also use the symbol “⇐” to mean “is implied by”. Thus

is equivalent to Both statements mean “if A then B”, or equivalently, “B is true if A is true” or “A is true only if B is true”.

Finally, the symbol “⇔” means “implies and is implied by”, or “if and only if”. Thus

is equivalent to

If A is a statement, we write the claim that A is not true as

Note that

If A and B are statements, and both are true, we write

and if at least one of them is true we write Note, in particular, that writing “A or B” includes the possibility that both statements are true.

Two rules

Rule 1

If the statement

A ⇒ B

is true, then so is the statement

(not B) ⇒ (not A).

The first statement says that whenever A is true, B is true. Thus if B is false, then A is false—hence the second statement.

Rule 2

The statement

not(A and B)

is equivalent to the statement

(not A) or (not B).

Note the “or” in the second statement. If it is not the case that both A is true and B is true (the first statement), then either A is not true or B is not true.

Quantifiers

We sometimes wish to make a statement that is true for all values of a variable. For example, denoting the total demand for tomatoes at the price p by D(p), it might be true that In this statement, “for every price” is a quantifier.

Important note: We may use any symbol for the price in this statement: “p” is a dummy variable. After having defined D(p) to be the total demand for tomatoes at the price p, for example, we could write

Given that we just used the notation p for a price, switching to z in this statement is a little odd, BUT there is absolutely nothing wrong with doing so! In this simple example, there is no reason to switch notation, but in some more complicated cases a switch is unavoidable (because of a clash with other notation) or convenient. The point is that every statement of the form where x is any symbol, has exactly the same content.

Another type of statement we sometimes need to make is

or, equivalently, “For some x” (alternatively “there exists x”) is another quantifier, like “for every x”; my comments about notation apply to it.

Proof by induction

Suppose that you want to prove that some statement S(k) is true for every positive integer k. One way of doing so is to prove the statement S(1) is true and then prove that if, for any positive integer n, S(k) is true for all k = 1, ..., n, then S(n+1) is true. This line of argument is known as proof by induction.

Here is an example. You want to prove that, for any positive integer k,

For k = 1, the statement is 1 = 1(1 + 1)/2, which is true. Now assume that the statement is true for all k = 1, ..., n. You need to prove that it is true for k = n + 1, which means Now, the left-hand side of this equation can be written and by the assumption that the statement is true for n, this expression is equal to Thus indeed the statement is true for n + 1.