Applications of Zorn’s lemma with orderings other than set inclusion

axiom-of-choicereference-requestset-theory

In my set theory lecture notes, there is the following paragraph, after proving Axiom of Choice from Zorn's lemma:

The demonstration of this theorem is a typical example of the application of Zorn's lemma: we want to prove the existence of a set with certain properties (in our case, a choice function for a set $A$). A set like this will be a maximal element of a partially ordered set that satisfies the hypothesis of Zorn's lemma (in our case, of the set of choice functions for substs of $A$, partially ordered by strict inclusion). This way, we try to form a partially ordered set out from sets that have the properties we want the set we are looking for to have (if we want a choice function, the partially ordered set will consist of choice functions). Moreover, we will usually tend to consider the simplest partial order relations as possible (in the preceding case, like in almost any case $-$but not in all of them$-$, the strict inclusion relation).

I'm puzzled by the emphasis made in the very last line of the quote; during my whole course of set theory, we have used Zorn's lemma in the very same fashion as explained above, only considering the strict inclusion relation. However, with this method we have been able to proof a lot of results: Hausdorff 's maximal principle, Zermelo's well-ordering theorem, Teichmüller-Tukey's lemma, the order extension property, that for all infinite set $A,\;A\approx A\times A$, and many others, including the basic fact from linear algebra, that every vector space has a basis.

It is reasonable to consider, from the list I gave above, that Zorn's lemma is an extremely powerful result, because just considering the simplest partial order relation we can obtain a handful of results (although most of them are actually equivalent to Zorn's lemma).

How far-reaching can Zorn's lemma be, if we are considering non-standard partial order relations, different from the strict inclusion? Is there any concrete example of such application? I have been searching for such a result for the last days, but I have not yet encountered what I was looking for.

Thanks in advance for your interest, and your contributions

Best Answer

After some hard work, I found the following example:

Zorn's lemma implies the Zermelo well-ordering principle: Let $S$ be a set. We will prove that there exists a relation in $S$ that is a well-order of the set. Let:

$$\mathcal{W}=\{\langle A,<_A\rangle|A\subset S\;\&\;<_A\subseteq A\times A\text{ is a well-ordering of }A\}$$

Clearly, $\mathcal{W}\not=\emptyset$; in fact, from the Russell-Whitehead theorem we know that every finite subset $A\subseteq S$ can be well-ordered. We will define in $\mathcal{W}$ the following relation:

$$\langle A,<_A\rangle\preccurlyeq\langle B,<_B\rangle\iff\langle A,<_A\rangle\text{ is an initial segment of }\langle B,<_B\rangle$$

Or in other words:

  1. $A\subseteq B$
  2. $<_A\subseteq <_B\cap(B\times B)$
  3. For each $a\in A$ and $b\in B\setminus A$, we have that $a<_B b$

Clearly, $\prec$ is irreflexive and transitive, so $\langle\mathcal{W},\prec\rangle$ is a partially ordered set.

Let $C$ be a chain of $\langle\mathcal{W},\prec\rangle$. We will see that $C$ has an upper bound in $\langle\mathcal{W},\prec\rangle$. Let $U=\bigcup \text{dom}(C)$, and for each $s,t\in U$, we will say that $s<_U t$ if $s,t\in A$ and $s<_A t$ for some $\langle A,<_A\rangle$.

$<_U$ is then clearly well-defined and is a linear ordering of $U$. If $A\subset U$, then there exists $\langle B,<_B\rangle\in C$ such that $A\cap B\not=\emptyset$, and therefore, $A$ admits a minimal element $a_B$ (in the sense of $<_B$).

We will see that this can be defined to be the minimal element of $A$ in the sense of $<_U$. If it is also true that $a\cap B'\not=\emptyset$, for another set $B'$ with $\langle B',<_{B'}\rangle\in C$, since $C$ is a chain of $\langle W,\prec \rangle$, $\langle B,<_B\rangle\preccurlyeq\langle B',<_{B'}\rangle\text{ or }\langle B',<_{B'}\rangle\prec\langle B,<_B\rangle$. For example, suppose that $\langle B,<_B\rangle\preccurlyeq\langle B',<_{B'}\rangle$ (the other case is analogous). This implies that the minimal elements $a_B$ and $a_{B'}$ of $A\cap B$ and $A\cap B'$ are the same, since $\langle B, <_B\rangle$ is an initial segment of $\langle B',<_{B'}\rangle$, or $B=B'$.

In the end, $\langle U,<_U\rangle\in\mathcal{W}$ and it is an upper bound of $C$ in $\langle\mathcal{W},\prec\rangle$.

By Zorn's lemma, $\mathcal{W}$ admits a maximal element $\langle M,<_M\rangle$ in the sense of $\prec$. Lets see that, in fact, $<_M$ is a well-ordering of the set $S$. On the one hand, it is clear that $<_M$ is a well-order of a subset of $S$. On the other hand, if there existed an element $s\in S\setminus M$, then we could consider the set $M'=M\cup \{s\}$ and the relation $<_{M'}$ (that extends $<_M$) defined by: for each $t\in M$, $t<_{M'} s$. But then $\langle M', <_{M'}\rangle\in\mathcal{W}$, contradicting the fact that $\langle M,<_M\rangle$ is maximal.

Therefore, $<_M$ is a well-order of the set $S$.

Related Question