Skip to main content

Contradiction and Invariants Prove That Something Cannot Happen

What This Concept Is​

Proof by contradiction assumes the negation of the claim, derives an impossibility, and concludes the original claim must hold. It is powerful when the claim is universal ("no $x$ satisfies ...") or non-constructive ("there must exist some ..." without needing to build the witness).

Invariants are quantities or properties preserved across every legal move of a process. They are used to prove what cannot happen: if a quantity never changes parity, and the goal requires a parity change, the goal is unreachable.

Both are non-constructive in spirit: they prove things without showing you the object. That makes them powerful and subtle. A constructive proof hands you the object; a contradiction proof merely tells you the object exists (or does not) and leaves the search to you.

Distinguish two near-moves that this concept competes with:

  • Construction (next concept) builds the witness. Use it when you need the object, not just its existence.
  • Direct proof derives the claim forward from the hypotheses. Use it when the claim is "some structure exists" and the structure is easy to produce.

Use contradiction when (a) the claim is an impossibility (no tiling, no algorithm, no solution), or (b) the direct derivation is blocked by a case explosion but the negation quickly produces an absurdity. Use invariants when the process has a state and legal moves, and you want to prove some state is unreachable.

The two heuristics often combine: an invariant argument is a short contradiction proof in disguise. "Assume the goal is reachable; then the invariant would change; but the invariant is preserved by every move; contradiction."

Why It Matters Here​

Contradiction and invariants are the go-to tools when:

  • the claim is "there is no ..." (no infinite descent, no perpetual motion, no bijection)
  • the state space is huge but a single preserved quantity rules out entire regions
  • constructive proofs are infeasible or unknown
  • you need a quick impossibility argument before investing in a full construction

In CS specifically:

  • loop invariants prove iterative algorithm correctness (formal treatment in Semester 2)
  • reachability arguments in graph algorithms
  • impossibility proofs in distributed systems (FLP impossibility, CAP theorem)
  • protocol correctness via safety properties (the system never reaches a bad state)
  • type soundness proofs (progress + preservation -- preservation is itself an invariant)
  • complexity lower bounds (adversary arguments are contradiction-shaped)

Forward pipeline: Semester 2 (loop invariants in algorithmic correctness), Semester 4 (debugging impossible-looking bugs by disproving assumed invariants), Semester 5 (protocol safety proofs), Semester 6 (distributed-systems impossibility results), Semester 7 (architectural constraints framed as system-level invariants).

Concrete Examples​

Example 1 -- $\sqrt{2}$ is irrational (classical contradiction)​

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

Assume the negation: $\sqrt{2} = p/q$ with $\gcd(p, q) = 1$. Then $p^2 = 2q^2$, so $p^2$ is even, so $p$ is even (since the square of an odd is odd). Write $p = 2k$; then $4k^2 = 2q^2$, so $q^2 = 2k^2$, so $q^2$ is even, so $q$ is even.

But then both $p$ and $q$ are even, so $\gcd(p, q) \geq 2$, contradicting our assumption $\gcd(p, q) = 1$. Therefore no such rational representation exists; $\sqrt{2}$ is irrational. $\blacksquare$

The proof constructs nothing. It rules out a possibility by deriving an absurdity from the assumption that the possibility holds.

Example 2 -- the mutilated chessboard (invariant)​

Claim: An $8 \times 8$ chessboard with two opposite corners removed cannot be tiled by $2 \times 1$ dominoes.

Colour the board as a standard chessboard. Key observations:

  • Two opposite corners have the same colour -- say both black. Removing them leaves $32$ white and $30$ black squares.
  • Every $2 \times 1$ domino covers exactly one black and one white square. This is the invariant: every legal move preserves the equality "dominoes placed = black covered = white covered".
  • A full tiling would place $31$ dominoes, covering $31$ black and $31$ white squares.
  • But only $30$ black squares remain. Impossible.

The invariant (dominoes cover equal colours) plus the gap (30 vs 32) delivers the impossibility. No enumeration of tilings required.

Example 3 -- reaching a target by additions and multiplications (invariant)​

Claim: Starting from $1$, at each step you may either add $2$ or multiply by $3$. You cannot reach $100$.

Track parity. Start: $1$ (odd). "Add 2" preserves parity (odd stays odd, even stays even). "Multiply by 3" preserves parity (odd $\times$ 3 = odd, even $\times$ 3 = even). Invariant: the current number is odd at every step, since we started odd.

