Well Ordering Principle 2

Flash and JavaScript are required for this feature.

Download the video from iTunes U or the Internet Archive.

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.

Free Downloads

Video


Caption

  • English-US (SRT)