Skip to main content

Contradiction, Cases, and Iff Proofs

What This Concept Is​

Three proof forms that share a page because they all appear when a statement resists being handled in a single straight line:

  • Proof by contradiction assumes the negation of the full target claim and derives an impossibility (often "$0 = 1$" or "$P \land \lnot P$"). Since the negation cannot hold, the target must be true.
  • Proof by cases splits the argument into an exhaustive set of mutually manageable branches and proves the conclusion in each branch.
  • Iff (biconditional) proofs establish $P \leftrightarrow Q$ by proving the two implications $P \rightarrow Q$ and $Q \rightarrow P$ separately.

Each of these is a structural choice, not a stylistic one. The theorem's shape (or its difficulty under direct / contrapositive) decides which one fits. Contradiction is most useful when the negation creates a concrete impossible configuration; cases are essential when a definition or universal quantifier naturally splits the universe; iff is mandatory whenever the biconditional appears.

Pedagogically, these three share one discipline: label the branches. A contradiction proof opens with "Assume, for contradiction, …". A cases proof opens with "We consider the following cases…" and each case is announced. An iff proof has two named directions, each with its own proof block. Unlabelled proofs of these kinds are essentially unreadable.

Why It Matters Here​

Many false starts happen because learners try to force a direct or contrapositive proof onto a claim that naturally branches or resists direct construction. These three methods give disciplined alternatives with very different flavours.

Contradiction is historically important: the oldest surviving proof using it is Euclid's proof that there are infinitely many primes, and the oldest surviving irrationality proof (of $\sqrt{2}$) is by contradiction. Cases are how you handle anything involving absolute values, parity, residue classes, or combinatorial sub-conditions. Iff proofs are unavoidable because definitions are usually stated as biconditionals -- "$x$ is invertible iff …" -- and theorems about definitions inherit that shape.

Later in the curriculum, all three compose. Correctness proofs in Semester 2 frequently have a main-case / edge-case split (cases), a termination argument (contradiction via minimal counterexample), and an invariant equivalent to an iff between precondition and postcondition.

Concrete Examples​

Example 1 -- contradiction with a classical sting.

Claim: "$\sqrt{2}$ is irrational."

Proof (by contradiction). Suppose, for contradiction, that $\sqrt{2} = a/b$ in lowest terms for integers $a, b$ with $\gcd(a,b) = 1$. Then $a^2 = 2b^2$, so $a^2$ is even, hence $a$ is even (from the contrapositive in concept 6). Write $a = 2k$; then $4k^2 = 2b^2$, i.e., $b^2 = 2k^2$, so $b^2$ is even, so $b$ is even. But then $2 \mid \gcd(a,b)$, contradicting $\gcd(a,b) = 1$. $\blacksquare$

The move that earned the contradiction: expose the implicit assumption $\gcd(a,b) = 1$ and derive its negation from the arithmetic. Contradiction worked because the negation "$\sqrt{2} = a/b$" gave you the rich object (a ratio) whose properties could be pushed into an impossibility.

Example 2 -- cases driven by a definition.

Claim: "For every integer $n$, $n^2 \ge n$ on the nonnegative integers."

Proof (by cases). Let $n \in \mathbb{Z}_{\ge 0}$.

  • Case 1: $n = 0$. Then $n^2 = 0 \ge 0 = n$.
  • Case 2: $n \ge 1$. Then $n^2 - n = n(n - 1) \ge 0$ since both factors are nonnegative.

These two cases exhaust $\mathbb{Z}_{\ge 0}$, so the inequality holds for every nonnegative integer. $\blacksquare$

The proof's validity depends on the cases being exhaustive. "Cases 0 and 1" would not cover $n = 2$; "cases $n$ even and $n$ odd" would have worked differently.

Example 3 -- iff proof with one direct direction and one contrapositive direction.

Claim: "An integer $n$ is even iff $n^2$ is even."

($\rightarrow$, direct.) Assume $n = 2k$. Then $n^2 = 4k^2 = 2(2k^2)$, which is even.

($\leftarrow$, contrapositive.) Assume $n$ is odd, $n = 2k + 1$. Then $n^2 = 4k^2 + 4k + 1$, which is odd. This establishes the contrapositive "$n$ odd $\Rightarrow n^2$ odd" of the reverse direction.

Both directions hold, so the biconditional is established. $\blacksquare$

