Sunday, September 20, 2015

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?


Answer



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.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...