PROFESSOR: The well ordering principle is one of those facts in mathematics that's so obvious that you hardly notice it. And the objective of this brief introduction is to call your attention to it. We've actually used it already. And in subsequent segments of this presentation, I'll show lots of applications of it.
So here's a statement of the well ordering principle. Every nonempty set of nonnegative integers has a least element. Now this is probably familiar. Maybe you haven't even thought about it. But now that I mentioned it, I expect it's a familiar idea.
And it's pretty obvious too if you think about it for a minute. Here's a way to think about it. Given an nonempty set of integers, you could ask, is 0 the least element in it? Well, if it is, then you're done.
Then you could say, is 1 the least element in it? And if it is, you're done. And if it isn't, you could say 2, is 2 the least element? And so on. Given that it's not empty, eventually you're to hit the least element.
So, if it wasn't obvious before, there is something of a hand-waving proof of it. But I want to get you to think about this well ordering principle a little bit because it's not-- there are some technical parts of it that matter. So for example, suppose I replace nonnegative integers by nonnegative rationals.
And I asked does every nonempty set of nonnegative rationals have a least element? Well, there is a least nonnegative rational, namely 0. But not every nonnegative set of rationals has a least element. I'll let you think of an example.
Another variant is when, instead of talking about the nonnegative integers, I just talk about all the integers. Is there a least integer? Well, no, obviously because minus 1 is not the least. And minus 2 is not the least. And there isn't any least integer.
We take for granted the well ordering principle just all the time. If I ask you, what was the youngest age of an MIT graduate well, you wouldn't for a moment wonder whether there was a youngest age. And if I asked you for the smallest number of neurons in any animal, you wouldn't wonder whether there was or wasn't a smallest number of neurons. We may not know what it is. But there's surely a smallest number of neurons because neurons are nonnegative integers. And finally, if I ask you what was the smallest number of US coins that could make $1.17, again, we don't have to worry about existence because the well ordering principle knocks that off immediately.
Now for the remainder of this talk, I'm going to be talking about the nonnegative integers always, unless I explicitly say otherwise. So I'm just going to is the word number to mean nonnegative integer. There's a standard mathematical symbol that we use to denote the nonnegative integers. It's that letter N at the top of the slide with a with a diagonal double bar.
These are sometimes called the natural numbers. But I've never been able to understand or figure out whether 0 is natural or not. So we don't use that phrase. Zero is included in N, the nonnegative integers. And that's what we call them in this class.
Now, I want to point out that we've actually used the well ordering principle already without maybe not noticing it, even in the proof that the square root of 2 was not rational. That proof began by saying, suppose the square root of 2 was rational, that is, it was a quotient of integers m over n. And the remark was that you can always express a fraction like that in lowest terms. More precisely, you can always find positive numbers m and n without common factors, such that the square root of 2 equals m over n. If there's any fraction equal to the square root of 2, then there is a lowest terms fraction m over n with no common factors.
So now we can use well ordering to come up with a simple, and hopefully very clear and convincing, argument for why every fraction can be expressed in lowest terms. In particular, let's look at numbers m and n such that the square root of 2 is equal to m over n-- that fraction. And let's just choose the smallest numerator that works. Find the smallest numerator m, such that squared of 2 is equal to m over n.
Well, I claim that that fraction, which uses the smallest possible numerator, has got to be in lowest terms because suppose that m and n had a common factor c that was greater than 1-- a real common factor. Then you could replace m over n by m over c, the numerator is a smaller numerator that's still an integer, and n over c. The denominator is still an integer.
And we have a numerator that's smaller than m contradicting the way that we chose m in the first place. And this contradiction, of course, implies that m and n have no common factors. And therefore, as claimed, m over n is in lowest terms. And of course, the way I formulated this was for our application of the fraction that was equal to the square root of 2. But this proof actually shows that any rational number, any fraction, can be expressed in lowest terms.