Skip to main content

Contradiction and Invariants Prove That Something Cannot Happen

This generated surface maps a learner-facing curriculum unit to its canonical source routes.

Curriculum surface​

  • Open learner-facing unit
  • Curriculum path: content/curriculum/foundations/semester-01-math-foundations/module-05-problem-solving/concepts/cluster-03-structural-reasoning-and-construction/08-contradiction-and-invariants-prove-that-something-cannot-happen-primary.md
  • App: foundations
  • Semester: semester-01-math-foundations
  • Module: module-05-problem-solving
  • Unit kind: concept
  • Curation level: generated_default

Learning objectives​

  • Explain Contradiction and Invariants Prove That Something Cannot Happen in the language of the current curriculum, not just the source book.
  • Apply Contradiction and Invariants Prove That Something Cannot Happen to one concrete learner task or example inside this semester.
  • Use elementary-number-theory, how-to-solve-it-by-computers, mathematics-for-computer-science as a selective source of truth when the learner-facing explanation is not enough.

Prerequisites​

  • The earlier concept pages and practice tasks in the current module.

Source books​

  • elementary-number-theory
  • how-to-solve-it-by-computers
  • mathematics-for-computer-science

Source routes​

Elementary Number Theory​

How To Solve It By Computers​

  • /books/how-to-solve-it-by-computers/chapter-01-getting-started-on-a-problem via `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​

  • [Dromey: 1.5 Program verification, Dromey: 1.2.6 General problem-solving strategies, Dromey: 1.5.5 Verification of program segments with branches, Dromey: 1.5.8 Proof of termination`

Mathematics For Computer Science​

Supporting curriculum routes​

No supporting curriculum routes linked yet.

External enrichment​

No curated enrichment resources yet.

AI companion modes​

  • Explain simply
  • Socratic tutor
  • Quiz me
  • Challenge my understanding
  • Diagnose my confusion
  • Generate extra practice
  • Revision mode
  • Connect forward / backward

Source-of-truth note​

This teaching unit is learner-facing guidance assembled from multiple canonical book routes. Use the listed source books as the primary conceptual spine for Contradiction and Invariants Prove That Something Cannot Happen, and treat outside material as supporting enrichment only.