Skip to main content

Direct Proof and Contrapositive

What This Concept Is​

A direct proof of $P \rightarrow Q$ starts by assuming $P$ and derives $Q$ through a chain of definitions, previously proven facts, and algebra. It is the proof method that most resembles linear, forward reasoning and it is usually the first one to try.

A contrapositive proof of $P \rightarrow Q$ proves the equivalent statement $\lnot Q \rightarrow \lnot P$ instead. The validity rests on the truth-table equivalence $P \rightarrow Q \equiv \lnot Q \rightarrow \lnot P$ -- established in the previous cluster -- so a contrapositive proof is not a sleight of hand; it is a proof of a logically equivalent theorem.

Both methods are valid in classical logic. The real question is which method exposes the structure of the theorem most clearly. Sometimes the hypothesis $P$ gives you a concrete representation to work with (e.g., "$n = 2k+1$") and direct proof is natural. Sometimes the negated conclusion $\lnot Q$ gives the clean representation and contrapositive wins. Neither is strictly more powerful.

A subtle point beginners miss: a "direct proof" can still contain local reverse reasoning inside it (e.g., proving an equality by reducing both sides to a common form). The name refers to the outer direction -- from hypothesis to conclusion -- not to every move inside.

A compact cheat-sheet for the two methods:

DirectContrapositive
Opening assumption$P$$\lnot Q$
Targetderive $Q$derive $\lnot P$
When preferred$P$ has a concrete representation$\lnot Q$ has a concrete representation
Typical exampleodd + odd = even$n^2$ even $\Rightarrow n$ even

Both methods rest on classical logic. In constructive (intuitionistic) logic, the two are not interchangeable; the equivalence $P \rightarrow Q \equiv \lnot Q \rightarrow \lnot P$ fails in general. For this course we work in classical logic and both are free.

Why It Matters Here​

This pair appears constantly in proofs about divisibility, parity, set inclusion, function properties, and any implication-based definition. If you cannot move comfortably between direct and contrapositive, many later arguments stay harder than necessary.

Cluster 3 uses both techniques for proving set identities and function properties (injectivity, surjectivity). Cluster 4 uses them to establish relation properties. Cluster 5 uses contrapositive routinely in the step of an induction whose conclusion is hard to build up to directly. In Semester 2 algorithms, contrapositive is the standard tool for termination arguments: "if the algorithm has not yet halted, then the rank function strictly decreases."

Learning to pick the right one is mostly learning to look at $\lnot Q$ before committing: if $\lnot Q$ gives you a more algebraically concrete object than $P$ does, consider contrapositive.

Concrete Examples​

Example 1 -- direct proof of a simple arithmetic claim.

Claim: "If $a$ and $b$ are odd integers, then $a + b$ is even."

Proof (direct). Assume $a$ and $b$ are odd. Write $a = 2j + 1$ and $b = 2k + 1$ for integers $j, k$. Then $a + b = 2j + 2k + 2 = 2(j + k + 1)$, which is even. $\blacksquare$

The hypothesis gave usable representations; forward algebra landed the conclusion. No cleverness required.

Example 2 -- contrapositive when conclusion is awkward.

Claim: "If $n^2$ is even, then $n$ is even."

Direct proof is possible but requires a case analysis or number-theoretic lemma. Contrapositive is cleaner:

Proof (contrapositive). Suppose $n$ is odd; then $n = 2k + 1$ for some integer $k$. Compute $n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$, which is odd. This establishes "$n$ odd $\Rightarrow n^2$ odd," which is the contrapositive of the claim. $\blacksquare$

The move worked because the negated conclusion ("$n$ is odd") gave a concrete representation ($n = 2k + 1$), while the original hypothesis ("$n^2$ is even") gave only an indirect constraint.

Example 3 -- contrapositive on a set inclusion.

Claim: "If $A \not\subseteq B$, then there exists $x \in A$ with $x \notin B$."

This is the contrapositive of the definition of $A \subseteq B$. The "proof" is essentially just unpacking the definition, but it makes a pedagogical point: many theorems that look substantive are in fact one contrapositive rewrite away from a definitional triviality. Looking for that simplification is a fast win.

Example 4 -- mixed local reasoning inside a direct proof.

Claim: "If $f$ is injective, then $f(A \cap B) \subseteq f(A) \cap f(B)$."

Proof (direct). Let $y \in f(A \cap B)$. Then there exists $x \in A \cap B$ with $f(x) = y$. Since $x \in A$, $y = f(x) \in f(A)$; since $x \in B$, $y \in f(B)$. Hence $y \in f(A) \cap f(B)$. $\blacksquare$

Interestingly, this direction does not use injectivity at all -- it holds for any function. The injectivity is required for the reverse inclusion (see Cluster 3, concept 12). The example reinforces a discipline: a direct proof should use every hypothesis it cites; if it does not, either the proof is wrong or the hypothesis is superfluous.

