3.5: Proof Strategies

There are two elementary logical forms that occur so commonly in mathematical claims that they warrant some general discussion.

3.5.1. Universal Statements.

A logical form you are likely to encounter very often is \[(\forall x)[H(x) \Rightarrow P(x)] \text {, }\] where \(H(x)\) and \(P(x)\) are formulas in one variable. Statements in this form are called universal statements. The formulas \(H\) and \(P\) are used to characterize properties of mathematical objects, so that the claims in this form may be thought of as stating:

If a mathematical object has property \(H\), then it has property \(P\) as well.

This is particularly useful if we know a great deal about mathematical objects that have property \(P\). Because the statement we are endeavoring to prove is universal, examples do not suffice to prove such claims - the example you cite might accidentally have properties \(H\) and \(P\). Rather, universal claims must be proved abstractly, arguing that satisfying a definition or set of properties implies the satisfaction of other properties. This generally requires carefully evaluating definitions. In practice, we often do this by assuming that we have an arbitrary element that satisfies a definition or explicit assumptions, and logically derive additional conclusions about this object. By arbitrary we mean that we are not allowed to make any claims about the element except those that follow immediately from definitions, explicit assumptions, or are logically derived from definitions and explicit assumptions. Since the object was arbitrary (except for the explicit assumptions you make at the outset of the argument), the conclusions you derive concerning the object will be true universally of all objects which satisfy the assumptions.

