example of well-founded induction

This proof of the fundamental theorem of arithmetic (every natural number has a prime factorization) affords an example of proof by well-founded induction over a well-founded relation that is not a linear order.

First note that the division relation is obviously well-founded. The $|$-minimal elements are the prime numbers. We detail the two steps of the proof :

1. If $n$ is prime, then $n$ is its own factorization into primes, so the assertion is true for the $|$-minimal elements.

2. If $n$ is not prime, then $n$ has a non-trivial factorization (by definition of not being prime), i.e. $n=m\mathrm{\ell }$, where $m,n\ne 1$. By induction, $m$ and $\mathrm{\ell }$ have prime factorizations, the product of which is a prime factorization of $n$.