Proof by Contradiction

Why This Matters

Some statements are hard to prove directly. How do you prove that the square root of 2 is irrational? You cannot check every possible fraction. Instead, you use proof by contradiction: assume the opposite is true, then show that this assumption leads to a logical impossibility. Since the assumption caused a contradiction, it must be false, and the original statement must be true.

The contrapositive is a related technique. Instead of proving "if P then Q," you prove the logically equivalent statement "if NOT Q then NOT P." Both approaches let you tackle problems from a different angle when a direct path is not obvious.

A counterexample is the opposite weapon: to disprove a universal claim, you only need one case where it fails. Knowing when to find a counterexample versus when to construct a proof is a critical skill. Contradiction and counterexample together let you both prove true statements and demolish false ones.

Define Terms

Visual Model

Code Example

// Proof by contradiction pattern:
// To prove a claim, assume the opposite and find a contradiction

// Example: Prove there is no largest integer
// Assume: there IS a largest integer, call it max
// Then max + 1 > max, but max + 1 is also an integer
// Contradiction: max was not the largest after all

function proveNoLargestInteger(assumedMax) {
  const bigger = assumedMax + 1;
  console.log(`Assumed max: ${assumedMax}`);
  console.log(`But ${bigger} > ${assumedMax} and is also an integer`);
  console.log("Contradiction! There is no largest integer.");
}
proveNoLargestInteger(1000000);

// Contrapositive: instead of P => Q, prove NOT Q => NOT P
// Claim: if n squared is even, then n is even
// Contrapositive: if n is odd, then n squared is odd
function proveContrapositive(n) {
  if (n % 2 !== 0) { // n is odd
    const nSquared = n * n;
    console.log(`n=${n} is odd, n^2=${nSquared} is ${nSquared % 2 !== 0 ? "odd" : "even"}`);
    return nSquared % 2 !== 0; // should always be true
  }
  return true; // n is even, not relevant to contrapositive
}

for (let i = 1; i <= 9; i += 2) {
  proveContrapositive(i);
}

// Finding counterexamples to disprove false claims
function findCounterexample(claim, domain) {
  for (const x of domain) {
    if (!claim(x)) {
      console.log(`Counterexample found: ${x}`);
      return x;
    }
  }
  console.log("No counterexample found in domain");
  return null;
}

// False claim: all prime numbers are odd
function isPrime(n) {
  if (n < 2) return false;
  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (n % i === 0) return false;
  }
  return true;
}

const claim = (n) => !isPrime(n) || n % 2 !== 0; // if prime, then odd
findCounterexample(claim, [1,2,3,4,5,6,7,8,9,10]); // Counterexample: 2

Interactive Experiment

Try these exercises:

• Use the counterexample finder to disprove: "all perfect squares are even." What is the smallest counterexample?
• Verify the contrapositive of "if n is divisible by 4, then n is even" by testing all odd numbers from 1 to 20 and confirming none are divisible by 4.
• Write a proof-by-contradiction argument (in comments) that the square root of 2 is irrational, then verify computationally that no fraction p/q with q up to 1000 equals sqrt(2) exactly.
• Disprove: "for all integers n, n squared exceeds n." Find the counterexamples.
• Write a function that takes a claim function and a range, and returns either "no counterexample found" or the first counterexample it discovers.

Quick Quiz

Coding Challenge

Real-World Usage

Contradiction and counterexample techniques appear throughout engineering:

• Security auditing: Penetration testing is counterexample finding. You try to disprove the claim "this system is secure" by finding one exploit.
• Bug reports: A bug is a counterexample to the claim "this software works correctly." One failing test case disproves correctness.
• Impossibility results: Proofs by contradiction show fundamental limits: the halting problem cannot be solved, certain problems cannot be computed in polynomial time.
• Constraint solving: SAT solvers and SMT solvers work by assuming truth assignments and deriving contradictions to prune the search space.
• Property-based testing: Tools like QuickCheck automatically generate inputs to find counterexamples to programmer-specified properties.

Connections