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

Title	example of well-founded induction
Canonical name	ExampleOfWellfoundedInduction
Date of creation	2013-03-22 12:42:23
Last modified on	2013-03-22 12:42:23
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	9
Author	CWoo (3771)
Entry type	Example
Classification	msc 03B10