Lesson 1

This chapter was inspired by the book The Beginning of Set Theory by Vereshchagin and Shen (originally written in Russian).

Dilworth's theorem and its dual beautifully characterize the structure of finite posets. But what happens when we venture into the realm of infinite sets? One of the most fundamental questions is whether we can always impose a structured order on any set, no matter how large or bizarre.

A well-ordering on a set \(S\) is a total ordering where every non-empty subset of \(S\) has a least element. The natural numbers with \(\le\) are well-ordered. The integers are not (the set of all integers has no least element). The positive real numbers are not (the open interval \((0, 1)\) has no least element). Can we, for instance, well-order the real numbers? The answer is yes, but the proof requires a powerful and once-controversial axiom.

Theorem (Zermelo's Well-Ordering Theorem, 1904). Every set can be well-ordered.

This theorem is logically equivalent to the famous Axiom of Choice (AC). AC states that for any collection of non-empty sets, it's possible to choose exactly one element from each set. It sounds obvious, but for infinite collections, it asserts the existence of a choice function without providing a way to construct it.

But at first, we prove that AC follows from the Well-Ordering Theorem.

Theorem. The Axiom of Choice follows from the Well-Ordering Theorem.

Proof. What does AC state? It says that for any collection of non-empty sets, there exists a function that chooses one element from each set. Let's construct such a function. Let \(\mathcal{F}\) be an arbitrary set. The Well-Ordering Theorem says that there is an ordering on \(\mathcal{F}\) such that there is unique minimum element \(x\). Hence, our function on \(\mathcal{F}\) outputs \(x\). Thus, we have constructed a choice function, proving that the Axiom of Choice holds.◼