8
$\begingroup$

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$
6
  • 3
    $\begingroup$ If there aren't any counterexamples, the theorem is true, and we're done, so it's only the case where there is a counterexample that we have to deal with. This method of proof goes back (at least) to Fermat, who called it "proof by infinite descent." Google that, and you'll find lots of examples. $\endgroup$
    – saulspatz
    Nov 17, 2018 at 19:14
  • $\begingroup$ Related: matheducators.stackexchange.com/questions/10021/… $\endgroup$ Nov 17, 2018 at 19:25
  • 1
    $\begingroup$ Any uneven natural number is prime. Counterexample 9 = 3*3. $\endgroup$
    – Uwe
    Nov 17, 2018 at 21:52
  • 3
    $\begingroup$ (If I understand correctly) "proof by minimal counterexample" proves that a minimal counterexample does not exist (wikipedia), and the 2 comments above are not correct. $\endgroup$
    – user202729
    Nov 18, 2018 at 16:23
  • 1
    $\begingroup$ @forest Proof by minimal counter-example is used to prove theorems true as opposed to the examples both of you gave, which were just examples of disprove by counterexample, which I am familiar with. $\endgroup$ Nov 19, 2018 at 22:54

4 Answers 4

26
$\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$
15
$\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.
$\endgroup$
10
$\begingroup$

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
  • 1
    $\begingroup$ In this proof how do we know that $a/2$, $b/2$ are also whole numbers? (I'm probably missing something obvious.) $\endgroup$
    – LarsH
    Nov 18, 2018 at 0:50
  • 1
    $\begingroup$ It isn't obvious but it is infamous. I can't find it for you now because I am out to dinner. But you can find by looking up the classic proof regarding the irrationality of square root of 2. Its in Bertrand Russell's history of western philosophy... $\endgroup$
    – Mason
    Nov 18, 2018 at 0:57
  • 3
    $\begingroup$ @LarsH ny squaring the equation and wiggling it a bit you can prove that a is even, and then that b is also even. $\endgroup$
    – Dan M.
    Nov 18, 2018 at 2:29
  • $\begingroup$ Here are the details $\endgroup$
    – Mason
    Nov 18, 2018 at 2:38
  • 1
    $\begingroup$ @LarsH We have $2 = a^2/b^2$ hence $2b^2 = a^2$ from which: $a^2$ is even, hence $a$ is even, hence $a^2$ is a multiple of 4, hence $b^2=a^2/2$ is even, hence $b$ is even. So, both $a,b$ are even. $\endgroup$
    – chi
    Nov 18, 2018 at 11:11
1
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.