I 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.

▲

BeetleB a day ago | parent | next [-]

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?"

▲

kccqzy a day ago | parent [-]

You are talking about the well-ordering theorem, not the similarly named well-ordering principle. That’s exactly my confusion when I first opened this PDF.

	▲	BeetleB a day ago \| parent [-]
		Different folks use different conventions. When I was taught it, they called it the principle, not theorem. You can find similar comments on the Internet (e.g. math subreddit). Here's one that acknowledges it: https://math.stackexchange.com/questions/1837836/well-orderi... > The "well-ordering principle" has (at least) two different meanings. The first meaning is just another name for the well-ordering theorem. The second meaning is the statement that the usual relation < on the set N is a well-ordering. This statement is equivalent to the statement that ordinary induction on the natural numbers works.

▲

soseng a day ago | parent | prev [-]

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

▲

kccqzy a day ago | parent [-]

Yeah. I have had several different courses teach induction, and nobody really thinks of the WOP. I’m pretty sure most of them skips the WOP when introducing induction.

	▲	seanhunter a day ago \| parent [-]
		I’ve seen it used when people show a proof of induction as a theorem. Sometimes they just take the technique of induction as given and don’t prove it.