Proof Of The Well Ordering Principle

Proof of the Well-Ordering Principle

The Well-Ordering Principle states that every non-empty set of positive integers contains a least element. This seemingly simple statement is fundamental in number theory and has far-reaching consequences in mathematics. While intuitive, a rigorous proof requires careful consideration. This article will explore a common proof leveraging the principle of mathematical induction.

This article will provide a clear and concise proof of the Well-Ordering Principle, explaining each step thoroughly to ensure understanding. We will delve into the core concepts and demonstrate how the principle of mathematical induction is instrumental in establishing the truth of the Well-Ordering Principle. Understanding this proof provides a solid foundation for further mathematical exploration.

Understanding the Components

Before diving into the proof, let's clarify the key concepts involved:

• Positive Integers: The set of natural numbers, typically denoted as ℕ, excluding zero: {1, 2, 3, ...}.
• Non-empty Set: A set containing at least one element.
• Least Element: The smallest element within a set, smaller than all other elements in the set.
• Principle of Mathematical Induction: A fundamental proof technique stating that if a property holds for the base case (often 1) and if the property holding for n implies it holds for n+1, then the property holds for all positive integers.

The Proof by Contradiction

We will prove the Well-Ordering Principle using proof by contradiction. This involves assuming the opposite of what we want to prove and showing that this assumption leads to a contradiction. If the assumption leads to a contradiction, it must be false, therefore proving the original statement.

1. Assumption: Let's assume the Well-Ordering Principle is false. This means there exists at least one non-empty subset S of positive integers that does not contain a least element.

2. Constructing a Subset: Since S is non-empty, it must contain at least one element. Let's call this element 'a'.

3. Applying Induction: Now, let's consider the property P(n): "The integer n is not in S."

   • Base Case: Is 1 in S? If 1 is in S, it's the least element (contradicting our assumption). Therefore, 1 is not in S; P(1) is true.

   • Inductive Step: Assume P(k) is true for some positive integer k; that is, k is not in S. Now, let's consider k+1. If k+1 is in S, it would be the least element (because all integers less than or equal to k are not in S). This again contradicts our assumption. Therefore, k+1 is also not in S, making P(k+1) true.

4. Contradiction: By the principle of mathematical induction, P(n) is true for all positive integers n. This means that no positive integer is in S. However, this directly contradicts our initial statement that S is a non-empty subset of positive integers.

5. Conclusion: Since our assumption that the Well-Ordering Principle is false leads to a contradiction, the assumption must be incorrect. Therefore, the Well-Ordering Principle is true: every non-empty set of positive integers contains a least element.

Conclusion

The proof presented utilizes the power of proof by contradiction and the principle of mathematical induction to establish the validity of the Well-Ordering Principle. This principle, though seemingly simple, forms a cornerstone for various mathematical proofs and serves as a powerful tool in various mathematical fields. Its rigorous proof highlights the elegance and precision of mathematical reasoning.