Well Ordering Principle: Definition, Proof, Applications & Examples

The well-ordering principle is a basic idea in mathematics that says every non-empty set of natural numbers has a smallest number. In simple terms, if you have a group of whole numbers and at least one number is in it, then there will always be one number that is the smallest among them. This rule is very useful and is used in many areas of math, like number theory and algebra. It helps prove other ideas and is one of the key tools for solving problems that involve counting or arranging numbers in order.

In this maths blog, we'll explore what the well-ordering principle is, why it's important, and how it's used in mathematics.

Definition and Explanation of the Well-Ordering Principle

The well-ordering principle is a simple idea in mathematics. It says that if you have a set of positive whole numbers and the set is not empty, then there is always one number in that set which is the smallest. In other words, no matter how many numbers are in the set, you can always find the least number.

For example, take the set {1, 2, 3, 4, ...}. This set has many numbers, but 1 is the smallest. So, it follows the well-ordering principle. Another example is the set of positive even numbers {2, 4, 6, 8, ...}. Here, 2 is the smallest number, and all the other numbers are greater than 2. So, this set also follows the well-ordering principle.

This principle is helpful in proving many other ideas in mathematics. It gives us a way to start with the smallest number and move forward in a logical and organized way.

The well-ordering principle is used in many different areas of mathematics. For example, it is used in number theory to prove theorems about prime numbers. The well-ordering principle can also be used to prove the existence of mathematical objects, such as solutions to equations or certain types of functions.

One example of the well-ordering principle in action is the proof of the fundamental theorem of arithmetic. This theorem states that every positive integer can be expressed uniquely as a product of primes. To prove this theorem, we start by assuming that there exists a positive integer that cannot be expressed as a product of primes. Using the well-ordering principle, we can show that this assumption leads to a contradiction, which means that our assumption must be false and the fundamental theorem of arithmetic must be true.

Proof of the Well-Ordering Principle

The formal statement of the Well-Ordering Principle is as follows:

: Every non-empty subset S of the set of positive integers contains a least element. That is, there exists an element such that for all .

Proof: Let S be a non-empty subset of . We will prove the Well-Ordering Principle by contradiction. Suppose that S does not have a least element, that is, for any , there exists an such that .

Now, consider the set . Intuitively, T is the set of all positive integers k such that the set of elements in S that are less than k is non-empty.

Since S is non-empty, there exists some m\in S. Therefore, is empty, which implies that T.

Now, suppose that . Then, by definition of T, there exists some such that m<k. Since S does not have a least element, there must exist some such that . Then, n<k, and so contains an element less than k. Therefore, is non-empty, which implies that T.

Thus, we have shown that , and if , then . By the Principle of Mathematical Induction, it follows that .

Now, for each , define to be the least element of the set . Since S does not have a least element, we have <n for all . Therefore, the sequence is a decreasing sequence of positive integers.

But this contradicts the fact that every decreasing sequence of positive integers must have a lower bound. Specifically, since S for all n, the set S contains an infinite decreasing sequence of positive integers, which contradicts the fact that is well-ordered.

Therefore, our initial assumption that S does not have a least element must be false, and so the Well-Ordering Principle holds.

Well-Ordering Principle vs. Axiom of Choice

The well-ordering principle is closely related to another principle in mathematics, known as the axiom of choice. Both principles deal with the concept of choosing elements from sets. However, the axiom of choice is a stronger principle than the well-ordering principle.

The axiom of choice states that given any collection of non-empty sets, there exists a way to choose one element from each set. This principle is often used in modern mathematics to prove the existence of certain objects or to construct mathematical models.

The well-ordering principle can be thought of as a weaker version of the axiom of choice. In fact, the well-ordering principle can be used to prove the axiom of choice! However, the converse is not true: the axiom of choice cannot be used to prove the well.

Well Ordering Principle Solved Examples

Example 1: Prove that every positive integer can be written as the sum of distinct powers of 2.

Solution:

We will prove this using the well‑ordering principle. Let us assume the opposite of what we want to prove. Let S be the set of positive integers that cannot be written as the sum of distinct powers of 2. Suppose S is non‑empty. Then, by the well‑ordering principle, S must have a smallest element, say n.

Now, n cannot be a power of 2, because powers of 2 (like 1, 2, 4, 8, …) can be written as themselves and are clearly sums of distinct powers of 2 (just one power). So n must be greater than some power of 2. Let’s choose the largest power of 2 less than or equal to n, say 2^k, and let k = n − 2^k, so that k < n.

By the choice of n as the smallest number in S, k is not in S, which means k can be written as the sum of distinct powers of 2. Since n = 2^k + k, we’ve expressed n as the sum of distinct powers of 2, which contradicts the assumption that n is in S.

Therefore, our assumption was wrong. The set S must be empty.

Hence, every positive integer can be written as the sum of distinct powers of 2.

Example 2: Prove that every non-empty set of positive integers has a smallest element.

Solution:
This statement is the well-ordering principle itself, so we usually accept it as a basic rule or axiom in mathematics. However, let us show a simple contradiction if we assume the opposite.

Suppose there is a non-empty set S of positive integers that does not have a smallest element. Pick any number n in S. Now look at all the elements in S that are less than or equal to n. Since these are only a finite number of elements, the set formed is finite and non-empty. Every finite non-empty set of positive integers must have a smallest element. Let that smallest number be k.

Now, k is a positive integer in S that is less than or equal to n, but we assumed that S has no smallest element. That’s a contradiction.

So our assumption must be false.
Therefore, every non-empty set of positive integers has a smallest element.

Example 3: Prove that there are infinitely many prime numbers.
Solution:
We will prove this using the well-ordering principle and contradiction.
Suppose there are only finitely many prime numbers. Let them be p₁, p₂, ..., pₙ. Let N be the product of all these primes:
N = p₁ × p₂ × ⋯ × pₙ

Now, consider the set S of all positive integers greater than 1 that are not divisible by any of these primes. Clearly, 1 is not divisible by any prime, but since we're considering numbers greater than 1, we need to find such a number in S.

If S is non-empty, then by the well-ordering principle, it must have a smallest element, say k.
Now, k is greater than 1 and is not divisible by any of the known primes. This means that k must be a new prime (because otherwise it would have a prime factor among p₁, ..., pₙ, which is not allowed by definition of S).

But we already assumed that p₁, ..., pₙ are all the primes. This contradicts the fact that k is a new prime.

So our assumption that there are only finitely many primes must be false.
Therefore, there are infinitely many prime numbers.

We hope that the above article is helpful for your understanding and exam preparations. Stay tuned to the Testbook App for more updates on related topics from Mathematics and various such subjects. Also, reach out to the test series available to examine your knowledge regarding several exams.

Maths Notes Free PDFs

Topic	PDF Link
Class 12 Maths Important Topics Free Notes PDF	Download PDF
Class 10, 11 Mathematics Study Notes	Download PDF
Most Asked Maths Questions in Exams	Download PDF
Increasing and Decreasing Function in Maths	Download PDF