Franklin's Notes


Well-Ordering Principle

The Well-Ordering Principle, sometimes abbreviated WO, states simply that every set can be well-ordered . It turns out that this statement is equivalent to both the Axiom of Choice and Zorn's Lemma .

Theorem 1. The Axiom of Choice is equivalent to the Well-Ordering Principle.

Proof. Assuming AC is true, we also have that Zorn's Lemma holds. (See the page on Zorn's Lemma for a proof of this.) Given a set $A$, we may consider the set $W$ of well-orderings of subsets of $A$. We may define a partial order on $W$ as follows: let $(A_1,\rho_1)\leq (A_2,\rho_2)$ if and only if the former ordering is an initial segment of the latter; that is, if $A_1\subset A_2$, $\rho_1\subset\rho_2$, and $x_1\rho_2 x_2$ whenever $x_1\in A_1$ and $x_2\in A_2\backslash A_1$.

Under this ordering of $W$, any chain must have an upper bound - namely, the well-ordering $(A,\rho)$ where $A$ is the union of all $A_i$ in the chain and $\rho$ is the union of all $\rho_i$ in the chain. Notice that this is, in fact, a well-ordering: for if $A'\subset A$ is nonempty, then $A'\cap A_i\ne\varnothing$ for some $A_i$ in the chain, meaning that $A'\cap A_i$ has a least element in $(A_i,\rho_i)$, which must also be its least element in $(A,\rho)$.

Therefore, since all chains of $(W,\leq)$ have an upper bound, we have that there exists a maximal element $(A^\star,\rho^\star)$ in this ordering, by Zorn's Lemma. However, if $A^\star\ne A$ and there exists some $a\in A$ such that $a\notin A^\star$, then we could form an even greater well-ordering by simply "appending" the extra element $a$ to the well-ordering $(A^\star,\rho^\star)$, like this: However, since this would also be a well-ordering, it would contradicts the maximality of $(A^\star,\rho^\star)$! Hence, we have that $A^*$ must equal $A$, so that $(A,\rho^\star)$ is the desired well-ordering of $A$. Hence, we have that AC $\implies$ WO.

Proving that WO $\implies$ AC is much more straightforward. Given a set $Z$ of disjoint nonempty sets, let $Y=\bigcup Z$ be the union of these sets, and define a well-ordering $(Y,\leq)$. Then we may easily define a choice function $f:Z\to Y$ by letting $f(A)$ be the unique smallest element of $A\subset Y$ for each $A\in Z$, since $(Y,\leq)$ is a well-ordering. $\blacksquare$

set-theory

order-theory

back to home page