EXAMPLE 3.15. Suppose \(F(x)\) is the formula: \[\text { " } x \in \mathbb{N} \text { and } x \text { is a multiple of } 4 . "\] Let \(E(x)\) be the formula: \[\text { " } x \text { is even." }\] Then \[(\forall x)[F(x) \Rightarrow E(x)] .\] It does not suffice to observe that 4,8 and 12 are all even. In order to argue for the statement directly, you would argue abstractly that any object which satisfies \(F(x)\) necessarily satisfies \(E(x)\).

There are a couple of approaches that one commonly considers when proving conditional statements. Choosing an approach is choosing a strategy for the proof. Normally, more than one strategy can be made to work, but often one may be simpler than the others.

Claims of the form (3.14) are generally approached in one of the following ways:

(1) Direct Proof. Let \(x\) be an object for which \(H\) holds. By decoding the property \(H\), you might be able to show directly that \(P\) holds of \(x\) as well. Since \(x\) was an arbitrary object satisfying \(P\), the universal claim will be proved.

EXAMPLE 3.17. Prove (3.16) directly.

Let \(x \in \mathbb{N}\) (we treat \(x\) as a fixed but arbitrary element of the natural numbers). If \(x=4 n\), then \[x=2 \cdot(2 n),\] and is therefore even.

EXAMPLE 3.18. Prove that any 3 points in the plane are either collinear or lie on a circle.

Proof. Label the points \(A, B, C\). Let \(L\) be the perpendicular bisector of \(A B\). Every point on \(L\) is equidistant from \(A\) and \(B\).

Let \(M\) be the perpendicular bisector of \(B C\). Every point on \(M\) is equidistant from \(B\) and \(C\).

If \(A, B\) and \(C\) are not collinear, the lines \(L\) and \(M\) are not parallel, so they intersect at some point \(D\). The point \(D\) is equidistant from \(A, B\) and \(C\), so these points lie on a circle centered at \(D\).

EXAMPLE 3.19. Pythagoras’s theorem can be stated in the form (3.14). (What are \(H\) and \(P\) in this case?) Euclid’s proof of Pythagoras’s theorem is a direct proof (Euclid’s Elements I.47).

(2) Contrapositive Proof.

It is sometimes easier to show that the failure of \(P\) implies the failure of \(H\). Assume you have an object for which \(P\) fails (that is assume \(\neg P\) holds of the object). Derive that \(H\) must fail for the object as well. In this case you will have demonstrated that \[(\forall x)[\neg P(x) \Rightarrow \neg H(x)] .\] This is equivalent to the claim \[(\forall x)[H(x) \Rightarrow P(x)] .\] EXAMPLE 3.20. Prove (3.16) by proving the contrapositive.

Let \(x \in \mathbb{N}\), and assume \(\neg E(x)\), so \(x\) is odd. As \(x\) is odd, then \(x\) divided by 4 has remainder 1 or 3 . Then, \[x \neq 4 n \text {. }\] So \(x\) is not a multiple of 4 .

EXAMPLE 3.21. Prove that if \(x\) is an integer and \(x^{2}\) is even, then \(x\) is even.

The contrapositive is the assertion that if \(x\) is an odd integer, then \(x^{2}\) is odd. We shall prove this.

Suppose \(x\) is odd, so \(x=2 n+1\) for some integer \(n\). Then \(x^{2}=\) \(4 n^{2}+4 n+1\), so \(x^{2} \equiv 1 \bmod 2\), and \(x^{2}\) is therefore odd.

(3) Contradiction.

This is a proof in which we show that \(H \wedge \neg P\) is necessarily false. That is, assume that \(H\) holds for an arbitrary object and \(P\) fails for that object, and show that this gives rise to a contradiction. Since contradictions are logically impossible, it is logically necessary that \[\neg(H \wedge \neg P)\] which is propositionally equivalent to \[\neg H \vee P\] or, alternatively, \[H \Rightarrow P \text {. }\] Since we shall have shown that for any substitution of \(x\), the statement \(H \Rightarrow P\) holds, we shall have shown the universal claim.

EXAMPLE 3.22. Prove (3.16) by contradiction.

Assume that \(x\) is a multiple of 4 and that \(x\) is odd. Let \(r\) be the residue of \(x\) modulo 2 . Since \(x\) is a multiple of \(4=2 \cdot 2\), we have that \(r \equiv 0 \bmod 2\). Since \(r\) is odd, we have that \(r \equiv 1 \bmod 2\). This implies \(0 \equiv 1 \bmod 2\), a contradiction. Therefore the assumption that there was an \(x\) that was both a multiple of 4 and odd is false, and so ((3.16) must be true. EXAMPLE 3.23. Prove that \(\sqrt{2}\) is irrational.

Proof. We restate this as an implication: If a number is rational, it’s square cannot equal 2 . We begin by considering the logical structure of the claim. Here the hypothesis \(H(x)\) is that \(x\) is a rational number, and the conclusion \(P(x)\) is that \(x^{2} \neq 2\). We wish to prove \[(\forall x) H(x) \Rightarrow P(x) .\] We shall give a proof by contradiction. That is, we assume the statement is false and derive a contradiction. So we assume \[\neg((\forall x) H(x) \Rightarrow P(x)) .\] This is logically equivalent to \[(\exists x) H(x) \wedge \neg(P(x)) .\] Let’s go back to mathematical prose now that we have fought through the logic. Assume that \(x\) is a rational number, and assume also that \(x^{2}=2\); we wish to derive a logical contradiction. Write \(x=m / n\), where \(m\) and \(n\) are non-zero integers that have no common factors. Then \[x^{2}=m^{2} / n^{2}=2,\] so \(m^{2}=2 n^{2}\). Therefore \(m^{2}\) is even, so by Example 3.21, \(m\) is even. Therefore \(m=2 k\) for some integer \(k\), and so \[m^{2}=4 k^{2}=2 n^{2} .\] Therefore \(n^{2}=2 k^{2}\) is even, so \(n\) is even. But then both \(m\) and \(n\) are even, and so have 2 as a common factor, which contradicts the assumption that \(m / n\) was the reduced form of the rational number \(x\).

Contrapositive proofs and proofs by contradiction are very similar. Indeed, any contrapositive proof, that \(\neg P \Rightarrow \neg H\), automatically yields that \((H \wedge \neg P)\) is impossible. The distinction is more linguistic than logical. The reason for having names for different proof strategies is to provide guidance to the reader in order to make the proof easier to follow. In Chapter 4 we shall see another powerful method for proving universal statements over \(\mathbb{N}\), namely the Principle of Induction.

3.5.2. Existence Proofs.

A second common form for a mathematical claim is an existential statement, that is, a statement in the form \[(\exists x) P(x) \text {. }\] There are three common approaches to proving existential statements.

(1) Construction.

Obviously, the most direct way to show that something exists with certain properties is to introduce or construct an object with property \(P\). For claims in this form, the example is the proof, although you will need to show that the object satisfies \(P\), if it is not obvious.

ExAmPLE 3.25. Prove that there exists a real function whose first derivative is everywhere positive, and whose second derivative is everywhere negative.

PrOOF. The easiest way to do this is to write down a function with these properties. One such function is \(f(x)=1-e^{-x}\). The derivative is \(e^{-x}\), which is everywhere positive, and the second derivative is \(-e^{-x}\), which is everywhere negative.

(2) Counting.

Sometimes one can establish an object’s existence by a counting argument.

ExAMPLE 3.26. Suppose there are 30 students in a class. Show that at least two of them share the same last initial.

PROOF. For each letter \(A, B, \ldots\) group all the students with that letter as their last initial. As there are only 26 groups and \(30>26\) students, at least one group must have more than on student in it.

The argument we just gave is called the "pigeon-hole principle", based on the analogy of putting letters into pigeon-holes. If there are more letters than pigeon-holes, then some pigeon-hole must have more than one letter. Notice that unlike a constructive proof, a counting proof does not tell you which group has more than one element in it.

For Cantor’s spectacular generalization of the pigeon-hole principle to infinite sets, see Chapter 6 .

(3) Contradiction.

It can be difficult to prove existential statements by construction. An alternative is to assume that the existential statement is false (that there is no object which satisfies \(P(x)\) ). If it is impossible that no object has property \(P\), then some object must. Again, this approach may not give us much insight into the objects that have property \(P\). See e.g. Exercise 3.27.

EXAMPLE 3.27. Suppose all the points in the plane are colored either red or blue. Prove that there must be two points of the same color exactly one unit apart.

Proof. Assume there are not. Draw an equilateral triangle of side 1. Label its vertices \(A, B\) and \(C\). Then \(A\) and \(B\) must be different colors, \(B\) and \(C\) must be different colors, and \(C\) and \(A\) must be different colors. This is impossible with only two colors to choose from.

Notice that we have not said whether there is a red-red pair that is unit distance apart, or a blue-blue pair that is unit distance apart, just that one such pair must exist.