Notice the two directions used different techniques. That is normal. The iff structure forces you to consider each direction independently, and each direction is free to pick its own method.

Common Confusion / Misconceptions​

  1. Contradiction used as a reflex. Contradiction feels powerful, so beginners over-apply it. But a "contradiction proof" that just shuffles algebra until a tautology pops out is worse than a direct proof. Discipline: use contradiction when the negated claim yields a concrete impossible configuration (irrationality arguments, no-largest-prime, pigeonhole violations), not when you merely find the direct approach uncomfortable.
  2. Non-exhaustive cases. A case split is a proof only if the cases cover every possibility. Splitting "$n$ is even" vs "$n$ is divisible by 3" leaves $n = 5$ unhandled. Always write a one-liner justifying exhaustiveness.
  3. Half-an-iff-is-an-iff. Proving only the forward direction of $P \leftrightarrow Q$ and labelling the result "iff" is the most common mistake in undergraduate proof writing. Discipline: start the proof with two labels and fill each in; refuse to write the conclusion until both blocks exist.
  4. Confusing contradiction with contrapositive. Contrapositive proves $\lnot Q \rightarrow \lnot P$. Contradiction assumes $P \land \lnot Q$ and derives a contradiction. They sometimes produce similar-looking text, but the logical obligation differs. Mislabelling matters during review.

How To Use It​

For contradiction proofs:

  1. Write the negation of the target carefully (quantifier-aware; see concept 4).
  2. Ask: does the negation describe a concrete impossible configuration?
  3. If yes, assume it; derive the impossibility; conclude.
  4. If no, prefer direct or contrapositive.

For case proofs:

  1. Identify the natural split: parity, sign, emptiness, definition branches, residue classes.
  2. State each case clearly: "Case 1: …".
  3. Prove the conclusion in each case.
  4. Explicitly note the cases are exhaustive.

For iff proofs:

  1. Split into two directions with distinct labels: "($\Rightarrow$)" and "($\Leftarrow$)".
  2. Each direction is its own miniature proof; choose the best method (direct or contrapositive) for each.
  3. After both directions, write "Hence $P \leftrightarrow Q$" to close.

Transfer / Where This Shows Up Later​

  • Semester 2 (algorithms). Minimal-counterexample arguments -- a descendant of contradiction -- are used to prove termination and correctness by reducing to "a smallest violation cannot exist." Algorithm analysis frequently splits into "best-case / average-case / worst-case" case analyses.
  • Semester 5 (concurrency). Liveness arguments often proceed by contradiction: "suppose request $r$ never receives a response; derive that the scheduler must be unfair." Cases split by which thread is currently holding a lock.
  • Semester 6 (distributed systems). Impossibility results (FLP, CAP) are classical proofs by contradiction: assume the property holds, exhibit an adversarial schedule, derive a contradiction. Cases split by message-loss scenarios.
  • Semester 7 (architecture). ADR acceptance criteria are often biconditionals: "we accept this decision iff the fitness functions below pass." Reviewing the ADR means proving both directions informally -- that the decision enforces the criteria, and that the criteria capture the decision.

Check Yourself​

  1. What must be true for a proof by cases to be valid, and how do you audit that property at the end of the proof?
  2. Why is one proved direction never enough for an iff statement, even when the two directions "feel" equivalent?
  3. When should contradiction be preferred over contrapositive? When should it be avoided?
  4. Can a single proof combine cases and contradiction? Sketch a template.
  5. Why does the $\sqrt{2}$ irrationality proof require the assumption $\gcd(a,b) = 1$? What would happen without it?
  6. Is "proof by cases where one case is empty" a legitimate proof? Under what condition?

Mini Drill or Application​

Choose a proof structure for each statement and justify the choice in one sentence. For the ones you mark "by cases," explicitly list the cases you would use:

  1. $|x| = |-x|$ for every real number $x$.
  2. If $n$ is not divisible by 3, then $n^2$ is not divisible by 3.
  3. A real number $x$ satisfies $x^2 = x$ iff $x = 0$ or $x = 1$.
  4. There is no largest integer.
  5. For every integer $n$, $n^2 + n$ is even.
  6. $\sqrt{3}$ is irrational.

Write out at least one of these proofs in full, labelling your strategy choice and the case splits (if any).

Read This Only If Stuck​