Common Confusion / Misconceptions​

  1. "Contrapositive and contradiction are the same thing." They are not. Contrapositive proves the equivalent implication $\lnot Q \rightarrow \lnot P$ directly. Contradiction assumes the whole negated statement $P \land \lnot Q$ and derives an impossibility. They overlap in practice, but the logical structure differs, and so do the writing conventions.
  2. "Always start direct; fall back to contrapositive only if direct fails." Wrong heuristic. Look at both $P$ and $\lnot Q$ at the start. If $\lnot Q$ is the algebraically concrete one, start there.
  3. "The initial assumption is obvious; I can skip stating it." Proofs that do not explicitly announce the assumption ("Assume $P$" or "Suppose $\lnot Q$") leave the reader to reconstruct the proof method. That is a readability bug, not a style preference.
  4. "The contrapositive of an iff is the same iff." The contrapositive is a statement about one direction. The contrapositive of $P \rightarrow Q$ is $\lnot Q \rightarrow \lnot P$; the contrapositive of the reverse direction $Q \rightarrow P$ is $\lnot P \rightarrow \lnot Q$. These are different one-direction proofs and a biconditional still needs both.

How To Use It​

An operational checklist for picking and executing the method:

  1. Write the target as $P \rightarrow Q$. Make hypothesis and conclusion explicit.
  2. Look at $P$. Is there a clean representation or definition to unpack?
  3. Look at $\lnot Q$. Is there a cleaner representation there?
  4. Pick the side with the concrete representation. If $P$, plan direct. If $\lnot Q$, plan contrapositive.
  5. Open the proof with the matching assumption. "Assume $P$." or "Suppose $\lnot Q$, i.e., …".
  6. Chain definitions and known facts until you reach the target conclusion. Keep each step cited.
  7. Close with the matching verdict. "Hence $Q$, as required." or "Hence $\lnot P$, which proves the contrapositive and therefore the original implication."

Transfer / Where This Shows Up Later​

  • Semester 2 (algorithms). A termination proof by contrapositive reads: "if the loop has not terminated, then we are in a state where the measure has strictly decreased." Contrapositive lets you avoid enumerating terminating cases; you argue about non-termination instead.
  • Semester 5 (concurrency). "If a thread holds the lock, then no other thread is in the critical section" is often easier to prove by contrapositive: "if two threads are both in the critical section, some lock invariant has been violated."
  • Semester 6 (distributed systems). Safety properties are implications ("if majority ACK, then committed"); their negations localise the bug. Contrapositive reasoning is the workhorse when debugging protocol counter-examples.
  • Semester 7 (architecture). ADR justifications -- "if we adopt choice X, then quality attribute Y is preserved" -- are reviewed as implications. A skeptical reviewer will read the contrapositive to expose failure modes: "if Y is violated, then we didn't actually adopt X correctly."

Check Yourself​

  1. What assumption begins a direct proof of $P \rightarrow Q$? What assumption begins a contrapositive proof?
  2. When does a contrapositive proof become cleaner than a direct proof? Give two distinguishing features of $P$ vs $\lnot Q$ that tip the choice.
  3. Is a proof that "uses the contrapositive internally" but opens with "assume $P$" a direct proof or a contrapositive proof?
  4. Why must a biconditional proof label each direction explicitly? What goes wrong if you don't?
  5. If a direct proof never invokes the hypothesis $P$, what should you suspect?
  6. Can you always convert a direct proof into a contrapositive proof of the same theorem? Under what assumption about the underlying logic?

Mini Drill or Application​

Write a proof plan (not the full proof) for each statement, deciding between direct and contrapositive. State which method you chose and justify in one sentence based on the relative concreteness of $P$ and $\lnot Q$:

  1. "If $x$ is irrational, then $x + 1$ is irrational."
  2. "If $n^2$ is odd, then $n$ is odd."
  3. "If $A \subseteq B$, then $A \cup C \subseteq B \cup C$."
  4. "If $3n + 2$ is odd, then $n$ is odd."
  5. "If $f$ is not injective, then there exist distinct $a, b$ with $f(a) = f(b)$."
  6. "If the product $xy$ is irrational, then at least one of $x, y$ is irrational."

For items 4 and 6, note which strategy is preferred and why: one has a concrete $P$ representation; the other has a concrete $\lnot Q$ representation.

Read This Only If Stuck​

Closing Note​

Direct and contrapositive are the two most-used proof methods in this whole module and the next. They are also the most transferable to code reasoning: the implication $P \rightarrow Q$ becomes a precondition-postcondition pair, and the contrapositive gives the "if the postcondition is not achieved, the precondition was not met" audit path that debugging relies on. Time invested here pays dividends every semester.