Principle of Least Counterexample
Jump to navigation
Jump to search
Theorem
Let $\map P n$ be a condition on $n \in \set {x \in \Z: x \ge m \in \Z}$.
Suppose that:
- $\neg \paren {\forall n \ge m: \map P n}$
(That is, not all $n \ge m$ satisfy $\map P n$.)
Then there exists a least counterexample, that is a smallest integral value of $n$ for which $\neg \map P n$.
Proof
Let $S = \set {n \in \Z: n \ge m \in \Z: \neg \map P n}$.
That is, $S$ is the set of all elements of $\Z$ not less than $m$ for which the condition is false.
Since:
- $\neg \paren {\forall n \ge m: \map P n}$
it follows that:
- $S \ne \O$
Also, $S \subseteq \Z$ and is bounded below (by $m$).
Therefore $S$ has a smallest element, which proves the result.
Also known as
Some sources refer to the least counterexample as the least rascal.
Sources
- 1978: Thomas A. Whitelaw: An Introduction to Abstract Algebra ... (previous) ... (next): $\S 10.3$: The well-ordering principle