Part 2

New Skills

Formulating Maths
Introduction
Hypotheses &c
Implications
And & or
For all & there exists
Dependence

Proof
Introduction
Counter examples
Constructing proofs
Understanding
Experimentation
Precision
Examples
Assumptions
Contradiction
Induction
The End

 

---

Site map

---

 

 

 

We saw in Part 1: Studying the theory one example of a proof by contradiction. This was rather a simple example-the statement (that Ö2 is irrational) had no hypotheses and a simple conclusion-so there was no great difficulty in setting up the argument. In more advanced situations, proof by contradiction can be a powerful method, but it is a dangerous one, as it is easy to introduce fallacies.

Recall from Hypotheses and conclusions that typically one has to prove a statement of the form:

Z1:

If P, then Q.

Here, P represents the hypotheses and Q the conclusion. In principle, there are three ways in which Z1 can be proved:

(i)

Assume that P is true, and deduce by some logical process that Q is true (a direct proof);

(ii)

Assume that Q is false, and deduce that P is false (i.e., prove the contrapositive of Z1);

(iii)

Assume that P is true and Q is false, and deduce some obviously false statement (e.g., 1 = 0) (i.e., proof by reductio ad absurdum).

The term ``proof by contradiction'' is commonly applied to proofs of type (ii) or (iii) (although some would say that it should be applied only to (iii)).

Sometimes, it is possible to prove a given statement by two of these three methods, or even by all three. For example, we will now prove the following statement by each method in turn:

Z2:

If a³ + 3a² + 3a ³ 0, then a ³ 0.

In this statement, it is assumed that a is a real number. The hypothesis is that a³ + 3a² + 3a ³ 0; the conclusion is that a ³ 0.

First proof: We assume that a³ + 3a² + 3a ³ 0. Then (a+1)³ = a³ + 3a² + 3a + 1 ³ 1. Taking cube roots, it follows that a+1 ³ 1, so a ³ 0. This completes a direct proof of Z2.

Second proof: Suppose that a < 0. Then a+1 < 1. It follows that (a+1)³ < 1, so a³ + 3a² + 3a = (a+1)³ - 1 < 0. This contradicts the hypothesis of Z2. Thus we have proved Z2 by proving its contrapositive.

Third proof: Suppose that a³ + 3a² + 3a ³ 0 and a < 0. Dividing by the negative number a gives:

a2 + 3a + 3 £ 0. (*)

But

a2 + 3a + 3 = æ ç è a+ 3 2 ö ÷ ø 2   + 3 4 ³ 3 4 .

This contradicts (*), so we have proved Z2 by reductio ad absurdum.

If you have Alice in Numberland, you will find (p.6) three proofs of the statement: If n² is odd, then n is odd.

A principle which is generally, but not universally, true is that your first approach should be to look for a proof of type (i) (a direct proof). The reason why this is a good principle is that both (ii) and (iii) require you to assume the negation of Q, i.e. to assume that Q is false. Now, Q is likely to be a fairly complicated mathematical statement, and it is not always easy to write down a mathematical formulation of the negation of Q. There is one obvious exception to this-when Q is itself a negative statement. For example, the conclusion Ö2 is irrational is a negative statement, because, by definition, it means Ö2 is not rational, and the negation of this is Ö2 is rational. Thus, in this example, and in others where the conclusion Q is a negative statement, it is natural to look for a proof by contradiction.

Even where the conclusion Q is a positive statement, you will find many instances where it just does not seem possible to give a direct proof of Z1, and you are obliged to consider the possibility of a proof by contradiction. The first problem then is to formulate the negation of Q correctly, in mathematical terms. We shall devote the remainder of this section to how to do this. The negation of Q is the statement Q is false, or Q does not hold, but the problem is to put such a statement in a form which is suitable for mathematical argument.

The first step is to formulate Q in basic mathematical terms. For example, if Q is the statement f is continuous, then the negation of Q is f is discontinuous. However, this is useless for the purpose of proving things, unless we have a mathematical definition of discontinuous. In fact, continuity is defined mathematically, and then one has to deduce the definition of discontinuity by taking the negation. The mathematical definition of f is continuous is:

Z3:

For all x, and for all e > 0, there exists d > 0 such that |f(y)-f(x)| < e whenever |y-x| < d.

At this stage, one should forget about the meaning of the statement, and proceed formally. This may seem surprising advice, but it is the most reliable way of obtaining the correct negation of a complicated mathematical statement. It is likely that the statement can be built up out of a few standard constructions such as the following:

Z4:

"x Î S, P(x);

Z5:

$x Î S such that P(x);

Z6:

P and P¢;

Z7:

P or P¢.

