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