Principle of Least Counterexample

From ProofWiki

Jump to: navigation, search

Theorem

Suppose $P \left({n}\right)$ is a condition on $n \in \left\{{x \in \Z: x \ge m \in \Z}\right\}$.

Suppose next that: $\neg \left({\forall n \ge m: P \left({n}\right)}\right)$.

(That is, not all $n \ge m$ satisfy $P \left({n}\right)$.)

Then there is a least counterexample, that is a smallest integral value of $n$ for which $\neg P \left({n}\right)$.

Let $S = \left\{{n \in \Z: n \ge m \in \Z: \neg P \left({n}\right)}\right\}$.

That is, $S$ is the set of all elements in $\Z$ not less than $m$ for which the condition is false.

Since:

$\neg \left({\forall n \ge m: P \left({n}\right)}\right)$

it follows that:

$S \ne \varnothing$

Also, $S \subseteq \Z$ and is bounded below (by $m$).

Therefore $S$ has a smallest element, which proves the result.

Some sources refer to the least counterexample as the least rascal.