Tip:
Highlight text to annotate it
X
In the last lecture we presented 3 different versions of the principle of mathematical
induction and in the last one we talked about the well ordering principle and
mentioned that it was equivalent to the principle of mathematical induction.
We will prove now that the well ordering principle is equivalent to the principle of mathematical
induction.
What do mathematicians mean when they say that two statements are logically equivalent?
To understand this we first need to know that the majority of mathematical propositions
are statements that are true if some condition or conditions are satisfied. What that means
is that if any of the conditions fail to be true then the consequence will not necessarily
be true. Propositions of this types are the atoms that make up the whole body of mathematics.
The first part of preconditions, suppositions or conditions that are assume to be true are
called the hypotheses and they are usually pre appended with the "if" word. Then before
the consequent or conclusion we find the "then" word.
We have already seen examples of mathematical propositions in that form.
Like If k is a natural number greater than 1 then
it can be represented as a product of primes. Many times the if and then do not explicitly
appear but they are implied, if we could turn tables reversing the role of the hypothesis
or the conclusion or thesis that is if we could make the thesis be the hypothesis and
the hypothesis be the thesis then the hypothesis is mathematically equivalent to the thesis.
Discovering that two statements are equivalent is something very important. For a mathematician
this is important because it will allow an equivalent translation of a statement just
the same as one is able to translate from english to spanish or any other language even
more the mathematical equivalence of statements got a meaning similar to equality. Like in
an equality of two numbers. For example, one immediate consequence of
equality of numbers we do without even thinking is that we can replace one for the other.
Like one is able to replace 2 every where we see 1+1 this is just the same with mathematical
logical equivalency. We will study this in more detail at some other lecture.
So what this all means is that to prove the principle of mathematical induction is equivalent
to the well ordering principle we need to prove that the well ordering principle is
a consequence of the principle of mathematical induction and the other way around, that the
principle of mathematical induction is a consequence of the well ordering principle.
Let us refresh our memory. About what each of them claim.
The principle of weak mathematical induction If P sub k is some proposition we need to
proof where k is natural we first need to prove the basis step that P sub 1 is true
and then we prove the inductive step we assume that P sub k is true for some arbitrary k
and derived from here that P sub k +1 is also true, therefore P sub k is valid for all k
natural. That is the conclusion of the principle of weak mathematical induction and the well
ordering principle states that for any non empty subset of natural numbers there is a
minimal integer that belongs to that subset. At first sight there seems to be no relation
between one principle and the other. The principle of mathematical induction says that if some
proposition is valid for a first element and also satisfy that if assume valid for some
arbitrary k is valid for k+1 then the proposition is valid for all the natural numbers. The
well ordering principle also talks about a first element. It claims
that any non empty subset will have a smallest element.
First let us notice that if we can see an element that is smaller than any other on
a subset then we are in effect comparing all the elements of the subset in order to find
the smallest the usual way to compare natural numbers is using the relation "is less than".
We can also see why we need the condition that the subset must not be empty. That is
because if it was it will not contain any elements and therefore it will not have an
smallest element. When we pick the subset it could be finite
or infinite. If the subset is finite we can see is trivial to find the smallest element
of the subset if the subset is infinite then it is not very clear how that could happen.
Now we can see some relation on both we talked about some first element satisfying some property
for the well ordering principle that is just a mere existance of that first element in
any non empty subset and of other possibly an infinitude of elements that belong to some
subset so that an element belongs to a subset can be considered as the property analogous
to the property P sub k in the principle of mathematical induction.
Let us first prove that the principle of weak mathematical induction implies the well ordering
principle. Proof
Let P be a non empty subset of naturals N and suppose that P has no smallest element.
As you can see we are actually supposing that the well ordering principle is not true. Let
us define a subset Q of natural numbers in N such that the elements of Q are not on P.
Clearly 1 is in Q since if it was on P then P will have a smallest element. We can also
see this is also true for 2 that means that 2 is also in Q for the same reason and so
on until we arrive to k that also have to be in Q and also k+1 have to be in Q otherwise
k+1 will be the smallest element of P but by the principle of mathematical induction
that means that Q contains all the natural numbers but since Q contain all the natural
numbers not in P then P must be empty but by our hypothesis P can not be empty so we
have arrived to a contradiction!
Now let us prove the other way. That is to show that the well ordering principle
implies the principle of weak mathematical induction.
The consequence of the principle of mathematical induction is that P sub k is valid for all
natural number so let us assume that Q is the set of natural numbers such that P sub
k is false. If Q is empty then P sub k is true for every
natural so we are done with the prove. If Q is non empty then by the well ordering
principle there is a natural number k in Q that is the smallest element of Q but that
means that P sub k-1 must be true because otherwise k will not be the smallest element
of Q. So P sub k is true for {1, 2, up to k-1} but then by the inductive step P sub
k is also true. But that is a Contradiction! So we have prove that the principle of mathematical
induction is equivalent to the well ordering principle.
If you noticed in the proof we made in the prior lecture about the square root of 2 been
a rational. We assume that it was rational and then try to arrive to a contradiction
and for that we use the well ordering principle. As a consequence of assume the square root
of 2 is rational we were able to build an infinite decreasing sequence of natural integers.
Something that is impossible by the well ordering principle. It is of interest to know that
if we regard the subset of all mathematical statements of certain type that are in existence
now and also the statements formulated by mathematicians in the future we can then apply
the well ordering principle to this subset and assuming as ordering the order of the
statements in the deductive sequence. Then we arrive to the conclusion that there is
a smallest elements to that list. No matter even if that list is infinite. The well ordering
principle guarantees that there is a first element and not surprisingly the well ordering
principle itself is chosen as that kind of primal building block of mathematical statements
that mathematicians used. This very special first statements in the list are called Axioms.