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\ell$ , where $m,n\not=1$ . By induction, $m$ and $\ell$ have prime factorizations, the product of which is a prime factorization of $n$ .