Well Ordering Principle
Well, “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=p1p2…pk where all pi’s are prime numbers.
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 a1 and a2 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 a1 < a and a2 < a. If either of a1 or a2 can not be written as product of primes then, either a1 or a2 belongs to S. But we already said that a is the smallest element in S. So, a2 and a2 must be product of primes i.e.a1=p1p2…pr and a2=q1q2…qs. Thus,
a = a1.a2 = p1…pr.q1…qs which is a prime product. This again created a contradiction that a belongs to 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?