Exercise WO.6

Proof. First, suppose that the maximum principle is true and let $X$ be any set. Then let $A$ be the collection of all pairs $(A,<)$, where $A\subset X$ and $<$ is a well-ordering of $A$ as in Exercise WO.5. Define the relation $\prec$ on $A$ also as in Exercise WO.5, i.e $(A,<)\prec (A^{\prime },{<}^{\prime })$ if $(A,<)$ is a section of $(A^{\prime },{<}^{\prime })$. It was then shown in that exercise that $\prec$ is a strict partial order on $A$ so that, by the maximum principle, there is a maximal simply ordered subset $B\subset A$. Now let $(B^{\prime },{<}^{\prime })$ be the unions of the corresponding elements of $B$ so that we know that ${<}^{\prime }$ well-orders $B^{\prime }$ by part (b) of Exercise WO.5.

We claim that $B^{\prime }=X$. Suppose that this is not the case so that there is a $x\in X$ where $x\notin B^{\prime }$ (since we know that $B^{\prime }\subset X$). Then define $B^{\mathit{\prime \prime }}=B^{\prime }\cup \left\{x\right\}$ and the relation ${<}^{\mathit{\prime \prime }}={<}^{\prime }\cup \left\{(b^{\prime },x)\mid b^{\prime }\in B^{\prime }\right\}$. It is then easy to see (and trivial but tedious to show) that $B^{\mathit{\prime \prime }}$ is well-ordered by ${<}^{\mathit{\prime \prime }}$. Also, clearly $B^{\prime }$ is the section of $B^{\mathit{\prime \prime }}$ by $x$ so that, for any $B\in B$, we have $B\preccurlyeq B^{\prime }\prec B^{\mathit{\prime \prime }}$. Since $B$ was arbitrary, this shows that the set $B\cup \left\{B^{\mathit{\prime \prime }}\right\}$ is simply ordered by $\prec$ and is a subset of $A$. Since $x\notin B^{\prime }$ we have that $x\notin B$ for any $B\in B$ (since $B^{\prime }$ is their union) so that $B^{\mathit{\prime \prime }}\ne B$ since $x\in B$. It follows that $B⊊B\cup \left\{B^{\mathit{\prime \prime }}\right\}$, but this contradicts the maximality of $B$! So it has to be that in fact $B^{\prime }=X$ itself so that ${<}^{\prime }$ is a well-ordering of $X$. Since $X$ was an arbitrary set, this shows the well-ordering theorem.

Now suppose the well-ordering theorem and that $A$ is a set with strict partial ordering $\prec$. Then we know that $A$ has a well-ordering, say $<$. Now, for any function $f$ from a section $S_x$ (by $<$) to $P\left(A\right)$, define

Then by the general principle of recursive defamation (Exercise WO.1) there is a unique function $h:A\to P\left(A\right)$ such that $h(\alpha )=\rho (h\upharpoonright S_{\alpha })$ for all $\alpha \in A$.

First we show that, for $\alpha ,\beta \in A$ where $\alpha <\beta$, we have $h(\alpha )\subset h(\beta )$. So consider any $x\in h(\alpha )=\rho (h\upharpoonright S_{\alpha })$, and hence either $x\in \bigcup <!--\; FUNCTION\; APPLICATION\; -->h(S_{\alpha })\cup \left\{\alpha \right\}$ or $x\in \bigcup <!--\; FUNCTION\; APPLICATION\; -->h(S_{\alpha })$. Either way obviously $x\in \bigcup <!--\; FUNCTION\; APPLICATION\; -->h(S_{\alpha })$ so that there is a set $X\in h(S_{\alpha })$ where $x\in X$. Then there is a $\gamma \in S_{\alpha }$ where $X=h(\gamma )$. Since we have $\alpha <\beta$, clearly also $\gamma \in S_{\beta }$ and hence $X\in h(S_{\beta })$. Then also clearly both $x\in \bigcup <!--\; FUNCTION\; APPLICATION\; -->h(S_{\beta })\cup \left\{\beta \right\}$ and $x\in \bigcup <!--\; FUNCTION\; APPLICATION\; -->h(S_{\beta })$ so that for sure $x\in \rho (h\upharpoonright S_{\beta })=h(\beta )$. Since $x$ was arbitrary this shows that $h(\alpha )\subset h(\beta )$ as desired.

