Ideally, mathematical proofs would start with statements that are known, or assumed to be, true and proceed through a series of steps to a final theorem. At each step a new statement would be shown to be true as a consequence of previous statements. However, in number theory in particular, it is often necessary to resort to less direct methods of proof.

Suppose P and Q are certain statements. If the truth of P implies that Q is true, we cannot assume the converse, that is, that Q implies that P is true. For example x = 1 implies that x^{2} = 1, but if x^{2} = 1, x is not necessarily 1. If the converse does happen to be true, we say that “P is true if and only if Q is true”, or that the statements P and Q are logically equivalent. For example, as can be easily shown, n is odd if and only if n^{2} is odd for all integers n.

Although the statement “If P is true then Q is true” does not imply its converse, it does imply the contrapositive, namely “If Q is false then P is false”. For example if x^{2} ≠ 1 then x ≠ 1. In number theory, propositions are often proved by proving the contrapositive.

If the truth of P implies Q is true, then the truth of Q is a necessary condition for P to be true, that is, P cannot be true unless Q is true, and it is not possible for P to be true if Q is false. If the truth of Q implies P is true, then Q is a sufficient condition for P to be true. That is, instances of Q being true can provide us with instances of P being true, but not necessarily all such instances. If Q is both necessary and sufficient then it is the logical equivalent of P. P is true on precisely those occasions when Q is true.

Reductio ad absurdum is a variant of the contrapositive. Suppose P is a proposition that it is desired to prove true. This method of proof starts with the proposition that P is false and shows that this leads to a conclusion that is either known to be false, or contradicts the proposition that P is false. This is considered to negate the proposition that P is false and hence prove that P is true.

As an example of its use (and also the use of the contrapositive), we prove that √2 is irrational. Start by assuming the contrary, that is, that √2 = p/q for some positive integers p, q . Because a number can be represented as a fraction in infinitely many ways, assume that it is possible to cancel out common multiples of 2 from p and q until at least one of p and q is odd (it is not necessary to assume that this process results in p and q being unique). p^{2} = 2q^{2} so p^{2} is even. But if p is odd p^{2} is odd so p must be even. Thus p^{2} = 4k^{2} for some positive integer k. Thus q^{2} is even, so q is even, a contradiction. Therefore our starting proposition must be false.

Infinite descent is a specific form of reductio ad absurdum. It was used by Pierre de Fermat around 1640 to prove that there are no non-zero integer solutions to the equation x^{4} + y^{4} = z^{4} where z,y,z are positive integers, and has been widely used in other problems. It assumes the negative of the proposition, that is that there is a solution for some z, and shows that the existence of a solution for any value of z implies the existence of a solution for a smaller value of z, which is impossible because there is a least value of z (i.e. 1) beyond which no further solutions can exist.

Suppose that there is a (finite or infinite) sequence of propositions P_{1}, P_{2}, and so on. The Principle of Induction states that if P_{1} is true and if we can demonstrate that if P_{k} were true for any given k then P_{k+1} would be true, then all of P_{1}, P_{2}, … are true.

It is sometimes more practical to use the following corollary. If P_{1} is true and if we can demonstrate that if for any given k, P_{i} were true for all 1 ≤ i ≤ k, then P_{k+1} would be true, then all of P_{1}, P_{2}, … are true.

For let P’_{k} be the proposition that P_{i} is true for all 1 ≤ i ≤ k. If P_{1} is true then P’_{1} = P_{1} is true. If the truth of P’_{k} implies the truth of P_{k+1} then it implies the truth of P’_{k+1}. Therefore by induction all the P’ are true and so all the P are true.

## Leave a Reply