PROFESSOR: So let's look at two examples
of using the well-ordering principle.
One of them is pretty obvious, and the other one
is not hard but a little bit more interesting.
So what we're going to prove is that every integer greater
than one is a product of primes.
So remember a prime is an integer greater than 1
that is only divisible by itself and the number 1.
It can't be expressed as the product of other numbers
greater than 1.
So the way we're going to prove this is by contradiction,
and we're going to begin by assuming
suppose that there were some numbers that
were non-products of primes.
OK.
That is to say, the set of non-products is non-empty.
So applying the least-- the well-ordering principle
to this non-empty set of non-products,
there's got to be a least one, so m is a number greater than 1
that is not a product of primes.
Now, by convention, if m itself was a prime,
it's considered to be a product of one prime,
so we know that m is not a prime.
Now look.
M is not a prime, or if it was a prime,
it would be a product of just itself,
so that means that it must be a product of two numbers,
call them j and k, where j and k are greater than 1
and less than m.
That's what it means to be a non-prime-- it's
a product of j and k.
Well, j and k are less than m, so that
means that they must be prime products, because they're
less than m and greater than 1, and m
is the smallest such number that's not a product of primes.
So we can assume that j is equal to some product of prime say,
p1 through p94, and k is some other product of primes,
q1 through q13, so you can see where this is going.
Now what we have is that m, which is jk,
is simply the product of those p's
followed by the product of those q's and is,
in fact, a prime product which is a contradiction.
So what did we assume that led to the contradiction?
We assumed that there were some counter-examples,
and there must not be any, and no counter-examples
means that, in fact, every single integer greater than 1
is indeed a product of primes as [AUDIO OUT].
Let's start looking at a slightly more interesting
example using the well-ordered principle
to reasoning about postage.
So suppose that we have a bunch of $0.05
stamps and $0.03 stamps, and what
I want to analyze is what amounts of postage
can you make out of $0.05 stamps and $0.03 stamps?
So I'm going to introduce a technical definition
for convenience.
Let's say that a number n is postal.
If I can make n plus $0.08 postage from $0.03
and $0.05 stamps.
So this is what I'm going to prove.
I claim that every number is postal.
In other words, I can make every amount of postage
from $0.08 up.
I'm going to prove this by applying
the well-ordering principle, and as
usual with well-ordering principles
we'll begin by supposing that there was
a number that wasn't postal.
That would be a counter-example, so if there's
any number that's not postal, then there's
at least one m by the well-ordering principal,
because the set of counter-examples
is non-empty if some number is not postal,
so there's at least one.
So what we know, in other words, is
that this least m that's not postal has the property.
It's not postal, and any number less than it is postal.
See what we can figure out about m.
First of all, m is not 0-- 0 is postal, because 0 plus $0.08
can be made with a $0.03 stamp and a $0.05 stamp.
M is not 0, because m is supposed to be not postal.
As a matter of fact, by the same reasoning,
m is not 1 because you can make 1 plus $0.08 with three $0.03,
and m is not 2, because you can make 2 plus $0.08-- $0.10--
using two $0.05.
So we've just figured out that this least counter-example has
to be greater than or equal to 3,
because 0, 1, and 2 are not counter-examples.
So we've got that m is greater than
or equal to 3, the least non-postal number,
so if I look at m minus 3, that means
it's a number that's greater than or equal to 0,
and it's less than m, so it's postal,
because m is the least non-postal one.
So, in other words, I can make-- out of $0.03 and $0.05 stamps,
I can make m minus 3 plus $0.08 but, look,
if I can make m minus 3 plus $0.08,
then obviously m is postal also, because I just
add $0.03 to that and minus 3 number,
and I wind up with m plus $0.08, which
says that m is postal and is a contradiction.
So assuming that there was a least non-postal number,
I reach a contradiction and therefore there
is no non-postal number.
Every number is postal-- 0 plus 8 is postal,
1 plus 8 is postal, 2 plus 8 is postal.
Every number greater than or equal to $0.08
can be made out of $0.03 and $0.05 stamps.