Tuesday, August 25, 2009

The Well-Ordering Principle and the Pop Quiz Paradox

Last night in class, we went over a proof of the Well-Ordering Principle, and tonight, it occurs to me how much that proof reminds me of what was possibly the first inductive "proof" I ever encountered: the pop-quiz paradox.

First, the well-ordering principle. This just states that, if you have a non-empty set of natural numbers, it has a least element. The natural numbers, N, are these ones:

{1, 2, 3, ...}

i.e., the counting numbers.

So if you take any subset of those, it will have a smallest element. Duh, right?

The well-ordering principle is actually equivalent to the principle of mathematical induction, which enables a certain type of proof, which is the type I am going to give of the well-ordering principle, as follows:
Let S be a non-empty subset of the natural numbers.
Assume, for a contradiction, that S has no least element.
Then 1 can't be in S, because otherwise, since 1 is the smallest natural number, it would be the least element of S.
Suppose, for some number k, that all of the numbers {1, 2, 3, ... k} are not in the set.
Then k+1 can't be in the set, or it would be the least element.
Thus, by the principle of mathematical induction, S is empty, a contradiction.
That is what is called a "proof by induction."

Now, the pop quiz paradox:
Let's say a teacher says she is going to give a pop quiz next week. It is impossible for the teacher to give a pop quiz in a specific week without the students' knowing what day it will be on. If she waits until Friday, the students will know it must be on Friday since it hasn't happened yet, so Friday is out. But since Friday is out, Thursday is also out - if she hasn't given it by Thursday, the students will know it must be on Thursday. But if Thursday and Friday are both out, then so is Wednesday, ...
It is worth noting that, while the well-ordering principle is true, it is, empirically speaking, not impossible to give a pop quiz, even with advance notice of the week in which it is to occur.


Edward said...

Empirically, it is possible to give advance notice of the day in which the quiz is to occur, and still have it be a pop quiz.

At least to a few.

Tam said...

That sounds like something Robert would have posted.

Tam said...

Oh, and also, I find that the title of this post is very amusing if you imagine that it has the form of something like a Harry Potter book (e.g., Harry Potter and the Half Blood Prince).

Anonymous said...

I used to tell my Calc students on Friday that I was going to give them such a pop quiz the next week. After a bit, someone would point out that i couldn't give it on Friday and that started the ball rolling. We all finally decided that I could not give such a quiz.
The next Monday I came in and gave them a pop quiz! I pointed out that not only did they not know I was giving on that day, they knew I could not give it at all. I laughed but I don't think my students appreciated the joke.