## 1.1 Logic: basics and proof by induction

### Basics

When making precise arguments, we often need to make conditional statements, like*if*the price of output increases

*then*a competitive firm increases its output

*if*the demand for a good is a decreasing function of the price of the good and the supply of the good is an increasing function of the price

*then*an increase in supply at every price decreases the equilibrium price.

*if*A

*then*B,

**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

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

*and*A ⇐ B.

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

### Two rules

- Rule 1
- If the statement
A ⇒ Bis 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

*D*(

*p*) > 100 for every price

*p*in the set

*S*.

*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

*D*(

*z*) > 100 for every price

*z*in the set

*S*.

*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

*x*) for every

*x*in the set

*Y*,

*x*is

*any*symbol, has exactly the same content.

Another type of statement we sometimes need to make is

*x*) for some

*x*in the set

*Y*,

*x*in the set

*Y*such that A(

*x*).

*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*,

*k*

*i*=1

*i*=

*k*(

*k*+ 1)/2.

*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

*n*+1

*i*=1

*i*= (

*n*+ 1)(

*n*+ 2)/2.

*n*

*i*=1

*i*+

*n*+ 1

*n*, this expression is equal to

*n*(

*n*+ 1)/2 +

*n*+ 1 = (

*n*+ 1)(

*n*+ 2)/2.

*n*+ 1.