Here, S denotes a certain set, x is a variable, P(x) is a statement which depends on the variable x (see For all & there exists), and P and P¢ are statements. All the statements P(x), P and P¢ may be complicated, involving several quantifiers " and $ as well as ``and'' and ``or''. The next step is to write Q in a formal fashion using statements of the form Z4-Z7. For example, we can write Z3 using three constructions of the type Z4 and one of Z5:

Z8:

"x Î R "e > 0, $d > 0 such that "y Î (x-d,x+d), |f(y)-f(x)| < e.

To find the negation of a statement Q constructed out of components Z4-Z7, it is enough to know how to negate each of statements Z4-Z7, and then to apply those principles to each of the components in turn. It is easy to find the negations of Z4-Z7. Using the notation ~ P to denote the negation of P, the negations of Z4-Z7 are:

~ Z4:

$x Î S such that ~ P(x);

~ Z5:

"x Î S, ~ P(x);

~ Z6:

~ P or ~ P¢;

~ Z7:

~ P and ~ P¢.

It should be clear to you after a little thought that this list is correct. If you are worried, try taking the following specific examples:

Z9:

Every undergraduate in my college is male;

Z10:

There is an undergraduate in my college who is less than 10 years old;

Z11:

x > 0 and x < 1;

Z12:

x > 1 or x < 0.

Now, if Q is composed of several clauses of the type Z4-Z7, we can find the negation of Q by applying the negation clause by clause until eventually we have only to take the negation of a simple statement. For example, the statement Z8 has the form:

Z13:

"x Î R, P(x),

where, for the moment, we are not bothered what P(x) is. So the negation of Z13 is:

~ Z13:

$x Î R such that ~ P(x).

Now, we have to work out what ~ P(x) is. Since P(x) is of the form:

Z14:

"e > 0, Q(x,e),

its negation is:

~ Z14:

$x Î R such that ~ Q(x,e).

Hence, the negation of Z8 is:

Z15:

$x Î R $e > 0 such that ~ Q(x,e).

Continuing in this way, we eventually find that the negation of Z8 is:

~ Z8:

$x Î R $e > 0 such that "d > 0 $y Î (x-d,x+d) such that |f(y)-f(x)| ³ e.

We can convert this back into a more readable form to find what it means to say that f is discontinuous:

~ Z3:

There exist x Î R and e > 0 such that, for all d > 0, there exists y such that |y-x| < d and |f(y)-f(x)| ³ e.

It is very easy to summarise this procedure of taking negations:

1.

Convert the statement into basic mathematical form by replacing technical terms by their definitions.

2.

Write the statement in a formal style using the constructions Z4, Z5, Z6, and Z7.

3.

Change each " to $, each $ to ", each logical ``and'' to ``or'', and each logical ``or'' to ``and''; take the negations of the remaining simple statements (this should be easy, for example reversing an inequality).

4.

Convert the negation into more readable form.

We should warn you about two points. Firstly, when we say that each ``and'' should be replaced by ``or'', and vice versa, this applies only when the word ``and'' or ``or'' is used as in Z6 or Z7. It does not apply when ``and'' or ``or'' is subordinate to a quantifier. For example, the negation of the statement:

Z16:

For all x Î S and all a Î A, P(x,a) (formally, "x Î S "a Î A, P(x,a))

is:

~ Z16:

There exist x Î S and a Î A such that ~ P(x,a) (formally, $x Î S $a Î A such that ~ P(x,a).

Secondly, in Dependence, we recommended that in a statement such as Z3 or Z8, you might write d_e instead of d to remind yourself that d may depend on e. However, if you are going to take the negation of the statement, you should not do such a thing; if you do, the negation will come out somewhat garbled.

At the beginning of this section, we described the three strategies for proving a statement of the form Z1: If P, then Q (direct, contrapositive, reductio ad absurdum). Often you will be required to prove a statement of the form:

Z17:

P if and only if Q.

This means that you have to prove both of the following (see Implications):

Z1:

If P, then Q;

Z18:

If Q, then P.

There are three strategies for proving Z1. Whichever way you choose to prove Z1, you are free to choose any of the three strategies to prove Z18. Thus, there are (at least) nine different strategies for proving Z17. For example, you might assume P and deduce Q (a direct proof of Z1), and then assume Q and deduce P (a direct proof of Z18). Alternatively, you could assume P and deduce Q, then assume that P is false and deduce that Q is false (a proof of the contrapositive of Z18).

This is an opportunity to repeat a warning made in Implications. It is tempting to try to save time by proving Z1 and Z18 simultaneously. You are advised to resist the temptation, as this process very rarely works. Only occasionally is it possible to give a complete proof which works logically accurately in both directions at once. In attempting to construct such a proof, you may well confuse yourself and end up by proving neither direction satisfactorily.