The Well Ordering Principle is
or
note how it only applies to sets with nonnegative integers.
By the WOP, we can assume that for any positive integers and , the fraction can be written in lowest terms.. in the form where and are positive integers with no common prime factors. How do we know this is possible?
Suppose to the contrary that there are positive integers and such that the fraction cannot be written in lowest terms.
Let .
Then so is nonempty.
By WOP, there must be a smallest integer .
By definition of , there is an integer such that
This means that and must have a common prime factor, , but
so any way of expressing the left-hand fraction in lowest terms would also work for , which implies
So by definition of , the numerator is in . But m which contradicts the fact that is the smallest element of .
Since the assumption that is nonempty leads to a contradiction, it follows that must be empty. That is, there are no numerators of fractions that can't be written in lowest terms, and hence there are no such fractions at all.
Standard way to prove that holds for every nonnegative integer (" is true for all ").
(The notation means that "the set if all elements for which is true.")
Assume for proof by contradiction that is nonempty.
By WOP, there will be a smallest element in .
Reach a contradiction somehow - often by showing that is actually true or by showing that there is another member of that is smaller than . This is the open ended part of the proof task.
Conclude that must be empty, that is, no counterexamples exist.
Every integer greater than one has a unique1 expression as a product of prime numbers.
1 - Unique up to the order in which the prime factors appear.
Theorem: Every positive integer greater than one can be factored as a product of primes.
Proof: This proof is by WOP.
Let be the set of all integers greater than one that can't be factored as a product of primes. We assume is not empty and derive a contradiction.
If is not empty, there is a least element by WOP. This can't be prime, because a prime by itself is considered a (length one) product of primes, and no such products are in .
So must be a product of two integers and where and .
Since and are smaller than the smallest element in , we know that .
In other words, can be written as a product of primes and as a product of primes .
Therefore, can be written as a product of primes, contradicting the claim that . Our assumption that is not empty must therefore be false.
Well ordering cokmmonly comes up in computer science as a method for proving that computations won't run forever. The idea is to assign a value to each successive step of a computation so that the values get smaller at every step. If the values are all from a well ordered set, then the computation can't run forever, because if it did, the values assigned to its successive steps would define a subset with no minimum element.
Notice that a set may have a minimum element but not be well ordered. The set of nonnegative rational numbers is an example: is has a minimum element zero, but it also has nonempty subsets that don't have minimum elements - the positive rationals, for example.
The following theorem is a generalization of the WOP: "For any nonnegative integer the set of integers greater than or equal to is well ordered." (Proven in example section below)
The definition of well ordering states that every subset of a well ordered set is well ordered, and this yields two convenient corollaries to the generalized theorem above (proved in the examples section below):
A lower bound for a set of real numbers is a number such that for every .
A upper bound for a set of real numbers is a number such that for every .
(Note that a lower or upper bound of set is not required to be in the set)
Corollary 1: Any set of integers with a lower bound is well ordered.
Corollary 2: Any nonempty set of integers with an upper bound has a maximum element.
Finite sets are yet another routine example of well ordered set.
Lemma 1: Every nonempty finite set of real numbers is well ordered.
Theorem:
For any nonnegative integer the set of integers greater than or equal to is well ordered.
Proof:
Let be any nonempty set of integers . Now add to each of the elements in ; lets call this new set . Now is a nonempty set of nonnegative integers, and so by WOP, it has a minimum element . Then it is easy to see is the minimum element of .
Theorem: Any set of integers with a lower bound is well ordered.
Proof:
A set of integers with a lower bound will also have an integer as a lower bound, where , called the floor of , is gotten by rounded down to the nearest integer. So the theorem "For any nonnegative integer the set of integers greater than or equal to is well ordered." implies the set is well ordered.
Theorem: Any nonempty set of integers with an upper bound has a maximum
element.
Proof:
Suppose a set of integers has an upper bound .
Multiply each element of by ; lets call this new set of elements .
is a lower bound of .
So has a minimum element by corollary 1. Then it is easy to see that is the maximum element of .
Theorem: Every nonempty finite set of real numbers is well ordered.
Proof:
Since subsets of finite sets are finite, it is sufficient to prove that every finite set has a minimum element.
We prove this using the WOP on the size of finite sets.
Let be the set of positive integers such that some set of size has no minimum element. Assume for the sake of contradiction that is nonempty. By WOP, there is a minimum integer .
Every set if size one obviously has a minimum element, so .
Let be a set of real numbers. We will reach a contradiction by showing that has a minimum element.
Let be an element of . Since , removing from leaves a nonempty set smaller than . Since is the smallest element of , we know that has a minimum element of . But tghat means the smaller of and is the minimum element of .
Theorem:
for all nonnegative integers .
Proof:
By contradiction. Assume the theorem is false. Then, some nonnegative integers serve as counterexamples ot it. Collected in a set:
(set C is defined as the set of natural numbers that when added up don't equal .
Assuming there are counter examples, is a nonempty set of nonnegative integers.
By WOP, has a minimum element which is the smallest counterexample, .
Since is the smallest counterexample, we know that our theorem is false for but true for all nonegative integers . But our theorem is true for , so . This means that is a nonnegative integer, and since it it less than , our theorem is true for . That is,
Adding to both sides, we get
which means that our theorem does hold for afer all. This is a contradiction, and we are done.