One of the most important pieces of advice to keep in mind is: “Use the definition”. In the world of mathematics, terms mean exactly what they are defined to mean and nothing more. Definitions allow very complex ideas to be summarized as single terms. When you are trying to prove things about those terms, you generally need to ‘unwind’ the definitions. In our example above, we used the definition of even to write n = 2k, and then we worked with that equation. When you are trying to prove something about equivalence relations in Chapter 4, you can be pretty sure that you will need to use the fact that equivalence relations, by definition, are symmetric, reflexive, and transitive. (And, of course, you’ll need to know how the term ‘relation’ is defined in the first place! We mean something quite different than the idea that ‘relations’ are something like your aunt and uncle.)
More advice along the same line is to check whether you are using the assumptions of the theorem. An assumption that is made in a theorem is called an hypothesis. The hypotheses of the theorem state conditions whose truth will guarantee the conclusion of the theorem. To prove the theorem means to assume that the hypotheses are true, and to show, under that assumption, that the conclusion must be true. It’s likely (though not guaranteed) that you will need to use the hypotheses explicitly at some point in the proof, as we did in our example above.1 Also, you should keep in mind that any result that has already been proved is available to be used in your proof.
A proof is a logical argument, based on the rules of logic. Since there are really not all that many basic rules of logic, the same patterns keep showing up over and over. Let’s look at some of the patterns.
The most common pattern arises in the attempt to prove that something is true ‘for all’ or ‘for every’ or ‘for any’ entity in a given category. In terms of logic, the statement you are trying to prove is of the form ∀x P(x). In this case, the most likely way to begin the proof is by saying something like, “Let x be an arbitrary entity in the domain of discourse. We want to show that P(x).” We call this a proof by generalisation In the rest of the proof, x refers to some unspecified but definite entity in the domain of discourse. Since x is arbitrary, proving P(x) amounts to proving ∀x P(x). You only have to be careful that you don’t use any facts about x beyond what you have assumed. For example, in our proof above, we cannot make any assumptions about the integer n except that it is even; if we for instance also assume x = 6 or that x is divisible by 3, then the proof would have been incorrect, or at least incomplete.
Sometimes, you have to prove that an entity exists that satisfies certain stated properties. Such a proof is called an existence proof. In this case, you are attempting to prove a statement of the form ∃x P(x). The way to do this is to find an example, that is, to find a specific entity a for which P(a) is true. One way to prove the statement “There is an even prime number” is to find a specific number that satisfies this description. The same statement could also be expressed “Not every prime number is odd.” This statement has the form ¬(∀x P(x)), which is equivalent to the statement ∃x (¬P(x)). An example that proves the statement ∃x (¬P(x)) also proves ¬(∀x P(x)). Such an example is called acounter example to the statement ∀x P(x): A counterexample proves that the statement∀x P(x) is false. The number 2 is a counterexample to the statement “All prime numbers are odd.” In fact, 2 is the only counterexample to this statement; many statements have multiple counterexamples.
Note that we have now discussed how to prove and disprove universally quantified statements, and how to prove existentially quantified statements. How do you disprove ∃x P(x)? Recall that ¬∃x P(x) is logically equivalent to ∀x (¬P(x)), so to disprove∃x P(x) you need to prove ∀x (¬P(x)).
Many statements, like that in our example above, have the logical form of an implication, p → q. (More accurately, they are of the form “∀x (P(x) → Q(x))”, but as discussed above the strategy for proving such a statement is to prove P(x) → Q(x) for an arbitrary element x of the domain of discourse.) The statement might be “For all natural numbers n, if n is even then n2 is even,” or “For all strings x, if x is in the language L then x is generated by the grammar G,”2 or “For all elements s, if s ∈ A then s ∈ B.” Sometimes the implication is implicit rather than explicit: for example, “The sum of two rationals is rational” is really short for “For any numbers x and y, if x and y are rational then x + y is rational.” A proof of such a statement often begins something like this:
“Assume that p. We want to show that q.” In the rest of the proof, p is treated as an assumption that is known to be true. As discussed above, the logical reasoning behind this is that you are essentially proving that
is a valid argument. Another way of thinking about it is to remember that p → q is automatically true in the case where p is false, so there is no need to handle that case explicitly. In the remaining case, when p is true, we can show that p → q is true by showing that the truth of q follows from the truth of p. So remember than proving an implication you should assume the antecedent and prove the consequent (you can refresh your memory of what those words mean on page 10).
A statement of the form p ∧ q can be proven by proving p and q separately. A statement of the form p ∨ q can be proved by proving the logically equivalent statement(¬p) → q: to prove p ∨ q, you can assume that p is false and prove, under that assumption, that q is true. For example, the statement “Every integer is even or odd” is equivalent to the statement “Every integer that is not even is odd”.
Since p ↔ q is equivalent to (p → q) ∧ (q → p), a statement of the form p ↔ q is often proved by giving two proofs, one of p → q and one of q → p. In English, p ↔ q can be stated in several forms such as “p if and only if q”, “if p then q and conversely,” and “p is necessary and sufficient for q”. The phrase ‘if and only if’ is so common in mathematics that it is often abbreviated iff .
You should also keep in mind that you can prove p → q by displaying a chain of valid implications p → r → s → · · · → q. Similarly, p ↔ q can be proved with a chain of valid biconditionals p ↔ r ↔ s ↔ · · · ↔ q.