$100$ is even. Therefore $100$ is unreachable. $\blacksquare$

Single-line invariant kills an otherwise large search space.

Common Confusion / Misconceptions​

Contradiction ≠ proof by negation. Proof by negation proves $\lnot P$ by assuming $P$ and deriving absurdity. Proof by contradiction proves $P$ by assuming $\lnot P$ and deriving absurdity. In classical logic they are interchangeable; in constructive logic only proof by negation is unconditionally valid.

Spurious contradictions. A contradiction proof that derives an unrelated error on the side is still invalid. The contradiction must follow from the assumed negation, not from a computation mistake downstream.

"Invariants hold most of the time". Invariants must be preserved by every legal move, not most. One move that breaks the invariant destroys the argument. Learners often verify preservation for a "representative" move and miss a special case.

Contradiction as fallback. Treating contradiction as a generic fallback for "I couldn't solve it constructively." Contradiction is a tool for specific problem shapes (impossibility claims, universal claims). Using it on constructive problems produces unwieldy, indirect proofs.

How To Use It​

Contradiction protocol:

  1. State the claim $P$ precisely.
  2. Write "assume, for contradiction, that $\lnot P$."
  3. Derive consequences by valid logical steps.
  4. Reach a contradiction (with a premise, a theorem, or a downstream consequence of your own).
  5. Conclude $P$.
  6. Look back: would a direct proof have been shorter? (It often is.)

Invariant protocol:

  1. Describe the state space and the legal moves.
  2. Hypothesise a quantity or property preserved by every move. Common candidates: parity, sum modulo $k$, colouring, a potential function.
  3. Verify preservation for every move type, not just representative ones.
  4. Compute the invariant value on the starting and goal states.
  5. If they differ, the goal is unreachable. If they agree, the invariant does not rule out reachability -- try another invariant or switch to construction.
  6. Write the invariant explicitly in the final proof; do not bury it in prose.

Transfer / Where This Shows Up Later​

  • Semester 2 (algorithm correctness). Loop invariants are the daily bread of iterative-algorithm proofs. "The prefix $a[0..i)$ is sorted" is an invariant that survives through insertion sort.
  • Semester 2 (lower bounds). Adversary arguments prove "no comparison sort can beat $\Omega(n \log n)$" by contradicting the existence of a faster algorithm.
  • Semester 3 (refactoring). Preserving behaviour is preserving an invariant: observable semantics. The refactor is legal only if every step preserves the invariant.
  • Semester 4 (debugging). "The bug should be impossible" means an assumed invariant is violated. Locating the violation is the debugging.
  • Semester 5 (protocol design). Safety properties (the system never enters a bad state) are invariants. Liveness properties are eventual reachability.
  • Semester 6 (distributed systems). FLP impossibility, CAP, and the two-generals problem are all contradiction-shaped.
  • Semester 7 (architecture). "We never call billing synchronously from orders" is an architectural invariant; enforcement is a fitness function.

Check Yourself​

  1. What is the difference between proof by contradiction and proof by negation? When does it matter?
  2. Why must an invariant be preserved by every legal move, not just most? Give a puzzle where skipping one move type breaks the argument.
  3. Give an invariant argument from graph theory (Module 2) that rules out reachability.
  4. For the mutilated chessboard, what if we removed two adjacent corners instead of opposite ones? Does the invariant argument still apply? Why or why not?
  5. Name a CS impossibility result and state it as "assume the opposite; derive absurdity."

Mini Drill or Application​

Drill A. Problem: Starting with the number $1$, at each step you may either add $2$ or multiply by $3$. Can you reach $100$? Find an invariant, use it to conclude. Write the full argument including the preservation check for both move types.

Drill B. Prove by contradiction that there are infinitely many primes. Assume finitely many $p_1, \dots, p_k$; consider $N = p_1 p_2 \cdots p_k + 1$; derive a contradiction from the claim that $N$ has no prime factor in the list.

Drill C (unseen). Problem: A $4 \times 4$ grid has 16 light bulbs, initially all off. Toggling one bulb also toggles its up/down/left/right neighbours. Can you reach the state where exactly one corner bulb is on and the rest are off? Find an invariant (hint: sum of bulb states, mod something appropriate) and use it.

Read This Only If Stuck​