Well ordering

This uses the fact that with N there is always a smallest element.

Fundamental theorem of Arithmetic, by Well Ordering

Proof, by contradiction:

• S = {n ? N | n can not be expressed as a product of primes}

• Let s ? S be its smallest element. s can not be prime, since it is in S, so:

• s = ab for some a, b ? N with 1 < a, b < s.

• a and b are smaller than the least element of S, and so can not be in S

• So a and b can be written as products of primes, but combining a and b gives s from primes

• Contradiction

Proof, by mathematical induction:

• 1 P(n) is the statement there is no element of N smaller than n

• 2 Base case: P(0) is true, as there are no natural numbers smaller than 0

• 3 Assume P(n) is true

• If P(n+1) were false, then theres a smaller element than (n+1) but it must be bigger than n as P(n) is true. So there is a minimal element n

• By induction, if P(n) implies P(n+1) for all n, then P(n) is true for all n