alt Hacker NewsI took a look at the table of contents and found that the second chapter is about the well-ordering principle. That’s surprising to me because I’ve only heard of the well-ordering theorem by Zermelo, which is a fundamental theorem in set theory, stating that any set has a well-ordering assuming the axiom of choice. It’s amazing and mind-bending in its own right (imagine a well-ordering for reals), but is clearly not very relevant to computer science.
I find the well-ordering principle slightly bewildering. It seems to presuppose the existence of an ordering on natural numbers and then prove this principle. But I’ve never been taught things this way; you always construct the natural numbers from Peano and define the ordering first, then you can actually prove the well-ordering principle rather than leaving it as an axiom.
Replies
Not to say it isn't useful to a CS education, but the only time I've ever ran into the well-ordering principle was to establish the foundation for mathematical induction proofs. Students usually learn this in discrete math for CS in undergrad. Then in many future undergrad courses that are algorithms focused, the proofs tend to use induction and no one really thinks of the WOP
The well ordering principle, the axiom of choice, and Zorn's Lemma are all "equivalent", meaning you can pick any one as an axiom and prove the other two.
So some text books may pick one as the axiom and others pick a different axiom.
The crazy thing about the well-ordering principle: It states that a well ordering exists on the reals, which means that you can find an ordering such that any open set has a minimum. Apparently, elsewhere in mathematics, they've proven that even though it exists, you cannot articulate that ordering.
There's a common joke:
"The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?"