Exercise A0.V.3.07

⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️

We will make use of the notation introduced in 3.06

Definition (complement-choice function)

Given a non-empty set $Z,$ a complement-choice function on $Z$ is a function $\gamma : \mathscr{P}(Z) \setminus \{Z\} \to Z$ such that $\gamma(S) \notin S.$

Definition ($\gamma$-woset)

Given a complement-choice function $\gamma$, a $\gamma$-woset is a well-order relation $\leq$ such that $\operatorname{ground}(\leq) \subseteq \operatorname{cod}(\gamma)$ and for every $s \in \operatorname{ground}(\leq)$ it is the case that $s = \gamma\left(\left\{a \in \operatorname{ground}(\leq)\setminus \{s\} \mid a \leq s \right\}\right).$

Definition (union of $\gamma$-wosets)

Given a complement-choice function $\gamma$ and a family of $\gamma$-wosets $\mathscr{F}$, the union of $\gamma$-wosets $\bigcup \mathscr{F}$ is a relation such that $\operatorname{dom}\left(\bigcup \mathscr{F} \right) = \bigcup_{\leq \in \mathscr{F}} \operatorname{dom}(\leq),$ $\operatorname{cod}\left(\bigcup \mathscr{F} \right) = \bigcup_{\leq \in \mathscr{F}} \operatorname{cod}(\leq),$ and $\operatorname{pairs}\left(\bigcup \mathscr{F} \right) = \bigcup_{\leq \in \mathscr{F}} \operatorname{pairs}(\leq).$

Proposition A

Let $\gamma$ be a complement-choice function. All $\gamma$-wosets agree on their countable initial segment.

Proof

Let $\leq$ and $\leq'$ be two $\gamma$-wosets, and suppose that $\operatorname{ground}(\leq)$ and $\operatorname{ground}(\leq')$ are countable or larger.

We will prove inductively that for any $n \in \mathbb{N},$ the $n$-th least element under $\leq$ is exactly the $n$-th least element under $\leq'.$

If $n = 0$, we are interested in the $\leq$-minimal element $s$ and the $\leq'$-minimal element $s'.$ Note that the set $\left\{a \in \operatorname{ground}(\leq)\setminus \{s\} \mid a \leq s \right\}$ is empty, hence $s = \gamma(\emptyset).$ Similarly, the set $\left\{a \in \operatorname{ground}(\leq')\setminus \{s'\} \mid a \leq s' \right\}$ is empty, thus $s' = \gamma(\emptyset).$ The two minimal elements are equal, as required.

Suppose that $\leq$ and $\leq'$ agree on their $m$-th least elements for all $m$ less than $n.$ Let $s$ be $n$-th least element under $\leq$ and let $s'$ be the $n$-th least element under $\leq'.$ Observe that the set $S_1 = \left\{a \in \operatorname{ground}(\leq)\setminus \{s\} \mid a \leq s \right\}$ contains all elements smaller than the $n$-th least element under $\leq.$ By our inductive hypothesis, this set is identical to the set $S_2 = \left\{a \in \operatorname{ground}(\leq')\setminus \{s'\} \mid a \leq s' \right\},$ containing all elements smaller than the $n$-th least element under $\leq'.$ Since $S_1 = S_2$ it is also the case that $s = \gamma(S_1) = \gamma(S_2) = s'.$

Suppose instead that either $\operatorname{ground}(\leq)$ or $\operatorname{ground}(\leq')$ is finite. In this case, the above inductive argument can be modified in order to prove that the two well-orders agree on the shorter of the two.

Thus $\leq$ and $\leq'$ agree on their countable initial segment.

$\blacksquare$

Lemma L3.4

Let $\gamma$ be a complement-choice function and let $\leq$ and $\leq'$ be two $\gamma$-wosets such that $\operatorname{ground}(\leq) \subseteq \operatorname{ground}(\leq')$ and $\leq$ is a restriction of $\leq'$ to $\operatorname{ground}(\leq).$ Then $\leq \preceq \leq'.$

Proof

Note that our hypothesis includes the first two initial segment conditions. We only need to prove the third.

Since $\leq$ is a restriction of $\leq',$ we will use $\leq'$ exclusively, handling all proof steps dedicated to converting between the two implicitly.

