Franklin's Notes

The Szpilrajn Extension Theorem is as follows:

Szpilrajn Extension Theorem. Every partial ordering on a set can be extended to a total order. That is, if $(A,\rho)$ is a partial ordering of $A$, then there exists $\rho'$ such that $\rho\subset \rho'$ and $(A,\rho')$ is a total ordering.

As it happens, this statement is equivalent to Zorn's Lemma (which is in turn equivalent to the Axiom of Choice and the Well-Ordering Principle ).

Theorem 1. Zorn's Lemma implies the Szpilrajn Extension Theorem.

Proof. Given a set $A$ and a partial ordering $(A,\rho)$, consider the set $R$ of all partial orderings extending that partial order, ordered by inclusion. (That is, if $\rho_1$ and $\rho_2$ are two orders extending $\rho$, we say that $\rho_1\leq \rho_2$ if and only if $\rho_1\subset\rho_2$.) Every chain of $(R,\leq)$ has an upper bound, namely the union of all partial orderings in that chain (which must itself be a partial ordering). By Zorn's Lemma, there must exist a maximal partial ordering $\rho^\star$ extending $\rho$. However, if $\rho^\star$ were not a total ordering and there existed two elements $x,y\in A$ incomparable under $\rho^\star$, then $\rho^\star\cup{(x,y)}$ would be another partial ordering strictly greater than $\rho^\star$ - but this would contradict the maximality of $\rho^\star$! Hence, $\rho^\star$ must be a total order, and we have verified the existence of a total order extending $\rho$, so Zorn's Lemma $\implies$ the Szpilrajn Extension Theorem.

Question. Does the Szpilrajn Extension Theorem imply Zorn's Lemma? In other words, are they equivalent?



back to home page