Following is from MIT OCS Mathematics for Computer Science book
Every positive integer greater than one can be factored as a product of primes.
The proof is by well ordering. Let $C$ be the set of all integers greater than one that cannot be factored as a product of primes. We assume $C$ is not empty and derive a contradiction.If $C$ is not empty, there is a least element, $n \in C$, by well ordering. Then $n$ can’t be prime, because a prime by itself is considered a (length one) product of primes and no such products are in C.So $n$ must be a product of two integers $a$ and $b$ where $1<a,b<n$. Since $a$ and $b$ are smaller than the smallest element in $C$, we know that $a,b \notin C$. In otherwords, $a$ can be written as a product of primes $p_1p_2\cdots p_k$
Here is where I have a conceptual problem with the example – we have not yet proven that we can factor a number into a product of primes, nor was it assumed to be true for the purpose of the proof. I know that well ordering and induction are equivalent and that in induciton I would assume the truth of the statment as a part of the proof. Is it just an implied step that was not stated or am I missing somethign crucial from the proof idea?
Best Answer
There is a sort of "inductive hypothesis" here. It is hiding in the definition of $C$ and construction of $n$. We can translate it into a strong induction like so.
As a basis, 2 is prime and can be factored as a product of primes.
Now, assume that $2,...,n-1$ can be factored as products of primes, and consider $n$. Assume for the sake of contradiction that $n$ cannot be factored as a product of primes. (From here I repeat your proof, but so far we have just defined $n$ to match exactly the assumptions on it in the proof -- it is the least number that cannot be factored.) Then $n$ can't be prime, because a prime is a product of primes. Then $n$ must be composite, so that $n=ab$ for $1<a,b<n$. But by our strong inductive hypothesis, $a$ and $b$ can be factored, so it follows that $n$ can be too, which is a contradiction.
So, the correspondence between the well-ordering and the strong induction in this particular case is that both are able to assume for contradiction the existence of some $n$ which is the smallest number that is not a product of primes.