Discrete Math · Undergraduate
Proof Techniques: Direct, Contrapositive and Contradiction
Quick answer
A proof is a chain of steps, each justified, from what is known to what is claimed. A direct proof of "if p, then q" assumes p and works forward to q, usually by unpacking definitions. Proving the contrapositive, "if not q, then not p", is equivalent and sometimes simpler. A proof by contradiction assumes the statement is false and derives something impossible. These three methods prove that the sum of two odd numbers is even, that √2 is irrational, and that there are infinitely many primes.
What you'll learn
- Write a direct proof by unpacking definitions
- Prove a conditional through its contrapositive
- Write a proof by contradiction
- Disprove a general claim with a counterexample
What counts as a proof
A proof shows that a statement is true in every case, by a chain of steps each of which follows from definitions, earlier results or plain algebra. Checking examples is not enough: is prime for , but not for , where it equals . A proof covers every case at once.
Most statements have the form “if , then ”. Three methods handle them.
Direct proof
Assume . Unpack the definitions, and work forward until appears.
Proof by contrapositive
The contrapositive of is , and the two are equivalent. Sometimes is the better starting point.
Why contradiction works
A statement is either true or false. If assuming it is false leads to an impossibility, such as a number that is both even and odd, then “false” was not an option. So it must be true. Contradiction is most useful for statements of the form “there is no…” or “this is not…”, where a direct approach has nothing to build on.
Counterexamples
To show “for all…” is false, one counterexample is enough. “Every prime is odd” is false because is prime and even.
Common mistakes
Practice problems
-
Prove that the sum of two even numbers is even.
Answer
, which is even.
Full solution
Write the numbers as and for integers and ; their sum is times the integer .
-
Prove that the product of two odd numbers is odd.
Answer
.
Full solution
Expand: , which is times an integer plus .
-
Write the contrapositive of “if is odd, then is odd”, and prove it.
Answer
“If is even, then is even”: .
Full solution
Negate both parts and swap them. An even is , and its square is twice an integer.
-
Find a counterexample to ” is prime for every whole number ”.
Answer
gives .
Full solution
. ( also works: .)
-
Find a counterexample to “if , then ”.
Answer
,
Full solution
Both squares are , but .
-
Which method would you use to prove “there is no largest even number”? Sketch the proof.
Answer
Contradiction: if were the largest even number, would be even and larger.
Full solution
Assuming a largest one exists gives a concrete to work with, and breaks the assumption.
-
In Example 4, is always prime? Try the primes .
Answer
No: .
Full solution
The proof only needs to have a prime factor outside the list. Here the new primes and appear.
-
A student proves “if is even, then is even” and claims to have shown “if is even, then is even”. What is wrong?
Answer
That proves the converse, a different statement.
Full solution
The statement needs its own proof, such as the contrapositive argument of Example 2.
Frequently asked questions
What is a direct proof?
A proof of "if p, then q" that assumes p and reasons step by step to q, typically by writing out the definitions involved.
When should you prove the contrapositive instead?
When the conclusion's negation gives you something concrete to work with. To show "if n² is even then n is even", it is easier to assume n is odd and show n² is odd.
What is a proof by contradiction?
Assume the statement is false, then reason to something impossible, such as a number that is both even and odd. The assumption must have been wrong, so the statement is true.
How do you disprove a statement?
For a claim about all cases, one counterexample is enough. The claim "every prime is odd" falls to the single example 2.
Do examples prove a general statement?
No. Checking cases can suggest a pattern but cannot prove it holds for every case; a proof must cover all of them at once.