Well-Ordering Principle

In this topic, we first state the Well-Ordering Principle and then we use it to prove the Archimedean Property and the Principal of Mathematical Induction. We then prove that the Well-Ordering Principle and the Principle Mathematical Induction are equivalent statements.

Definition (Well-Ordering Principle) The Well-Ordering Principle is the following statement:

    every nonempty set of positive integers contains a least element.

The Principle of Well-Ordering states that every nonempty set of positive integers contains a least element; that is, there is some in such that for all in In such a case, we say that the set is well-ordered with respect to The following proof is a typical "proof by contradiction" involving the Well-Ordering Principle.

Proposition (Archimedean Property) If and are positive integers, then there exists a positive integer such that

Proof. Assume for a contradiction that and do not satisfy the statement; that is, assume there exists positive integers and such that for every positive integer Consider the set,

which consists only of positive integers. By the Well-Ordering Principle, possess a least element, say for some positive integer However, is in and is less than by

Therefore, for positive integers and there must exist a positive integer such that

The method of proof by using the Principle Mathematical Induction is frequently useful in the theory of numbers. Familiarity with this type of argument is essential to subsequent work.

Proposition (Principle of Mathematical Induction) Let be a set of positive integers with the following property:

    (i) The integer 1 belongs to

    (ii) If is in then is in

Then is the set of positive integers.

    Proof. Let be the set of all positive integers not in and assume that is not empty. The Well-Ordering Principle states that must have a least element, say However, by (i) 1 is in and so it follows that and and therefore, is not in Then by (ii), is in which contradicts that lies in Therefore, is empty and so is the set of positive integers.

In any proof by mathematical induction, we must not forget to show that is in (called the basis step). Even if we show that the truth of in implies that is in if is not in then we cannot conclude that is the set of positive integers. For example, let be the set of all positive integers that satisfies: Suppose satisfies, Using this we have, so also satisfies: So, if satisfies: then, it would follow that is true for all positive integers However, since does not satisfy it is not true. In fact, is false for all positive integers
The next result states that the Well-Ordering Principle and the Principle of Mathematical Induction are equivalent. So in fact, either one can be used as an axiom.

Proposition (Mathematical Induction - Well Ordering Equivalence) If a set of positive integers has the two properties (i) the integer 1 belongs to and (ii) whenever the integer is in the next integer must also be in then is the set of positive integers; then every set of positive integers must a have a least element.

Proof. Assume that there exists a nonempty set of positive integers, say that does not have a least element. Because is the smallest positive integer, is not in and so is smaller than all integers in Let be the set of all positive integers that are less than all the integers in At least is in and so is nonempty. Suppose that is in If is in then by the Principle of Mathematical Induction must be the set of all positive integers, and thus is empty and so every set of positive integers must have a least element. If is not in then is the least integer in which contradicts the definition of Therefore, if is a nonempty set of positive integers, then must have a least integer.