# 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. 1.

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

2. 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$.

Title example of well-founded induction ExampleOfWellfoundedInduction 2013-03-22 12:42:23 2013-03-22 12:42:23 CWoo (3771) CWoo (3771) 9 CWoo (3771) Example msc 03B10