TOPIC 1 / 2

Direct, Contrapositive & Contradiction Proofs

Useful preparation: Logic, Sets & Relations

For a long equation, swipe sideways inside its formula box to see every term.

Meaning & notation

A proof handles every allowed object. Track which facts are given, which assumptions are temporary, and why each step follows.

Direct proof: To prove $\displaystyle P \Rightarrow Q$ directly, start with an arbitrary object satisfying P and derive Q through justified implications.
Contrapositive proof: Instead prove ¬Q⇒¬P. This is logically equivalent to $\displaystyle P \Rightarrow Q$ , whereas the converse $\displaystyle Q \Rightarrow P$ is generally not.
Contradiction and counterexample: Contradiction assumes the negation of the target alongside the hypotheses and derives incompatible statements. A counterexample is one allowed object satisfying the hypotheses but violating the conclusion.

Conditions before calculation

Declare the domain before using facts such as “not even means odd,” which is a dichotomy for integers, not arbitrary real numbers.
Division requires a nonzero divisor; taking square roots or reversing inequalities also needs its own stated conditions.
In an indirect proof, identify the temporary assumption and the precise contradiction. Do not assume the desired conclusion without a valid logical framework.

Why the method works

1. Unpack definitions

Replace descriptive words with usable equations. If an integer is divisible by a nonzero integer d, introduce an integer multiplier. The multiplier’s domain is part of the justification.

d\mid n\iff \exists k\in\mathbb Z\text{ such that }n=dk

2. Choose a helpful direction

A parity goal may be easier backwards. To establish that an even square has an even integer root, assume the root is odd and compute its square.

n=2k+1\ \Longrightarrow\ n^2=2(2k^2+2k)+1

3. Close the logical loop

Say which arbitrary choices were handled and how the last statement proves the target. For an equivalence, prove both directions separately; one implication alone is insufficient.

Worked examples

EXAMPLE 1

Prove that if a nonzero integer d divides both integers a and b, then it divides $\displaystyle 3\, a - 2\, b$ .

Because d divides a and b, choose integers r and s with $\displaystyle a = dr$ and $\displaystyle b = ds$ .
Substitute these representations and distribute. This uses the hypotheses rather than the desired conclusion.
$3a-2b=3dr-2ds=d(3r-2s)$
The number $\displaystyle 3\, r - 2\, s$ is an integer because integers are closed under multiplication and subtraction.

Conclusion: The displayed integer multiplier proves d divides $\displaystyle 3\, a - 2\, b$ .

EXAMPLE 2

Prove that there is no smallest positive rational number.

Assume a smallest positive rational r exists. “Smallest” means r is no larger than every positive rational.
The number $\displaystyle \frac{r}{2}$ is rational because rational numbers are closed under division by the nonzero integer 2.
Since r is positive, $\displaystyle 0 < \frac{r}{2} < r$ . This is a positive rational smaller than the supposed smallest one.

Conclusion: The assumed minimum contradicts its defining property, so it cannot exist.

Pitfalls & counterexamples

Tempting claim: A true conclusion means the argument proving it is valid.

Correction: Every implication must follow from available assumptions, even when the final statement happens to be correct.

Test the claim: “All multiples of 4 are even because 12 is even” gives one successful case but does not handle arbitrary multiples.

Check your understanding

What must be assumed first in a contrapositive proof of “if $\displaystyle n^{2}$ is odd, then n is odd” for integer n?

Write a reason before opening the explanation. This reflection is not graded or saved.

Compare your reasoning

Assume n is even.

Negate the conclusion, then show $\displaystyle n^{2}$ is even, which negates the premise.

Connect this idea

Proof methods support induction, limit arguments, and algebraic structure tests. Checking quantifiers and legal operations prevents the same logical errors across these subjects.

Practise this topic →Review concept flashcards

Reference reading

Use these texts to study the underlying definitions and theorems in greater depth. The explanations and examples above are written for Numerive.