proof by contradiction

Proof by contradiction proves a claim by showing that denying it leads to nonsense. It is the strategy of a detective who says 'suppose the butler is innocent' and then derives that two clocks must show different times at once — an impossibility — so the butler is guilty after all. You assume the opposite of what you want, follow the logic faithfully, and crash into something that cannot be true. Since correct reasoning never produces a contradiction, your starting assumption must have been wrong.

The shape is always the same. To prove a statement S, you instead assume 'not S' and treat it as true, then deduce consequences step by step using only valid reasoning, until you reach a contradiction — something both true and false at once, like 'a finite set has more elements than itself' or '0 = 1'. Because the deduction was sound but the conclusion is impossible, the only thing that could be at fault is the assumption 'not S'. Therefore S is true. The classic example proves the square root of 2 is irrational: assume it equals a fully reduced fraction p/q, derive that both p and q must be even, contradicting 'fully reduced'.

This technique is everywhere in the theory of computation. Non-regularity proofs assume a language is regular, invoke the pumping lemma, and pump a string out of the language to reach a contradiction. The undecidability of the halting problem assumes a halt-deciding machine exists and feeds it a self-referential input that forces it to disagree with itself. In each case the impossible conclusion is the payoff, and it kills the assumption that started it.