Forms of Proof

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 x2 = 1, but if x2 = 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 n2 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 x2 ≠ 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). p2 = 2q2 so p2 is even. But if p is odd p2 is odd so p must be even. Thus p2 = 4k2 for some positive integer k. Thus q2 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 x4 + y4 = z4 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 P1, P2, and so on. The Principle of Induction states that if P1 is true and if we can demonstrate that if Pk were true for any given k then Pk+1 would be true, then all of P1, P2, … are true.

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

For let P’k be the proposition that Pi is true for all 1 ≤ i ≤ k. If P1 is true then P’1 = P1 is true. If the truth of P’k implies the truth of Pk+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

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s