What is an example of a proof by minimal counterexample?

Consider, for instance, the statment

Every $n\in\mathbb{N}\setminus\{1\}$ can be written as a product of prime numbers (including the case in which there's a single prime number appearing only once).

Suppose otherwise. Then there would be a smallest $n\in\mathbb{N}\setminus\{1\}$ that would not be possible to express as a product of prime numbers. In particular, this implies that $n$ cannot be a prime number. Since $n$ is also different from $1$, it can be written as $a\times b$, where $a,b\in\{2,3,\ldots,n-1\}$. Since $n$ is the smallest counterexample, neither $a$ nor $b$ are counterexamples and therefore both of them can be written as a product of prime numbers. But then $n(=a\times b)$ can be written in such a way too.

Such a proof will often go as follows.

• Assume for contradiction that there is a counterexample to $P$ within some well-ordered set $X$.
• Consider the (certainly non-empty) set of all $X$ which are counterexamples to $P$. This set has a least element (that's what it means to be a well-order), so…
• Consider the smallest counterexample.
• Show that you can find a smaller counterexample.
• Contradiction, so there can't have been any counterexamples to $P$ after all.
• Therefore $P$ is true.

Assume the $\sqrt{2}$ is rational. Then there are whole numbers $a$ and $b$ such that $\sqrt{2}=a/b$ and $a$ is the smallest number with this property but then we find that $a/2, b/2$ are also whole numbers with this property. So there is a smaller example.

I think this must be the example people are the most familiar with and it's a kind of infinite descent even though we often don't refer to it as such.