# Principle of Least Counterexample

Jump to navigation
Jump to search

## Theorem

Suppose $P \paren n$ is a condition on $n \in \set {x \in \Z: x \ge m \in \Z}$.

Suppose next that: $\neg \paren {\forall n \ge m: P \paren n}$.

(That is, not all $n \ge m$ satisfy $P \paren n$.)

Then there is a **least counterexample**, that is a smallest integral value of $n$ for which $\neg P \paren n$.

## Proof

Let $S = \set {n \in \Z: n \ge m \in \Z: \neg P \paren n}$.

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

Since:

- $\neg \paren {\forall n \ge m: P \paren 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