Phase 1 - Lesson 1.3

Proof Techniques: Direct, Contrapositive, and Contradiction

The three workhorse proof strategies, when each is the right tool, and how to structure an argument a reader can verify.

⏱ 45 min● Beginner🔗 Prereqs: 1.2

↖ Phase 1 hub

Builds on: 1.2 supplied implication, contrapositive and negation - the raw materials for proofs.
Leads to: Every theorem in analysis, probability and stochastic calculus is proved with these three templates.

Learning Objectives

Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.

Structure a direct proof from hypotheses to conclusion with justified steps.
Convert a stubborn implication into its contrapositive and prove that instead.
Execute a proof by contradiction, identifying the assumption to be refuted.
Choose the appropriate technique for a given statement and justify the choice.

Key Vocabulary

Direct proof: Assume the hypothesis P and derive the conclusion Q by a chain of valid steps.

Proof by contrapositive: Prove ¬Q ⇒ ¬P, which is logically equivalent to P ⇒ Q.

Proof by contradiction: Assume the statement is false, derive a logical impossibility, conclude it must be true.

Counterexample: A single instance that refutes a universal claim; disproves ‘for all’ statements.

Without loss of generality: A justified reduction to a representative case when symmetry makes the others identical.

Lemma: A smaller proved result used as a stepping stone toward a theorem.

Direct proof: the default

A direct proof of \(P\Rightarrow Q\) assumes \(P\) and marches to \(Q\). The craft is in making each step a consequence of a definition, an axiom, or a prior step - never a leap.

Worked Example - Direct: the sum of two even integers is even

Let \(a,b\) be even. By definition \(a=2m,\ b=2n\) for integers \(m,n\).

Then \(a+b=2m+2n=2(m+n)\).

Since \(m+n\) is an integer, \(a+b\) is twice an integer, i.e. even. □

Contrapositive: when the negation is more concrete

If assuming \(P\) gives you little to work with but assuming \(\neg Q\) is concrete, prove \(\neg Q\Rightarrow\neg P\) instead.

Worked Example - Contrapositive: if n² is even then n is even

Direct is awkward. Contrapositive: assume \(n\) is odd, show \(n^2\) is odd.

Odd means \(n=2k+1\), so \(n^2=4k^2+4k+1=2(2k^2+2k)+1\), which is odd.

Having proved the contrapositive, the original follows. □

Contradiction: assume the opposite and break something

To prove a statement \(S\), assume \(\neg S\) and derive an impossibility. The classic:

Worked Example - Contradiction: √2 is irrational

Assume \(\sqrt2=p/q\) in lowest terms (so \(p,q\) share no factor 2).

Then \(p^2=2q^2\), so \(p^2\) is even, hence \(p\) is even (from the previous theorem): write \(p=2r\).

Then \(4r^2=2q^2\Rightarrow q^2=2r^2\), so \(q\) is even too - contradicting ‘lowest terms’.

The assumption was impossible, so \(\sqrt2\) is irrational. □

Situation	Best technique
Hypothesis gives usable structure	Direct
Negation of conclusion is concrete	Contrapositive
Claim asserts non-existence or ‘no such’	Contradiction
Universal claim you suspect is false	Find a counterexample

Interactive: pick the strategy

Predict first: You must prove: ‘if a product of two integers ab is odd, then both a and b are odd’. Which single technique is cleanest, and what do you assume first?

Common Mistakes to Avoid

Circular reasoning: using the conclusion (or something equivalent) as a step in its own proof.
In contradiction proofs, forgetting to state clearly what impossibility you reached.
Trying one example and calling a universal statement ‘proved’; examples motivate, they do not prove ∀.
Invoking ‘without loss of generality’ when the cases are genuinely different.

Quant Practitioner Tips

Write the first and last lines first: ‘Assume P’ and ‘therefore Q’, then fill the gap.
Stuck on a direct proof? Immediately try the contrapositive - it costs nothing.
One counterexample disproves a ‘for all’; to disprove a ‘there exists’ you need a full proof of ‘for all, not’.
Name reusable sub-results as lemmas; clean structure is itself a correctness check.

Practice this in the Euler Lab

Computational problems that exercise exactly this technique. Each opens in the Euler Lab with a Python workbench, a progressive hint ladder, and answer checking. Tier A/B run at full scale in the browser.

Warm-up:
#1 Multiples of 3 or 5 (1%, tier A) #2 Even Fibonacci Numbers (1%, tier A) #7 10 001st Prime (1%, tier A) #20 Factorial Digit Sum (1%, tier A)

Applied:
#293 Pseudo-Fortunate Numbers (16%, tier B) #313 Sliding Game (16%, tier B) #357 Prime Generating Integers (16%, tier B)

Challenge:
#161 Triominoes (41%, tier C) #182 RSA Encryption (41%, tier C)

481 Project Euler problems in total are mapped to this lesson. Open the Euler Lab to filter them all.

Knowledge Check

Q1 Easy

To disprove the universal claim ‘every continuous function is differentiable’, the correct move is:

a proof by contradiction

a proof by contrapositive

exhibit one counterexample such as |x| at 0

a direct proof

Q2 Medium

Proof by contradiction of a statement S proceeds by:

assuming S and deriving S again

assuming ¬S and deriving a logical impossibility

assuming the hypothesis and reaching the conclusion

checking finitely many cases

Q3 Medium

Which statement is most naturally attacked by contrapositive?

√2 is irrational

if n² is odd then n is odd

there are infinitely many primes

the empty set is a subset of every set

Practical Exercise

Prove that for every integer \(n\), \(n^2+n\) is even. Then prove that there is no largest even integer.

▶ Show full solution

Part 1 (direct). \(n^2+n=n(n+1)\) is a product of two consecutive integers; one of them is even, so the product is even.

Part 2 (contradiction). Suppose there were a largest even integer \(N\). Then \(N+2\) is also even and \(N+2\gt N\), contradicting maximality. Hence no largest even integer exists.

After the reveal, answer for yourself: Part 1 avoided a case split by spotting the ‘consecutive integers’ structure. Recognizing structure often replaces brute force.

Lesson Summary

Three templates cover most proofs: direct (assume P, reach Q), contrapositive (prove ¬Q⇒¬P when the negation is concrete), and contradiction (assume the claim false and break something, ideal for non-existence). Universal claims are disproved by a single counterexample. Choosing the right template is half the battle.

Retrieval Practice

Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.

▶ Show retrieval prompts & answers

Q: When should you reach for a contrapositive proof instead of a direct one?
A: When assuming the hypothesis yields little structure but assuming the negation of the conclusion is concrete and workable, since ¬Q⇒¬P is equivalent to P⇒Q.

Q: How do you disprove a ‘for all’ statement, and how does that differ from disproving a ‘there exists’ statement?
A: Disprove ∀ with one counterexample; disprove ∃ by proving the universal negation ‘for all, not’, which requires a full proof.

Completion Checklist

I can explain the core ideas in my own words
I worked the derivations/examples by hand
I completed the interactive workbench(es)
I passed the knowledge check

Confidence / mastery rating

Personal notes

Source References

This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.

Calculus, Vol. I (Tom Apostol, 2nd ed., 1967) foundational - Vol. I, rigor & induction - Standards of rigor and the structure of proofs used throughout the calculus text.
A Mind for Numbers (Barbara Oakley, 2014) foundational - problem-solving - Building proof ‘chunks’ and diffuse-mode incubation when a proof strategy will not come.

← 1.2 Next: 1.4 →