|
|
A mathematics proof establishes the validity of a mathematics statement. Statements are assertions that can be broadly classified under two types: Existence statements and others. An existence statement asserts that objects with a given property exist.
Here is an existence statement: Given two rational numbers, there is a rational number between them.
An existence statement is proved in one of two ways. One way is to construct and exhibit the objects whose existence is postulated by the existence statement. This is called a constructive proof, which is a proof method. For instance, given two rational numbers a and b, we may consider the number (a+b)/2 and show that it is rational and lies between a and b - thus we have constructed a rational number lying between any two rational numbers. Clearly, constructions for some existence statements can be difficult and there are existence statements for which constructions are not known.
A second way to prove an existence statement is by proving that the objects in question must exist. This is a non-constructive proof. A famous example of this is afforded by Cantor's proof of the non-denumerability of real numbers. Combining with his proof of the denumerability of rational numbers, it proves the existence of irrational numbers without actually constructing any irrational number.
Nonconstructive proofs are also used for proving statements other than existence statements.
In fact, these are the proofs used for proving statements other than existence statements.
Here is the summary of what we have discussed so far:
There are two kinds of proofs - constructive and nonconstructive. The only use of constructive proofs is in proving existence statements and sometimes it can be very difficult to find a constructive proof for a given existence statement. Nonconstructive proofs are used in proving statements other than existence statements; they are also used sometimes to prove existence statements.
The remainder of this discussion will be about nonconstructive proofs.
There are two kinds of nonconstructive proofs: Direct Proof and Indirect Proof.
Before we discuss these, we shall explain a technique called "Conditional Proof" that can be used in both direct and indirect proofs. Since Conditional Proof is applicable in any proof, we shall consider it a "special" inference rule.
This rule arises from a theorem in Propositional Logic, called the Deduction Theorem.
We recommend to younger students reading this page the first time to take a break here and return on a different day.
Deduction Theorem
If from a set of wffs G we can derive q from p1, p2, ⋯ pn, then we can derive (pn ⇒ q) from p1, p2, ⋯ pn-1 and G.
We use the standard notation p1, p2 ⊢ q to say that q is derived from p1 and p2. The Deduction Theorem says that if p1, p2 ⊢ q, then p1 ⇒ (p2 ⇒ q).
Deduction Theorem justifies the technique known as the Rule of Conditional Proof (CP).
To prove that q ⇒ r in a line of proof, we temporarily introduce the premise q and if now we can prove r, then by the Deduction Theorem we have proved q ⇒ r and the assumption q may be discharged from further use in the remaining portion of the proof. It is called Conditional Proof, because we have not proved the truth of r; we have only proved that if q is true then r is true. r is shown to be true provided that q is true. That is, r is true on the condition that q is true.
Direct Proof
Every direct deductive proof has this form: Assume as true a premise p and then establish p ⇒ q so that, by Modus Ponens, q would be true.
The work in this proof then is in establishing p ⇒ q, which often requires many steps: p ⇒ q1 ⇒ q2 ⇒ ⋯ qn ⇒ q.
By the rule of Hypothetical Syllogism, then p ⇒ q. Direct Proof is the preferred method of non-constructive proof.
A direct proof with many steps is like crossing a stream by stepping on steppable protuberances in the water.
Example:
If a and b are integers with b ¹ 0 and q and r are non-negative integers such that a = bq + r,
then gcd(a,b) ≤ gcd(b,r).
(gcd(a,b) means the greatest common divisor of a and b. For instance, gcd(4,6) = 2.)
Here the premise is this: a and b are integers with b ¹ 0 and q and r are non-negative integers such that a = bq + r. The conclusion is gcd(a,b) ≤ gcd(b,r). First we set up the problem. We ask, what do we need to show to establish gcd(a,b) ≤ gcd(b,r)? Well, if we can show that any common divisor of a and b is also a common divisor of b and r, then the largest (greatest) common divisor of a and b will be a common divisor of b and r. Since any common divisor of b and r can not exceed gcd(b,r), we will be done.
So the proof goes like this.
Given: a and b are integers with b ¹ 0 and q and r are non-negative integers such that a = bq + r.
To show: gcd(a,b) ≤ gcd(b,r).
It is sufficient to show that any common divisor of a and b is a common divisor of b and r.
Let c be a common divisor of a and b.
From c|a, we get a = nc, for some integer n.
From c|b, we get b = mc, for some integer m.
Then from r = a-bq, we get r = (n-mq)c, which means c|r.
But c|b. Hence c is a common divisor of b and r. QED
(Notice that the first three steps in the proof constitute a setting up of the proof. In the fourth step we have the premise of the proof. Then we went from step to step using rules of arithmetic and logic. In the last step, we used the rule that (X ⇒ Y).(X ⇒ Z) ⇒ (X ⇒ Y.Z). So you see, a proof of a theorem in a branch of mathematics uses the rules, definitions, axioms, and theorems of that branch of mathematics along with the rules of Logic.
Incidentally, one can similarly prove that gcd(b,r) ≤ gcd(a,b). That would mean gcd(a,b) = gcd(b,r), which is the principle behind the Euclidean Algorithm.)
Establishing p ⇒ q in situations where q is a statement that holds for all natural numbers greater than or equal to a specific natural number is often accomplished by a method called Mathematical Induction (MI). MI is a direct proof method.
Recommended break: Return to read another day!
Indirect Proof
An Indirect Proof is so called because, in it, to establish p ⇒ q, we start with ~q. Indirect proofs can take three forms.
1. Indirect proof by Contraposition
The contrapositive or counterpositive of p ⇒ q is ~q ⇒ ~p.
A truth table will show that (p ⇒ q) ⇔ (~q ⇒ ~p). That is, whenever p ⇒ q is true, ~q ⇒ ~p is true. So when ~q ⇒ ~p is established, p ⇒ q is established, and since p is the premise and hence assumed as true, q would be true by Modus Ponens. This is proof by contrapositive. So why use a contrapositive proof when it is equivalent to proving p ⇒ q? The reason is that in some instances, ~q may contain more information than p and it might be easier to establish ~p from ~q than q from p.
Example:
For any prime p, if p divides n2 then p divides n.
Proof: The contrapositive is, if p does not divide n then p does not divide n2. Since p does not divide n, n = pt + r, for some integer t and r and 0 < r < p.
Then n2 = p(pt2 + 2tr) + r2. But r < p implies r2 < p2. So if r2 = bp, for some b, b < p. But if b < p, bp is not a perfect square. So r2 ¹ bp, for any integer b. This means r2 = bp + r' for some b and r', 0 < r' < p. Then n2 = b'p + r', and hence n2 is not divisible by p. QED
If we tried a direct proof, we would have to invoke the Fundamental Theorem of Arithmetic - every positive integer is a unique product of prime powers - or a variation of it. So the proof by contrapositive was the better choice here.
2. Indirect Proof by Contradiction (of the premise)
If p and ~q together generate ~p, then we conclude that p ⇒ q. The reasoning behind this argument is the following:
(p ⇒ q) ⇔ (~p ∨ q). And ~(~p ∨ q) ⇔ (p ∧ ~q), by De Morgan Rule. This means the negation of "If p, then q" is "p
is true and q is false" So, to give a proof by contradiction
of "If p, then q," we assume that p is true and q is
false and derive ~p. From this we conclude - see RAA Theorem below - that the negation of 'p is true and q is false', namely p ⇒ q is true.
3. Indirect Proof by Reductio Ad Absurdum (RAA)
In Reductio Ad Absurdum, meaning reduction to the absurd, we again start with p and ~q, but it is not necessary to arrive now at ~p; arriving at any contradiction will suffice. Note that p as well as ~p is a contradiction too. So, Proof by Contradiction (of the premise) is a Reductio Ad Absurdum Proof. This is why many mathematicians often call a Proof by Contradiction (of the premise) a Reductio Ad Absurdum proof. However, you can readily see that not every Reductio Ad Absurdum proof is a Proof by Contradiction, in the sense we have described above. We recommend that a Proof by Contradiction be one that begins with p and ~q and ends up obtaining the negation of the premise, and that a Reductio Ad Absurdum Proof be one that ends up obtaining any contradiction of a known truth.
Recommended break: Return to read another day!
Here is a formal proof that RAA is a theorem in Propositional Logic. This theorem also justifies the Indirect Proof by Contradiction. The steps are explained after the proof.
Theorem (RAA):
Suppose p,q such that p and ~q together imply a contradiction, then p ⇒ q.
| (1) | p | [Premise] |
| (2) | ~q | [Premise, Conditional Proof] |
| (3) | p,~q ⊢ (C ∧ ~C) | [RAA step] |
| (4) | p ⇒ (~q ⇒ (C ∧ ~C) | [Deduction Theorem, 3] |
| (5) | ~q ⇒ (C ∧ ~C) | [MP, 1,4] |
| (6) | (~q ⇒ (C ∧ ~C)) ⇒ (~(C ∧ ~C) ⇒ q) | [T] |
| (7) | ~(C ∧ ~ C) ⇒ q | [MP, 5,6] |
| (8) | ~(C ∧ ~C) | [T] |
| (9) | q | [MP, 7,8] |
| (10) | p ⇒ q | [Deduction Theorem,1,8] |
The numbers in parentheses in the left column denote the numerical order of the steps. The description in square brackets in the right column gives the reasoning used to obtain the entry in the middle column.
In step (1) we assume p as premise. In step (2) we have used the Rule of Conditional Proof to introduce a new premise ~q.
Step (3) obtains a contradiction using also p - this is explained as the RAA step.
Step (4) uses the Deduction Theorem that if we can derive something, say X, from p and ~q, we can derive ~q ⇒ X from p alone. At this point an unusual thing happens. That is, ~q jumps from being in the antecedent of the conditional in the previous step to the consequent part in the current step.
This means ~q is no longer a premise. It is said to be 'discharged' from being a premise. A discharged premise can no longer be regarded as a premise even if it reappears in the antecedent in a later step.
Step (5) uses Modus Ponens (MP) on steps 1 and 4. Step (6) is the tautology (T) arising from the equivalence of the conditional of step (5) and its contrapositive. That is, (A ⇒ B) ⇒ (~B ⇒ A) is a tautology. Step (7) is clear. Step (8) is a tautology (T), being the negation of a contradiction. Step (9) is clear. Now with ~q having been discharged from being a premise, only p remains as a premise. Step (10) says that having established q in step 8, with p as the only remaining premise ( step 1), we have p ⇒ q.
(Note that we have here established RAA as a theorem in Propositional Logic. A proof of RAA in the more general setting including Predicate Logic would be necessary to handle all instances in mathematics. The general Deduction Theorem is the following: "If G is a collection of formulas with no free variables, and for some formula C, there is a proof of G,~q ⊢ C ∧ ~C, and if that proof contains no applications of generalization to variables that occur free in q, then G ⊢ q." Our proof for Propositional Logic will serve to just validate the general notion of the proof by contradiction.)
Now why is RAA also called an indirect proof? The reason is this: In showing that ~q with p gives a contradiction, we are actually proving that ~q ⇒ ~p, as in the proof by contrapositive.
Let us see why this is so.
The Rule of Conditional Proof says that if in a line of proof we introduce a new premise A and we obtain B, then we can infer (A ⇒ B) and discharge A as premise.
We use the Rule to show that if two statements p and ~q give a contradiction, then ~q ⇒ ~p.
| (1) | ~q | [Premise] |
| (2) | p | [Premise, Conditional Proof] |
| (3) | p,~q ⊢ contradiction | [RAA step] |
| (4) | ~q ⇒ (p ⇒ contradiction) | [Conditional Proof - p is discharged as premise] |
| (5) | p ⇒ contradiction | [1,4 Modus Ponens] |
| (6) | ~p ∨ contradiction | [5, Rule of Material Implication] |
| (7) | ~p | [6, Disjunctive Syllogism] |
| (8) | ~q ⇒ ~p | [1,7] |
In step (4), we use the Rule of Conditional Proof to discharge the introduced premise p and obtain (p ⇒ contradiction) from just ~q.
Step (6) uses the alternate way of writing a Material Implication as a disjunction (see inference rules).
Step (7) uses Disjunctive Syllogism which states that for a disjunction to be true when one disjunct is false, the other has to be true.
Step (8) says that, the introduced premise p having been discharged in step (4) the only remaining assumption is ~q, and since the result is ~p, we have proved that ~q ⇒ ~p.
Thus we have proved the contrapositive of p ⇒ q.
RAA is the most popular method of proof. Here are situations where RAA is usually the weapon of choice:
- If the conclusion is hard to manipulate or understand, but its
negation provides more information or material with which to work.
- If the conclusion is the negation of some other statement.
- If you need to show that there is at most one of something with
a given property.
- If you need to prove the converse of an already proved theorem.
Example:
Theorem. There are no positive integer solutions to the equation x2 - y2 = 1 for positive integers x and y.
Proof. (Proof by Contradiction.) Assume to the contrary that there is a solution (x, y) where x and y are positive integers. If this is the case, we can factor the left side: x2 - y2 = (x-y)(x+y) = 1. Since x and y are integers, it follows that either x-y = 1 and x+y = 1 or x-y = -1 and x+y = -1. In the first case we can add the two equations to get x = 1 and y = 0, contradicting our assumption that x and y are positive. The second case is similar, getting x = -1 and y = 0, again contradicting our assumption. By RAA, there is no solution (x,y) wth the property. QED
(Note: A similar, but more complex, argument will show that xn - yn = 1 has no solutions for positive integers x,y, and n.
Eugene Catalan of Catalan Numbers fame asked if this would be true of the equation xn - ym = 1, where x,y,n, and m are positive integers and n ¹ m.
The question remained unanswered for 150 years until the solution in 2002 by Preda Mihailescu. The answer is there is just one such (n,m,x,y). The solution is: 32 - 23 = 1. )
The difference between RAA and a proof by contrapositive is the following. In the former we start with ~q and p, obtain a contradiction, and deduce that ~q ⇒ ~p. In the latter, we start just with ~q and deduce that ~q ⇒ ~p. Thus we have available two kinds of indirect proofs. RAA is more efficient than proof by contrapositive because in trying to establish ~q ⇒ ~p, RAA uses both ~q and p as premises and thus has more information to work with as compared to proof by contrapositive where we only have the information in ~q to work with.
Since both RAA and proof by contrapositive are indirect proofs, it is clearer to the reader of the proof not to mention RAA as just an indirect proof. While it is not incorrect to call an RAA proof as an indirect proof, if you insist on mentioning 'indirect', it might be better to say 'indirect proof by contradiction' or 'indirect proof by contrapositive' as the case may be, or just 'proof by contradiction' or 'proof by contrapositive.'
Among the great proofs we have presented elsewhere on these page, a few are proofs by contradiction.
Although RAA proofs are often easier and more convenient, a direct proof is preferred for the reason that RAA depends for its validity on the assumption that (C ∧ ~ C) is always false. This assumption is known as the Law of Excluded Middle. That is, a statement C and its negation can not be simultaneously true. Not all logicians accept this.
G.R.T.
Also see: Notes on Methods of Proof
Þ
Great Proofs
ÜBACK
MathPath - "BRIGHT AND EARLY"
Send suggestions to webmaster@mathpath.org
Copyright © 2001-2007 Mathpath
Last updated - January 20, 2007
|
