Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > First Principles > Logic and Proof > Methods of Proof

Direct Proof

If the statement to be proved is of the form "if p then q", then a direct proof draws conclusions from p, then more conclusions from those, until q is shown true.

Cases

Often it's not so easy to  find a chain of statements leading directly from p to q.  Instead, statements like this can be found:

if p then a or b

And then other chains of statements lead from a to q, and still others lead from b to q.  When this happens, a proof is divided into cases.  In "case a", we assume that p and a are true, and prove q.  In "case b", we assume that p and b are true, and prove q.  As you can see, by dividing a proof into cases, we have more to work with, because in each case, there are more things we know to be true.

Example: The proof of the Triangle Inequality relies on cases.

In proposition logic, a proof by cases uses a technique called "Disjunction Elimination".

Strong, or "complete", Induction

Let P(n) be a property of an integer, n.  If we want to show P(n) by strong induction, we assume P(n) is true for all integers smaller than n and larger than or equal to b.  Then we deduce from this assumption that P(n) is true.

Weak, or "ordinary", Induction

Let P(n) be a property of an integer, n.  If we want to show P(n) by weak induction, we show that P(b) is true (the base case) for some small integer, b.  Then we show that if P(k) is true then P(k+1) is also true.

Note that ordinary induction can be used to derive strong induction as follows:  Let Q(n) be the property that P(k) is true for all k between b and n (inclusive).  Note that Q(b) is the same as P(b), so this is the base case.  Now if we assume Q(k) and can deduce that Q(k+1) is true using ordinary induction, we have shown that P(k+1) is true.  But this is the same as showing that P(k) for all k between b and n (inclusive) implies P(k+1), which is strong induction.

Weak induction is weak in the sense that it's a less powerful tool for use in proofs, because you are allowed to use only P(k) to prove P(k+1), but you are not allowed to use P(x) where x is smaller than k to show that P(k+1) is true.  So it is helpful to know that the validity of weak induction supports the validity of strong induction.  That way, the mathematician's toolbox is increased in size and power.

Multiplicative Induction

Multiplicative induction can be used in cases where it can be shown that an arbitrary prime, p, has property "E".  In this method, we assume a natural number, m, is "E", and then prove that mp is also "E".

A function, f, is "multiplicative" if GCD(a,b)=1 implies f(ab) = f(a) f(b).  Multiplicative induction is often a convenient way to prove statements regarding multiplicative functions.  Examples of multiplicative functions include the totient and M�bius functions.

Contradiction

Also called "reductio ad absurdum", a proof by contradiction begins by assuming the opposite of the thing to be proved, then reaching a statement so blatantly false, that the original statement must be true.

The statement "P implies Q" (sometimes stated "If P then Q") is true except when P is true and Q is false.  In other words "P implies Q" means the same thing as "~P or Q".  (The tilde, ~, means "not".)  Everyday speech confirms this.  A robber might say "you will give me your money or I will shoot you".  This statement is clearly the threat, "If you don't give me your money then I will shoot you".  If taken not as a threat but as a statement whose truth value may be assessed, we can let P be "you don't give me your money" and Q be "I will shoot you".  The robber is saying P implies Q, but the way he phrased it was "~P or Q"

"P implies Q" means "~P or Q", which means the same thing as "~P or ~~Q" because two "nots" flip the truth value of Q twice, canceling each other.  "~P or ~~Q" means "~~Q or ~P" because changing the order doesn't matter, and this means the same as "~Q implies ~P".  This is a fairly long-winded way of saying that "P implies Q" means the same as "~Q implies ~P".  An example might make this clearer: Let P be "x is an integer" and let Q be "x2 is an integer".  So "if x is an integer then x2 is an integer" (Q implies P) is a true statement.  What if x2 is not an integer?  In that case, x could not be an integer, because if it were then x2 would have been an integer, so we can conclude that x is not an integer.  In other words, "not Q implies not P".

In a proof by contradiction, we let Q be the statement to be proved, and assume the opposite, namely that ~Q is true.  Then, through a series of steps, we show that ~Q implies ~X where X is chosen to be an axiom or other universally accepted fact.  That is, we arrive at a contradiction.  The key point is that it doesn't matter what we contradict.  If we let X be 1=1, then we show that ~Q implies 1 is not equal to 1.  Then, since "~Q implies ~X" means the same as "X implies Q", we show that if 1=1 then Q is true.  Well, we know 1=1, so Q is true.

Interestingly, arguments that rely on contradiction make their way into everyday speech.  For example, a person might say "the day that X happens, pigs will fly".  The statement that pigs will fly (or that the moon is made of green cheese, etc.) is clearly false, and the fact that X happening implies this falsity shows that X will not happen: an everyday "proof" by contradiction.

Infinite Descent

In an "Infinite Descent" proof (sometimes called Infinte Regression), you first assume that a set of numbers with a certain property exists.  Then you find another set of numbers with the same property that's smaller in some specific way than the set of numbers.  If you assume the first set of numbers is minimal, then just one iteration of this descent is enough to prove by contradiction that there is no number with that certain property, but the method is called "Infinite" Descent because it shows more than just a contradiction; it shows that there are no smallest numbers with the given property.

Finding the "Trick"

Sometimes, when you're reading a proof, you will wonder, "how did they ever think of that?"  One way to find the trick is to run the proof backwards.  For example, to prove the quadratic formula, which gives the two roots r1 and r2, start by setting (x-r1)(x-r2)=0, and then it won't take long to derive the starting point, ax2+bx+c=0.  See the proof of the quadratic formula for the details.

Internet references

Dr. Math: Proof FAQs -- help for students on how to make a 2-column proof, and other such questions

Wikipedia: Mathematical induction 

Related pages in this website

Basic Principles

Proposition Logic

A discussion of the Infinite Descent form of proof.

 

The webmaster and author of this Math Help site is Graeme McRae.