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. Clear prose or a chain of justified equivalences can also expose these obligations.

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 to the module project

Use this concept to state, justify or challenge one claim in the workflow project. Name the mathematical model and the execution assumptions separately; software behavior is not established by an analogy alone.

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

Use the bounded reading guide to locate this lesson's topic in MCS or Rosen. These links open book indexes. Find the named topic in your edition, read one relevant explanation, then reconstruct the argument with the book closed.

Exhaustiveness, overlap and both directions

Cases must cover the hypotheses; they need not be disjoint. For instance, the cases x≤0 and x≥0 overlap at zero but cover all reals. Proving a target in both cases is valid. Cases “positive” and “negative” omit zero unless a nonzero hypothesis excludes it.

An iff proof owes both implications, but two separately labeled paragraphs are one presentation option. A chain of genuine equivalences can establish both directions at once. Check every arrow: a chain containing a merely necessary condition is not automatically reversible.

In contradiction, negate the whole claim. The negation of “every input has an output” is one input with no output, not “no input has an output.” Transfer attempt: prove the parity equivalence in A2 after practice, then explain which hypotheses each of your cases covers.

Use Practice Solutions and Feedback after your attempt, and Proof and Model Contracts to audit assumptions.