整列可能定理

thm-wot-main により $X$ 上の整列順序 $\le$ をとる。$(X,\le)$ と順序同型な順序数 $\alpha$ をとれば（上に引いた定理）、その順序同型写像は $X$ から $\alpha$ への全単射である。$\square$

$A\cap B$ の元 $c$ で、$A_{< c}=B_{< c}$ が集合として等しく、かつ $\le_A$ と $\le_B$ がこの集合の上で一致するもの全体を $D$ とする。
段 1：$D$ は $A$ と $B$ の両方の始切片である。 $c\in D$、$b\in A$、$b < _A c$ とする。$b\in A_{< c}=B_{< c}$ なので $b\in B$ かつ $b < _B c$ である。さらに
$$ A_{< b}=\{z\in A_{< c}\mid z < _A b\}=\{z\in B_{< c}\mid z < _B b\}=B_{< b} $$
であり（二つの順序は $A_{< c}=B_{< c}$ の上で一致する）、二つの順序はその部分集合 $A_{< b}$ の上でも一致するので、$b\in D$ である。$A$ と $B$ の役割を入れ替えても同じなので、$D$ は $A$ でも $B$ でも下に閉じている。また $c,c'\in D$ で $c < _A c'$ なら $c\in A_{< c'}=B_{< c'}$ なので $c < _B c'$ であり、二つの順序は $D$ の上で一致する。
段 2：始切片の最初の外の元。 整列集合 $(A,\le_A)$ の下に閉じた部分集合 $D\subsetneq A$ について、$a:=\min(A\setminus D)$ とおくと $A_{< a}=D$ である。実際、$b < _A a$ なら $a$ の最小性により $b\in D$ であり、逆に $b\in D$ なら、$a\le_Ab$ とすると $D$ が下に閉じていることから $a\in D$ となり矛盾するので $b < _A a$ である。
段 3：結論。 $D\neq A$ かつ $D\neq B$ と仮定し、$a:=\min_{\le_A}(A\setminus D)$、$b:=\min_{\le_B}(B\setminus D)$ とおく。段 2 により $A_{< a}=D=B_{< b}$ であるから、定義の条件により
$$ a=g(X\setminus A_{< a})=g(X\setminus D)=g(X\setminus B_{< b})=b $$
となる。すると $a\in A\cap B$ で $A_{< a}=D=B_{< a}$、しかも段 1 により二つの順序は $D$ の上で一致するので $a\in D$ となり、$a\notin D$ に反する。よって $D=A$ または $D=B$ である。$D=A$ なら段 1 により $A$ は $B$ の始切片であり、$D=B$ なら $B$ は $A$ の始切片である。$\square$

$X$ を集合とし、$g$ を上のように固定する。$g$ に沿う整列部分集合の全体 $\mathcal{G}$ は、$\mathcal{P}(X)\times\mathcal{P}(X\times X)$ から条件で取り出した集合である。$W:=\bigcup_{(A,\le_A)\in\mathcal{G}}A$ とおく。
段 1：$W$ 上の順序。 $x,y\in W$ に対し、$x,y$ をともに含むある $(A,\le_A)\in\mathcal{G}$ で $x\le_Ay$ となるとき $x\le_Wy$ と定める。$x\in A$、$y\in B$ なら、lem-wot-comparison により $A\subset B$ か $B\subset A$ なので、$x,y$ をともに含む $\mathcal{G}$ の元がある。同様に $W$ の有限個の元はつねに一つの $(C,\le_C)\in\mathcal{G}$ に含まれる。また $x,y$ が $A$ と $B$ の両方に含まれるとき、補題により一方は他方の始切片なので $x\le_Ay\iff x\le_By$ である。したがって、$x,y$ を含む任意の $(C,\le_C)\in\mathcal{G}$ について $x\le_Wy\iff x\le_Cy$ が成り立つ。反射律・反対称律・推移律・全順序性はいずれも有限個（高々 3 個）の元についての条件なので、それらを含む一つの $\le_C$ の性質から従い、$\le_W$ は $W$ 上の全順序である。
段 2：各 $A$ は $W$ の始切片。 $(A,\le_A)\in\mathcal{G}$、$a\in A$、$w\in W$、$w\le_Wa$ とする。$w,a$ を含む $(C,\le_C)\in\mathcal{G}$ をとる。$C$ が $A$ の始切片なら $w\in C\subset A$ であり、$A$ が $C$ の始切片なら $w\le_Ca$、$a\in A$ から $w\in A$ である。よって $W_{< a}=A_{< a}$ であり、$\le_W$ の $A$ への制限は $\le_A$ である。
段 3：$\le_W$ は整列順序。 $S\subset W$ を空でない部分集合とし、$s\in S$ と $s\in A$ となる $(A,\le_A)\in\mathcal{G}$ をとる。$m:=\min_{\le_A}(S\cap A)$ とおく。$t\in S$ が $t < _W m$ を満たすなら、段 2 により $t\in A$ なので $t\in S\cap A$ かつ $t < _A m$ となり、$m$ の取り方に反する。$\le_W$ は全順序なので $m$ は $S$ の最小元である。
段 4：$W$ も $g$ に沿う。 $w\in W$ とし $w\in A$ となる $(A,\le_A)\in\mathcal{G}$ をとると、段 2 により $W_{< w}=A_{< w}$ なので $g(X\setminus W_{< w})=g(X\setminus A_{< w})=w$ である。よって $(W,\le_W)\in\mathcal{G}$ である。
段 5：$W=X$。 $W\neq X$ と仮定し、$x^\ast:=g(X\setminus W)$ とおく。$x^\ast\notin W$ である。$W^\ast:=W\cup\{x^\ast\}$ に、$W$ の上では $\le_W$、$W$ のすべての元より $x^\ast$ が後になる順序を入れると、これは整列順序である（空でない部分集合は、$W$ と交われば交わりの最小元を、交わらなければ $x^\ast$ を最小元にもつ）。$w\in W$ については $W^\ast_{< w}=W_{< w}$ なので条件は段 4 から従い、$x^\ast$ については $W^\ast_{< x^\ast}=W$ で $g(X\setminus W)=x^\ast$ である。よって $(W^\ast,\le_{W^\ast})\in\mathcal{G}$ であり、$W$ の定義から $W^\ast\subset W$、とくに $x^\ast\in W$ となって矛盾する。
以上により $W=X$ であり、$\le_W$ は $X$ 上の整列順序である。$\square$

