Proofs Involving Negations and Conditionals

What do you do when a direct proof gets stuck? You sneak up on the goal from the other side. The two great indirect strategies — proof by contradiction and proof by contrapositive — are the workhorses behind some of the most famous theorems in mathematics, from Euclid's proof that there are infinitely many primes to the irrationality of $\sqrt{2}$. Both rely on a single equivalence from the truth table: $P \Rightarrow Q \equiv \neg Q \Rightarrow \neg P$. Once you can negate fluently and recognise when the negated form is concrete enough to attack, you have unlocked roughly half of all elementary-number-theory proofs.

Proof by contradiction

To prove a statement $P$ by contradiction, assume $\neg P$ and derive a logical impossibility — a statement of the form $R \wedge \neg R$ for some $R$. Since assuming the negation forces a contradiction, the negation cannot hold; therefore $P$ must. The template for proving a conditional $P \Rightarrow Q$ by contradiction:

1. Assume $P$ and $\neg Q$.
2. Use definitions and prior results to derive two statements that contradict each other.
3. Conclude that $\neg Q$ was untenable, so $Q$ holds. $\blacksquare$

Contradiction is the strategy of choice when negating the goal gives you a concrete handle. Euclid assumes only finitely many primes (a negation of an existential) and constructs a number that must have a prime factor outside the finite list — contradiction. Cantor assumes the reals are countable (negation of his goal) and diagonalises — contradiction.

Proof by contrapositive

The contrapositive of $P \Rightarrow Q$ is $\neg Q \Rightarrow \neg P$. The two are logically equivalent (verify with a 4-row truth table). To prove $P \Rightarrow Q$ by contrapositive:

1. State that you will prove the equivalent statement $\neg Q \Rightarrow \neg P$.
2. Assume $\neg Q$.
3. Derive $\neg P$. $\blacksquare$

Contrapositive is the right call when $\neg Q$ unpacks into a concrete object you can compute with. Classic example: to prove "if $n^2$ is even then $n$ is even," the direct route is awkward (what is the structure of $n^2$?), but the contrapositive "if $n$ is odd then $n^2$ is odd" gives you $n = 2k+1$ immediately and the rest is a one-line computation.

Conditional vs contrapositive: the truth-table check

The truth-table widget below confirms the equivalence visually. Type P => Q in one slot and (!Q) => (!P) in the other; the widget parses => as IMPLIES and ! as NOT, and the two output columns will be identical on all four rows. This is why the contrapositive trick is logically airtight: you are not proving "almost the same thing," you are proving the same thing in a different costume.

Negation rules — the indispensable toolkit

Both indirect strategies require fluent negation. Memorise these:

$\neg(P \wedge Q) \equiv \neg P \vee \neg Q$ (De Morgan) $\neg(P \vee Q) \equiv \neg P \wedge \neg Q$ (De Morgan) $\neg(P \Rightarrow Q) \equiv P \wedge \neg Q$ (the only way an implication fails)

Complex statements may need several negation moves before the form is usable. Push the negation as deep as you can — a leading $\neg$ blocking a quantifier is much harder to use than the equivalent statement with negation pushed down to the atomic level.

Choosing between direct, contrapositive, and contradiction

Try direct first. If the hypothesis $P$ gives you concrete material ($n = 2k$, $b = aq$, ...) and the goal $Q$ is reachable by computation, the direct route is the cleanest. Switch to contrapositive when $\neg Q$ is more concrete than $P$ — especially common when the goal's conclusion involves a negation (irrational, not divisible, not equal). Reach for contradiction when you suspect the assumption of $\neg(\text{goal})$ will collide with a given, a definition, or a basic property like $\gcd$ being well-defined.

Pause and think: You want to prove "if $3n + 7$ is even, then $n$ is odd." Why is the contrapositive (assume $n$ is even, show $3n + 7$ is odd) easier than the direct route? What concrete form does $n$ even give you?

Try it

• For each statement, predict whether contradiction or contrapositive is the cleaner strategy: (a) "$\sqrt{2}$ is irrational." (b) "If $n^2$ is not divisible by 3, then $n$ is not divisible by 3." (c) "There are infinitely many primes."
• Negate — carefully — the statement $\forall \varepsilon > 0, \exists N \in \mathbb{N}, \forall n \geq N, |a_n - L| < \varepsilon$. Push the negation all the way down to the atomic level. (This is the definition of "$a_n$ does not converge to $L$.")
• Spot the flaw: a student "proves by contradiction" that $\sqrt{2}$ is irrational by writing "Assume $\sqrt{2}$ is rational. So $\sqrt{2} = 1.41421...$, which is not a fraction. Contradiction." What is missing?
• Skeleton: write the opening sentence and the contradiction sentence for a proof that "there is no largest integer." Do not fill in the middle.
• Contrapositive drill: write the contrapositive of "if $x \in A \cap B$ then $x \in A$." Is the original true? Is the contrapositive obvious?

A trap to watch for

Beginners frequently confuse the contrapositive $\neg Q \Rightarrow \neg P$ with the converse $Q \Rightarrow P$. They are not equivalent. "If it rains, the ground is wet" has contrapositive "if the ground is not wet, it did not rain" (true and equivalent) but converse "if the ground is wet, it rained" (not equivalent — the sprinkler also wets the ground). When you switch to indirect mode, double-check that you are negating and reversing, not just reversing. Also watch the converse trap inside contradiction proofs: assuming $Q \wedge \neg P$ (the negation of the converse) is not the same as assuming $\neg(P \Rightarrow Q) = P \wedge \neg Q$.

What you now know

You can prove conditionals indirectly, by contradiction (assume $\neg(\text{goal})$ and derive nonsense) or by contrapositive (replace $P \Rightarrow Q$ with the equivalent $\neg Q \Rightarrow \neg P$). You can negate compound and quantified statements fluently using De Morgan and the quantifier-flip rules. You know when each strategy is the right tool: contradiction when the negated goal collides with a given, contrapositive when $\neg Q$ unpacks more concretely than $P$. The remaining sections will combine these with quantifier and case-analysis strategies to handle every logical form you will meet in undergraduate proofs.

References

• Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press, §3.2.
• Hammack, R. (2018). Book of Proof (3rd ed.). Open-source textbook, ch. 5 (Contrapositive) and ch. 6 (Contradiction).
• Solow, D. (2014). How to Read and Do Proofs (6th ed.). Wiley, ch. 9 (Contradiction).
• Pierce, B. C. et al. (2018). Software Foundations, Vol. 1: Logical Foundations. Online textbook (Coq), ch. "Logic" (constructive vs classical).
• Wadler, P. (2015). "Propositions as types." Communications of the ACM, 58(12), 75–84 (further reading: the Curry-Howard view of implication and negation).