example of well-founded induction

This proof of the fundamental theorem of arithmeticMathworldPlanetmath (every natural numberMathworldPlanetmath has a prime factorizationMathworldPlanetmath) 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 relationMathworldPlanetmath is obviously well-founded. The |-minimal elements are the prime numbersMathworldPlanetmath. 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, where m,n1. By inductionMathworldPlanetmath, m and have prime factorizations, the productPlanetmathPlanetmath 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