$P$ 上の整列順序 $\sqsubseteq$ をとる（$\le$ とは無関係の順序である）。$q\sqsubset p$ は $q\sqsubseteq p$ かつ $q\neq p$ を表し、$q < p$ は $q\le p$ かつ $q\neq p$ を表す。$\sqsubseteq$ に沿った再帰により、部分集合 $C\subset P$ を
$$ p\in C\iff\bigl(q\in C\text{ かつ }q\sqsubset p\text{ となるすべての }q\text{ について }q < p\bigr) $$
で定める。各 $p$ の採否は、$p$ より $\sqsubseteq$ で前の元の採否だけから決まるので、この定義は上の再帰で正当化される。
$C$ は鎖である。実際 $p,p'\in C$、$p\neq p'$ なら、$\sqsubseteq$ が全順序なので $p\sqsubset p'$ としてよく、$p'\in C$ の定義を $q=p$ に当てはめると $p < p'$ である。
仮定により $C$ は上界 $u\in P$ をもつ。$u$ が極大元であることを示す。$u < v$ となる $v\in P$ があったとする。任意の $q\in C$ について $q\le u < v$ なので $q < v$ であり、とくに $q\sqsubset v$ を満たす $q\in C$ についても $q < v$ である。$C$ の定義により $v\in C$ となり、$u$ は $C$ の上界なので $v\le u$ である。これは $u < v$ に反する。よって $u$ は極大元である。$\square$

$V$ 上の整列順序 $\sqsubseteq$ をとる。部分集合 $S\subset V$ の張る部分空間を $\langle S\rangle$ と書く（$\langle\emptyset\rangle=\{0\}$）。$\sqsubseteq$ に沿った再帰により
$$ v\in B\iff v\notin\bigl\langle\{w\in B\mid w\sqsubset v\}\bigr\rangle $$
で $B\subset V$ を定める。
$B$ は線型独立である。そうでないとすると、相異なる $b_1,\ldots,b_n\in B$（$n\ge1$）と $0$ でない $c_1,\ldots,c_n\in K$ で $\sum_ic_ib_i=0$ となるものがある。番号を付け替えて $b_n$ が $\sqsubseteq$ で最も後であるとすると、
$$ b_n=-c_n^{-1}\sum_{i=1}^{n-1}c_ib_i\in\bigl\langle\{w\in B\mid w\sqsubset b_n\}\bigr\rangle $$
となり（$n=1$ なら $b_1=0\in\langle\emptyset\rangle$）、$b_n\in B$ の定義に反する。
$B$ は $V$ を張る。$v\in V$ が $B$ に属さなければ、$B$ の定義により $v\in\langle\{w\in B\mid w\sqsubset v\}\rangle\subset\langle B\rangle$ であり、$v\in B$ なら当然 $v\in\langle B\rangle$ である。よって $\langle B\rangle=V$ であり、$B$ は基底である。$\square$

1. ex-wot-examples の 4 による。部分集合へは包含写像が単射であり、有限集合・可算集合は定義により $\mathbb{N}$ の部分集合へ単射をもつ。
2. $X,Y$ 上の整列順序 $\le_X,\le_Y$ をとる。$X\times Y$ 上で、$(x,y)\preceq(x',y')$ を「$x < _X x'$、または $x=x'$ かつ $y\le_Yy'$」で定める（辞書式順序）。これは全順序であり、空でない $S\subset X\times Y$ に対し、$x_0:=\min\{x\mid(x,y)\in S\text{ となる }y\text{ がある}\}$、$y_0:=\min\{y\mid(x_0,y)\in S\}$ とおけば $(x_0,y_0)$ が $S$ の最小元である。和集合については、$z\in X$ なら $(z,0)$、$z\in Y\setminus X$ なら $(z,1)$ を対応させる写像が $X\cup Y$ から $(X\times\{0\})\cup(Y\times\{1\})$ への単射であり、後者は「第 2 成分を先に比べ、同じなら $\le_X$ または $\le_Y$ で比べる」順序で整列されるので、1 により $X\cup Y$ は整列可能である。いずれの構成も元を選ばない。$\square$