Contents
Proving
conditional assertions: The direct method
Proving
conditional assertions: The contrapositive method
Proving conditional assertions: The direct method
Method:
To prove “If P, then Q” assume P is true and deduce that Q must be true as well. This form of proof is called
the direct method.
Note: In the process of proving Q, you would expect to use other facts that you know as well as the assumption that P is true.
Easy example
Remember that the integer n is even if there is an integer m
for which n = 2m.
Theorem
If n
is even, then is even.
Narrative proof by the direct method
Suppose that n is even. Then by
definition of “even” there is an integer m
for which n = 2m. Then .
is an integer because m is an integer, so by definition of “even”,
is even.
Remarks
¨ In this proof,
P is “n is even” and Q is “ is even”.
¨ The author does not tell you that the proof of “If P, then Q” is by the direct method. But you can detect the pattern when the proof starts with “Suppose that n is even”, in other words, “Suppose P”.
¨ A proof using the direct method is called a direct proof. You undoubtedly already knew how to give a direct proof. This article is intended to raise your knowledge to a conscious level (if it isn’t already there).
¨ This is an example of a proof by rewriting according to the definition of the words in the theorem.
¨ The name “direct method” is not common usage. I believe it originated with Daniel Solow’s book How to Read and Do Proofs.
In a more complicated situation, you might have to prove
If P
then ,
If then
,
…
If then Q
using a sequence of deductions.
Normally, although your final proof would be
written up in that order, you
would not think up the proof by thinking up ,
,
… in order. What
usually happens
is that you think of statements which imply Q, statements which imply them (backing
up), and at the same time you think of statements which P implies, statements
which they
imply (going forward), and so on, until your chain meets in the middle (if you
are lucky).
Thinking up a proof is a CREATIVE ACT
not a mechanical one of grinding out conclusions from hypotheses
Proving conditional assertions: The contrapositive method
Method: To prove “If P, then Q” assume Q is false and deduce that P must be false as well.
This method is the Direct Method applied to “If not Q, then not P.” That is the contrapositive of “If P, then Q” but proving the contrapositive of P is the same thing as proving P, since a conditional sentence and its contrapositive always have the same truth value.
Example
Theorem
If is even, then n is even.
Narrative proof by the contrapositive method
Suppose n
is odd. Then for some integer k, n
= 2k + 1. Then . Thus
for some integer h, so
is odd.
QED.
Remarks
¨ The proof of the contrapositive proceeds like any
direct-method proof, by assuming the hypothesis ( n is odd) and
deducing the conclusion ( is odd)
but the hypothesis and conclusion are those of the contrapositive of the
theorem as stated.
¨ If you didn't think of proving the contrapositive, you
might be dumbfounded when you saw that a proof of a theorem which says "if
is even then n is even” begins
with, "Let n be odd.” (See translation
problem and walking
blindfolded).
But that is a clue …
If a theorem has the form “If P then Q” and the proof begins with “Assume Q is false…”, that is a CLUE that the form of the proof is by contrapositive!
Proof by Contradiction
Method:
To prove that an assertion P is false, prove that “If P then Q” is true and that Q is false. This method is called proof by contradiction or reductio ad absurdum, sometimes abbreviated r.a.a.
I will give an example proof and then talk about why it works.
Example
Theorem
The number is not rational.
Typical narrative proof
Let where m and
n are positive integers. Then by definition of log,
,
so
. This is impossible because every positive
power of 10 is even and every positive power of 3 is odd. QED.
Analysis of the proof
In this proof, P is the statement “ is rational” and Q is the statement “An even integer cannot equal an odd
integer.”
¨ The proof proceeds by contradiction, which means it must prove “If P, then Q” .
¨ It proves “If P, then Q” by the direct method.
¨ Therefore
it starts with the unstated
assumption that is rational.
¨ By
rewriting according to the
definition of “rational”, we get where m and
n are positive integers. This is the first actual statement in the proof.
¨ Then
it uses the definition
of log to conclude .
¨ Using
the algebra of exponents,
it concludes that (a certain even integer equals a certain odd
integer)..
¨ The statement “Every positive power of 10 is even and every positive power of 3 is odd” is then made without proof (regarded as common knowledge)..
¨ It claims a contradiction, without stating the fact Q (also regarded as common knowledge) that it contradicts.
The proof does not say it is a proof by contradiction,
and neither P nor Q is stated explicitly in the proof.
This is very common in narrative proofs.
GET OVER IT.
Remarks
¨ This analysis of the proof is an example of the translation problem.
¨ Note that a direct proof is impossible (note)
¨ Authors sometimes tell you they are doing a proof by contradiction, and sometimes don’t.
¨ In practice it frequently happens that Q is obviously false so that the work goes into proving “If P then Q.” Thus a proof that P is false might begin, "Suppose P is true..."! That is a clue that you are reading a proof by contradiction.
Proving equivalences
Proof by cases.
Also called proof by exhaustion. For now, see what Wikipedia says.
Uniqueness theorems
Appendix
Impossibility of finding a direct proof that 
You can’t try every pair of integers m and n to see that because there are an infinite number of pairs.
In any case there
are pairs m and n that will give you the first googol digits of correctly.
(Why?) You
can’t calculate the first googol digits, so you could not carry out the calculation for such a
pair in your lifetime.
Still, you know there
is no rational number that gives to infinite precision because we have proved there is
no such number, by contradiction. return