Next, we show by transfinite induction that $h(\alpha )$ is simply ordered by $\prec$ for every $\alpha \in A$. So consider $\alpha \in A$ and suppose that $h(\beta )$ is simply ordered by $\prec$ for every $\beta <\alpha$. If $\bigcup <!--\; FUNCTION\; APPLICATION\; -->h(S_{\alpha })\cup \left\{\alpha \right\}$ is simply ordered by $\prec$ then clearly $h(\alpha )$ is since then $h(\alpha )=\rho (h\upharpoonright S_{\alpha })=\bigcup <!--\; FUNCTION\; APPLICATION\; -->h(S_{\alpha })\cup \left\{\alpha \right\}$. So suppose that this is not the case so that $h(\alpha )=\rho (h\upharpoonright S_{\alpha })=\bigcup <!--\; FUNCTION\; APPLICATION\; -->h(S_{\alpha })$. Consider then any $x,y\in h(\alpha )=\bigcup <!--\; FUNCTION\; APPLICATION\; -->h(S_{\alpha })$ where $x\ne y$ so that there are $X$ and $Y$ in $h(S_{\alpha })$ where $x\in X$ and $y\in Y$. Then there is a $\beta$ and $\gamma$ in $S_{\alpha }$ where $X=h(\beta )$ and $Y=h(\gamma )$. If $\beta =\gamma$ then $x$ and $y$ are both in $X=h(\beta )=h(\gamma )=Y$, which is simply ordered by the induction hypothesis so that $x$ and $y$ are comparable in $\prec$. If $\beta <\gamma$ then by what was shown above we have that $x\in X=h(\beta )\subset h(\gamma )$ so that $x$ and $y$ are both in $h(\gamma )$, which is simply ordered by the induction hypothesis so that again $x$ and $y$ are comparable. A similar argument shows that $x$ and $y$ are both in $h(\beta )$ and thus are comparable when $\beta >\gamma$. This completes the induction since $x$ and $y$ are comparable in all cases so that $h(\alpha )$ is always simply ordered.

We then claim that the set $B={\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{\alpha \in A}h(\alpha )$ is a maximal simply ordered (by $\prec$) subset of $A$, which of course shows the maximum principle. First, it is obviously a subset of $A$ since each $h(\alpha )\in P\left(A\right)$ so and so is a subset of $A$. To show that that $B$ is simply ordered by $\prec$, consider $x$ and $y$ in $B$ where $x\ne y$ so that there is an $\alpha$ and $\beta$ in $A$ where $x\in h(\alpha )$ and $y\in h(\beta )$. Without loss of generality, we can assume that $\alpha <\beta$ so that $h(\alpha )\subset h(\beta )$ by what was shown below. Then both $x$ and $y$ are in $h(\beta )$, which is simply ordered by what was shown above. Hence $x$ and $y$ are comparable in $\prec$ so that $B$ is simply ordered.

To show that $B$ is maximal, suppose that $B⊊Z$ and $Z\subset A$ are simply ordered by $\prec$. Then there is a $z\in Z$ where $z\notin B$. Now let $x\in \bigcup <!--\; FUNCTION\; APPLICATION\; -->h(S_z)$ so that there is an $X\in h(S_z)$ where $x\in X$. Then there is an $\alpha \in S_z$ where $x\in X=h(\alpha )$. Hence clearly $x\in B$ so that also $x\in Z$ and so $x$ and $z$ are comparable in $\prec$ since $Z$ is simply ordered. Since $x$ was arbitrary this shows that the set $\bigcup <!--\; FUNCTION\; APPLICATION\; -->h(S_z)\cup \left\{z\right\}$ is simply ordered so that $h(z)=\rho (h\upharpoonright S_z)=\bigcup <!--\; FUNCTION\; APPLICATION\; -->h(S_z)\cup \left\{z\right\}$. However, then we have that $z\in h(z)$ so that $z\in B$, which is a contradiction. So it must be that there is no such set $Z$ and hence $B$ is maximal. □