What is an example of a proof by minimal counterexample?
I was reading about proof by infinite descent, and proof by minimal counterexample. My understanding of it is that we assume the existance of some smallest counterexample $A$ that disproves some proposition $P$, then go onto show that there is some smaller counterexample to this which to me seems like a mix of infinite descent and 'reverse proof by contradiction'.
My question is, how do we know that there might be some counterexample? Furthermore, are there any examples of this?
$\endgroup$ 64 Answers
$\begingroup$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.
$\endgroup$ $\begingroup$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.
$\endgroup$ 5 $\begingroup$A fundamental example in number theory is descent by (Euclidean) division with remainder (or, equivalently, by repeated subtraction), as in the following basic result.
Lemma $\ \ $ Let $\,S\,$ be a nonempty set of positive integers that is closed under subtraction $> 0,\,$ i.e. for all $ \,n,m\in S, \,$ $ \ n > m\ \Rightarrow\ n-m\, \in\, S.\,$ Then the least $ \:\ell\in S\,$ divides every element of $\, S.$
Proof ${\bf\ 1}\,\ $ If not there is a least nonmultiple $ \,n\in S,\,$ contra $ \,n-\ell \in S\,$ is a nonmultiple of $ \,\ell.$
Proof ${\bf\ 2}\, \,\ \ S\,$ closed under subtraction $ \,\Rightarrow\,S\,$ closed under remainder (mod), when it is $\ne 0,$ since mod is simply repeated subtraction, i.e. $ \ a\bmod\ b\, =\, a - k b\, =\, a\!-\!b\!-\!b\!-\cdots\! -\!b.\,$ Therefore $ \,n\in S\,$ $\Rightarrow$ $ \, (n\bmod \ell) = 0,\,$ else it is in $\, S\,$ and smaller than $ \,\ell,\,$ contra minimality of $ \,\ell.$
Remark $\ $ In a nutshell, two applications of induction yield the following inferences
$\begin{eqnarray}\rm S\ closed\ under\ {\bf subtraction} &\:\Rightarrow\:&\rm S\ closed\ under\ {\bf mod} = remainder = repeated\ subtraction \\ &\:\Rightarrow\:&\rm S\ closed\ under\ {\bf gcd} = repeated\ mod\ (Euclid's\ algorithm) \end{eqnarray}$
This yields Bezout's GCD identity: the set $ \,S\,$ of integers of form $ \,a_1\,x_1 + \cdots + a_n x_n,\ x_i\in \mathbb Z,\,$ is closed under subtraction so Lemma $\Rightarrow$ every positive $ \,k\in S\,$ is divisible by $ \,d = $ least positive $ \in S.\,$ Therefore $ \,a_i\in S$ $\,\Rightarrow\,$ $ d\mid a_i,\,$ i.e. $ \,d\,$ is a common divisor of all $ \,a_i,\,$ necessarily the greatest such because $ \ c\mid a_i$ $\Rightarrow$ $ \,c\mid d = a_!\,x_1\!+\!\cdots\!+\!a_nx_n$ $\Rightarrow$ $ \,c\le d.\,$ When interpreted constructively, this yields the extended Euclidean algorithm for the gcd.
$\endgroup$