Let $S = \operatorname{ground}(\leq)$ and let $T = \operatorname{ground}(\leq') \setminus S.$ If $T$ is empty, then the third initial segment condition is vacuously satisfied. Suppose instead that $T$ is non-empty, and let $a \in T$ be the $\leq'$-least element.

Suppose, for the sake of contradiction, that there is a $\leq'$-least element $b \in S$ such that $a \leq' b.$ Let $U = \{ z \in \operatorname{ground}(\leq') \setminus \{a\} \mid z \leq' a\}.$ Since $T$ has no elements strictly $\leq'$-smaller than $a,$ $U \subseteq S.$ Then let $V = \{ z \in S \setminus \{b\} \mid z \leq' b\}.$ Note that, by totality of $\leq',$ every element of $V$ is $\leq'$-lesser than $a$ (if $z \in S$ is strictly $\leq'$-lesser than $b$ and yet $a \leq' z$, then minimality of $b$ is violated), so $V \subseteq U.$ At the same time, $U$ is a subset of $S$ and each element of $U$ is $\leq'$-lesser than $a,$ hence $U \subseteq V.$ Thus $U = V,$ yet $\gamma(U) = a$ while $\gamma(V) = b,$ which contradicts $a \in T.$

Thus, every element of $S$ is $\leq'$-lesser than every element of $T.$

$\blacksquare$

Lemma L3.5

Let $\gamma$ be a complement-choice function. A union of a non-empty $\preceq$-chain $\ell$ of $\gamma$-wosets is a $\gamma$-woset.

Proof

Let $\leq$ be the union of $\ell.$ If $\operatorname{ground}(\leq)$ is empty, then $\leq$ is vacuously a $\gamma$-woset. Suppose otherwise.

Let $T$ be any finite non-empty subset of $\operatorname{ground}(\leq).$ For each element $t \in T,$ select an element $\leq_t \in \ell$ such that $t \in \operatorname{ground}(\leq_t).$ Since $\preceq$ is a total order on the finite set $U = \{ \leq_t \in \ell \mid t \in T \}$, there exists $\preceq$-maximal element $\leq_m \in U.$ Since $\preceq$-maximality induces maximality by inclusion of ground sets, $\operatorname{ground}(\leq_t) \subseteq \operatorname{ground}(\leq_m).$

Since $\operatorname{pairs}(\leq_m) \subseteq \operatorname{pairs}(\leq),$ $\leq$ is a transitive reflexive relation on $T.$ Suppose $a, b \in T,$ and $(a \leq b) \land (b \leq a).$ Since $\leq_m$ is a well-order on $T,$ either $a = b$ and we are done, or one of $\{a \leq_m b, b \leq_m a\}$ fails to hold.

Suppose $a \leq_m b$ fails to hold, and let $\leq_1$ be any $\gamma$-woset in $\ell$ such that $a,b \in \operatorname{ground}(\leq_1)$ and $a \leq_1 b.$ If $\leq_1 \preceq \leq_m,$ then restriction $\leq_m$ to $\operatorname{ground}(\leq_1)$ would make it equivalent to $\leq_1$ and hence $a \leq_m b$ has to hold, which is contradictory. If instead $\leq_m \preceq \leq_1,$ restricting $\leq_1$ to $\operatorname{ground}(\leq_m)$ makes $\leq_1$ equivalent to $\leq_m$ but then $a \leq_m b$ has to hold by equivalence, which is also contradictory.

Suppose instead $b \leq_m a$ fails to hold. The case analysis here is analogous to the above.

Thus, we have ruled out all cases except $a = b,$ proving $\leq$ antisymmetric on $T.$ A relation that is a partial order on any finite subset of its ground set is necessarily a partial order on its whole ground set.

Suppose, for the sake of contradiction, $a, b \in \operatorname{ground}(\leq)$ and that neither $a \leq b$ nor $b \leq a$ holds. Take any relation $\leq_\tau \in \ell$ such that $a \in \operatorname{ground}(\leq_\tau).$ If $b \notin \operatorname{ground}(\leq_\tau)$ then any relation $\leq_\sigma \in \ell$ such that $b \in \operatorname{ground}(\leq_\sigma)$ has to be $\preceq$-greater than $\leq_\tau$ (since for $\preceq$-lesser relations, the ground set is a subset of $\operatorname{ground}(\leq_\tau)$) but then the third initial segment condition forces $a \leq b,$ a contradiction. So $a, b \in \operatorname{ground}(\leq_\tau)$ and the totality of $\leq_\tau$ forces one of the two inequalities to hold. Thus, $\leq$ is total.

Let $T$ be any non-empty subset of $\operatorname{ground}(\leq).$ Let $t \in T$ and let $\leq_t$ be any element of $\ell$ such that $t \in \operatorname{ground}(\leq_t).$ Let $S = T \cap \operatorname{ground}(\leq_t)$ and note that $S$ has a $\leq_t$-minimal element, say $s \in S.$

Suppose, for the sake of contradiction, that $s' \in T$ is distinct from $s$ and $s' \leq s.$ This can only be the case if there exists $\leq_t' \in \ell$ such that $s, s' \in \operatorname{ground}(\leq_t')$ and $s' \leq_t' s.$

If $\leq_t' \preceq \leq_t,$ then $\operatorname{ground}(\leq_t') \subseteq \operatorname{ground}(\leq_t).$ But then $s, s' \in \operatorname{ground}(\leq_t)$ and restriction forces $s' \leq_t s,$ which contradicts $\leq_t$-minimality of $s.$ Suppose instead that $\leq_t \preceq \leq_t'.$ If $s' \in \operatorname{ground}(\leq_t') \setminus \operatorname{ground}(\leq_t)$ then the third initial segment condition requires $s \leq s',$ which implies $s = s',$ contradicting distinctness. Instead, $s' \in \operatorname{ground}(\leq_t),$ but then $s \leq_t' s'$ has to hold by $\leq_t$-minimality of $s$ and restriction of $\leq_t'$ to $\operatorname{ground}(\leq_t).$

Thus, $s$ is the $\leq$-minimal element of $T.$ Hence, $\leq$ is a well-order.

Finally, let $a \in \operatorname{ground}(\leq).$ Take any $\leq_a \in \ell$ such that $a \in \operatorname{ground}(\leq_a).$ Let $A = \{ z \in \operatorname{ground}(\leq_a) \setminus \{a\} \mid z \leq_a a\}$ and let $B = \{ z \in \operatorname{ground}(\leq) \setminus \{a\} \mid z \leq a\}.$ Since $\leq_a$ is a $\gamma$-woset, it is the case that $a = \gamma(A).$ Since $z \leq_a a$ implies, by inclusion of pairs in the union, $z \leq a,$ $A \subseteq B.$ We want to show $B \subseteq A.$

Suppose, for the sake of contradiction, that $z \in \operatorname{ground}(\leq) \setminus \{a\}$ such that $z \leq a$ and $z \notin A.$ Then there has to be a relation $\leq_b \in \ell$ such that $z \leq_b a.$ If $\leq_b \preceq \leq_a$ then, by restriction to $\operatorname{ground}(\leq_b),$ $z \leq_a a,$ which is contradictory. Suppose instead $\leq_a \preceq \leq_b.$

If $z \notin \operatorname{ground}(\leq_a)$ then $z \in \operatorname{ground}(\leq_b) \setminus \operatorname{ground}(\leq_a)$ and is thus $\leq_b$-larger than $a$ by the third initial segment condition, a contradiction. So $z \in \operatorname{ground}(\leq_a)$ and so it must be $z \not\leq_a a$ and, by restriction to $\operatorname{ground}(\leq_a),$ $z \not\leq_b a.$ This is also a contradiction.

This proves $B \subseteq A,$ hence $B = A$ and $a = \gamma(B),$ which is sufficient for $\leq$ to be a $\gamma$-woset.

$\blacksquare$

Lemma L3.6.1

Let $\leq$ be a total order and let $A$ and $B$ be two downward closed subsets of $\operatorname{ground}(\leq).$ Then either $A \subseteq B$ or $B \subseteq A.$

Proof

Suppose neither is a subset of the other. Then let $x \in A \setminus B$ and $y \in B \setminus A.$

If $x \leq y,$ then, by downward closure, $x \in B.$ A contradiction. Suppose instead $y \leq x.$ Then downward closure forces $y \in A,$ which is also a contradiction. Thus one must be a subset of the other.

$\blacksquare$

Lemma L3.6

Let $\gamma$ be a complement-choice function. Let $\leq$ and $\leq'$ be two $\gamma$-wosets. Then there exists a $\gamma$-woset $\leq_c$ such that $\leq_c$ is $\preceq$-maximal among the $\gamma$-wosets that are initial segments of both $\leq$ and $\leq'.$

Proof

Let $\mathscr{S}$ be the family of all $\gamma$-wosets $\preceq$-lesser than both $\leq$ and $\leq'.$

Fix $\leq_a, \leq_b \in \mathscr{S}.$ Since ground sets of both are downward-closed subsets of $\operatorname{ground}(\leq),$ either $\operatorname{ground}(\leq_a) \subseteq \operatorname{ground}(\leq_b)$ or $\operatorname{ground}(\leq_b) \subseteq \operatorname{ground}(\leq_a)$ (by lemma 3.6.1).

Without loss of generality, assume $\operatorname{ground}(\leq_a) \subseteq \operatorname{ground}(\leq_b).$ Observe that restricting $\leq$ to $\operatorname{ground}(\leq_b)$ and then to $\operatorname{ground}(\leq_a)$ is equivalent to restricting $\leq$ directly to $\operatorname{ground}(\leq_a).$ But the restriction of $\leq$ to $\operatorname{ground}(\leq_b)$ is $\leq_b.$ Thus $\leq_b$ restricts to $\operatorname{ground}(\leq_a),$ producing $\leq_a.$

By lemma 3.4 this is sufficient to show $\leq_a \preceq \leq_b.$

This $\mathscr{S}$ is a chain under $\preceq,$ and, by lemma 3.5, its union $\leq_c$ is a $\gamma$-woset. No member of a union can be greater by inclusion than the union itself, and hence no element of $\mathscr{S}$ has a ground set such that $\operatorname{ground}(\leq_c)$ is a proper subset. This $\leq_c$ is indeed $\preceq$-maximal.

$\blacksquare$

Lemma L3.7

Let $\gamma$ be a complement-choice function. The initial segment relation $\preceq$ is in fact a total order on $\gamma$-wosets.

Proof

Let $\leq$ and $\leq'$ be two $\gamma$-wosets. Suppose, for the sake of contradiction, that neither is an initial segment of the other. If either of the two is empty, then it is the initial segment of the other. Thus, we assume that they are both non-empty.

Let $\leq_c$ be the maximal common initial segment of $\leq$ and $\leq',$ guaranteed to exist by lemma 3.6. Let $O = \operatorname{ground}(\leq_c).$ Note that $O$ is downward closed under $\leq$ and $\leq',$ since being $\preceq$-lesser than both $\leq$ and $\leq'$ makes it a restriction of both of these relations.

If $\operatorname{ground}(\leq) \subseteq O$ or $\operatorname{ground}(\leq') \subseteq O,$ then one of the $\gamma$-wosets is an initial segment of the other, by lemma 3.4. This leads to a contradiction. Suppose otherwise, and let $a \in \operatorname{ground}(\leq)$ be the $\leq$-least element of $\operatorname{ground}(\leq) \setminus O,$ and let $b \in \operatorname{ground}(\leq')$ be the $\leq'$-least element of $\operatorname{ground}(\leq') \setminus O.$

Since $O$ is the set of all elements of $\operatorname{ground}(\leq)$ that are $\leq$-lesser than $a,$ the $\gamma$-woset condition forces $\gamma(O) = a.$ But also, since $O$ is the set of all elements of $\operatorname{ground}(\leq')$ that are $\leq'$-lesser than $b,$ the $\gamma$-woset condition forces $\gamma(O) = b.$ Thus $a = b$ is the element of both orders coming directly after all of $O.$ Thus, the two orders agree on $a$ as well, but $a \notin O.$ This contradicts maximality of $O$.

$\blacksquare$

Lemma L3.8

Let $\gamma$ be a complement-choice function. Then there exists $\preceq$-maximal $\gamma$-woset $\leq_M.$

Proof

By lemma 3.5, a union of a $\preceq$-chain of $\gamma$-wosets is a $\gamma$-woset, by definition, its ground set is the union of the ground sets of all $\gamma$-wosets in the family. Since $\preceq$ is a total order on the set $\mathscr{F}$ of all $\gamma$-wosets, we can fix $\leq_M$ to be the union of $\mathscr{F}.$

Suppose there exists a $\preceq$-greater $\gamma$-woset $\leq_M'.$ Then $\operatorname{ground}(\leq_M') \subseteq \operatorname{ground}(\leq_M)$ since $\operatorname{ground}(\leq_M)$ is the union of all ground sets of $\gamma$-wosets, including $\leq_M'.$ Since $\leq_M \preceq \leq_M',$ it is also the case that $\operatorname{ground}(\leq_M) \subseteq \operatorname{ground}(\leq_M').$ Thus the two wosets have the same ground set, and the restriction condition of $\preceq$ forces them to be identical.

Thus, $\leq_M$ is the $\preceq$-maximal $\gamma$-woset.

$\blacksquare$

Lemma L3.9

Let $\gamma$ be a complement-choice function and let $\leq$ be a $\gamma$-woset such that $\operatorname{ground}(\leq) \subsetneq \operatorname{cod}(\gamma)$. Then there exists a $\preceq$-greater $\gamma$-woset $\leq'.$

Proof

Indeed, let $s = \gamma(\operatorname{ground}(\leq)).$ Then define $u \leq' v$ if and only if either $v = s$ or $u, v \in \operatorname{ground}(\leq)$ and $u \leq v.$

Let $u \in \operatorname{ground}(\leq').$ If $u = s,$ then by definition $u \leq' u.$ Otherwise, $u \in \operatorname{ground}(\leq)$ and $u \leq u \equiv u \leq' u.$ Thus $\leq'$ is reflexive.

Suppose $u \leq' v$ and $v \leq' u.$ If $u = s$ or $v = s,$ then necessarily $u = v,$ since $s$ is $\leq'$-maximal. Otherwise, we can use antisymmetry of $\leq.$ Thus $\leq'$ is antisymmetric.

Suppose $u, v, w \in \operatorname{ground}(\leq')$ such that $u \leq' v$ and $v \leq' w.$ If $w = s,$ then $u \leq' w$ by definition. If $v = s,$ then maximality of $s$ forces $w = s$ and hence $u \leq' w.$ If $u = s,$ then maximality of $s$ forces $v = s$ and $w = s$ and then $u \leq' w.$ If $u, v, w \in \operatorname{ground}(\leq),$ then transitivity follows by restriction to $\leq.$ Thus $\leq'$ is transitive.

Suppose, for the sake of contradiction, that neither $u \leq' v$ nor $v \leq' u$ hold. If either $u = s$ or $v = s,$ at least one of the inequalities hold by maximality of $s.$ If neither $u = s$ nor $v = s,$ then $u, v \in \operatorname{ground}(\leq)$ and by totality of $\leq$ one of our inequalities must hold, leading to contradiction. Thus $\leq'$ is total.

Let $T \subseteq \operatorname{ground}(\leq')$ be non-empty. If $T$ is a singleton, every total order is a well-ordering of $T$ and restriction of $\leq'$ to $T$ is a total order. Suppose $T$ is not a singleton. Then $T' = T \setminus \{s\}$ is non-empty. Since $T' \subseteq \operatorname{ground}(\leq),$ $\leq'$ restricts to $\leq$ on $T'$ and $\leq$ is a well-order. Thus, $\leq'$ well-orders $T.$

This proves that $\leq'$ is a well-order.

Note that $\operatorname{ground}(\leq') = \operatorname{ground}(\leq) \cup \{s\} \subseteq \operatorname{cod}(\gamma).$ Since $s$ is $\leq'$-maximal, the set $U = \{z \in \operatorname{ground}(\leq') \setminus \{s\} \mid z \leq' s\}$ is exactly $\operatorname{ground}(\leq).$ Since $s = \gamma(\operatorname{ground}(\leq)),$ $\leq'$ satisfies the main $\gamma$-woset condition. Thus $\leq'$ is a $\gamma$-woset.

It is clear that $\operatorname{ground}(\leq) \subseteq \operatorname{ground}(\leq').$ By construction, $\leq'$ restricts to $\leq$ on $\operatorname{ground}(\leq)$ and since $\{s\} = \operatorname{ground}(\leq') \setminus \operatorname{ground}(\leq),$ the third condition of the initial segment relation is satisfied, as $s$ is the $\leq'$-greatest element. Thus, $\leq \preceq \leq'.$

$\blacksquare$

Proposition B

The Axiom of Choice implies the Well-ordering Principle.

Proof

Let $Z$ be a non-empty set. The axiom of choice lets us select a single element of $Z \setminus S$ for each proper subset $S \subseteq Z,$ defining a complement-choice function $\gamma$ on $Z.$

By lemma 3.8 there exists $\preceq$-maximal $\gamma$-woset $\leq_M.$

Suppose, for the sake of contradiction, that $\operatorname{ground}(\leq_M) \subsetneq Z.$ Then by lemma 3.9 there exists $\preceq$-greater $\gamma$-woset $\leq_M'.$ This contradicts $\preceq$-maximality of $\leq_M.$

Thus, $\operatorname{ground}(\leq_M) = Z,$ and hence $Z$ is well-ordered.

$\blacksquare$