# Well ordering Principle

July 13, 2017 tags: math“Well Ordering Principle” is a very simple concept. It just says,

Every non-empty subset of Natural Numbers is well ordered i.e. every such subset of Natural Numbers contains a least element.

See, nothing could be more trivial. And if you are wondering is this even useful? Believe me, I did that the first time I heard about it and now I am its fan. Another trivial looking principle is Pigeonhole Principle which I won’t talk in detail about here though. It says, If there are N holes and N+1 pigeons then the pigeons cannot have a hole for each, two pigeons must share a single hole.

Now let’s prove a theorem using well ordering principle.
(Theorem) Let n be a positive integer such that n>1 then *n* = *p*_{1}*p*_{2}...*p*_{k} where all *p*_{i}s are prime numbers.

### Proof

Let S be a set of positive integers that cannot be written as product of primes. By the well ordering principle S has a least element, say a. Now, if the factors of a are a and 1 then a is a prime number and thus, this is a contradiction(since S consists of elements which don’t have prime factors).

Next, if *a* is not prime, let *a*_{1} and *a*_{2} are the factors of $a). If both of them
are prime then it again results in contradiction because *a* can be written as
product of primes.

Now, it is obvious *a*_{1} < *a* and *a*_{2} < *a*. If either of *a*_{1} or *a*_{2} can
not be written as product of primes then, either *a*_{1} ∈ *S* or *a*_{2} ∈ *S*. But we already
said that *a* is the smallest element in *S*. So, *a*_{1} and *a*_{2} must be product of
primes i.e. *a*_{1} = *p*_{1}*p*_{2}...*p*_{r} and *a*_{2} = *q*_{1}*q*_{2}...*q*_{s}. Thus, *a* = *a*_{1}.*a*_{2} = *p*_{1}...*p*_{r}.*q*_{1}...*q*_{s} which
is a prime product.

This again created a contradiction that *a* ∈ *S*. Thus, it can
be concluded that there is no positive integer > 1 that can not be written as
prime products.

Well Ordering Principle is pretty cool, right?