## You are here

Homeexample of well-founded induction

## Primary tabs

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

## Mathematics Subject Classification

03B10*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections