Hartogs数

集合であること。 $\mathrm{WO}(X)$ は $\mathcal{P}(X)\times\mathcal{P}(X\times X)$ の元のうち「$R\subset A\times A$ が $A$ の狭義整列順序である」という論理式を満たすものを分出公理で集めた集合である。各 $(A,R)$ に $\operatorname{type}(A,R)$ を対応させる規則は論理式で書けて値がただ一つなので、置換公理（ZFC公理系の「公理の一覧」節）により $H(X)$ は集合である。
1。 $\alpha\in H(X)$ なら、ある $(A,R)\in\mathrm{WO}(X)$ と順序同型写像 $f\colon\alpha\to A$ がある。$f$ と包含写像 $A\hookrightarrow X$ の合成は $\alpha$ から $X$ への単射である。逆に単射 $j\colon\alpha\to X$ があれば、$A:=j[\alpha]$ とし、$A$ 上の関係 $R$ を $j(\beta)\,R\,j(\gamma):\iff\beta<\gamma$ で定める。$R\subset A\times A$ は分出公理で作れる集合で、$j$ は $(\alpha,<)$ から $(A,R)$ への順序同型写像になるから、$R$ は $A$ の整列順序で $\operatorname{type}(A,R)=\alpha$ である。よって $\alpha\in H(X)$。
2。 $H(X)$ は順序数からなる集合である。$\alpha\in H(X)$、$\beta<\alpha$ とすると、$\beta\subset\alpha$ なので 1 による単射 $\alpha\to X$ を $\beta$ に制限すれば $\beta\preceq X$、再び 1 より $\beta\in H(X)$ である。したがって $H(X)$ は推移的集合であり、順序数の「性質」節の命題「順序数の集まりの整列性と上限」の 2 により順序数である。
3。 順序数は自分自身の元でないので $H(X)\notin H(X)$、1 により $H(X)\not\preceq X$ である。一方 $\beta< H(X)$、すなわち $\beta\in H(X)$ なら 1 により $\beta\preceq X$ である。よって $H(X)$ は $X$ へ単射で写せない最小の順序数であり、$h(X)=H(X)$。$\square$

1。 $\beta< h(X)$ と全単射 $g\colon h(X)\to\beta$ があれば、$\beta\preceq X$ による単射 $j\colon\beta\to X$ と合成して $j\circ g\colon h(X)\to X$ は単射になり、定義に反する。
2。 単射 $i\colon X\to Y$ をとる。$\alpha\preceq X$ なら単射の合成で $\alpha\preceq Y$ なので、thm-hartogs-existence の 1 により $h(X)=H(X)\subset H(Y)=h(Y)$、順序数では包含は $\le$ を意味する。対等なら両向きの単射があるので等号になる。
3。 $X$ と $n$ は対等で、2 により $h(X)=h(n)$ である。$m\le n$ なら $m\subset n$ なので $m\preceq n$。一方 $n+1\not\preceq n$ は鳩の巣原理（基数の「性質」節の命題「有限基数と $\omega$」の 1）である。$n+1$ より大きい順序数は $n+1$ を部分集合に含むので、やはり $n$ へ単射で写らない。よって $h(n)=n+1$。
4。 2 により $h(X)=h(\kappa)$ である。$\kappa\preceq\kappa$ だから $\kappa< h(\kappa)$ であり、1 により $h(\kappa)$ は $\kappa$ より大きい基数である。逆に $\mu$ を $\kappa<\mu$ である基数とする。$\mu\preceq\kappa$ と仮定すると、$\kappa\subset\mu$ による単射と合わせて 基数の「性質」節の定理「Cantor–Bernstein の定理：単射の往復から全単射」（選択公理を使わない）により $\mu\approx\kappa$ となり、$\mu$ が基数であることに反する。よって $\mu\not\preceq\kappa$ で、$h(\kappa)\le\mu$。したがって $h(\kappa)$ は $\kappa$ より大きい最小の基数である。$\kappa=\omega$ のとき、これは最小の非可算順序数 $\omega_1$ である。
5。 単射 $j\colon X\to h(X)$ があれば、$x\prec y:\iff j(x)< j(y)$ は $X$ の整列順序である（順序数 $h(X)$ の部分集合の整列順序を引き戻したもの）。逆に $X$ が整列可能なら $X\approx\kappa$ となる順序数 $\kappa$ があり、$\kappa\preceq X$ だから $\kappa< h(X)$、つまり $\kappa\subset h(X)$ で、$X\approx\kappa\preceq h(X)$ である。
6。 $\mathrm{WO}(X)\subset\mathcal{P}(X)\times\mathcal{P}(X\times X)$ である。$\alpha< h(X)$ に $C_\alpha:=\{(A,R)\in\mathrm{WO}(X)\mid\operatorname{type}(A,R)=\alpha\}$ を対応させる。thm-hartogs-existence の定義から各 $C_\alpha$ は空でなく、$\alpha\neq\beta$ なら $C_\alpha\cap C_\beta=\emptyset$ なので $C_\alpha\neq C_\beta$ である。よって $\alpha\mapsto C_\alpha$ は求める単射である。この対応は論理式で一つに決まり、選ぶ操作を含まない。$\square$

$x\in X$ を固定し、「行」$\{x\}\times\kappa$ の像を見る。
ある $x$ の行がすべて $X$ の側に入る場合。 すべての $\alpha<\kappa$ について $g(x,\alpha)\in\{0\}\times X$ となる $x$ があるとする。$g(x,\alpha)=(0,y_\alpha)$ と書くと、$g$ が単射なので $\alpha\mapsto y_\alpha$ は $\kappa$ から $X$ への単射であり、$\kappa=h(X)$ の定義に反する。したがってこの場合は起こらない。
どの $x$ の行も $\kappa$ の側に触れる場合。 各 $x\in X$ について $g(x,\alpha)\in\{1\}\times\kappa$ となる $\alpha<\kappa$ が存在する。そのような $\alpha$ の最小のものを $\alpha_x$ とし（順序数の空でない集合の最小元なので選択は要らない）、$g(x,\alpha_x)=(1,\gamma_x)$ と書く。$x\neq x'$ なら $(x,\alpha_x)\neq(x',\alpha_{x'})$ なので、$g$ の単射性から $\gamma_x\neq\gamma_{x'}$ である。よって $x\mapsto\gamma_x$ は $X$ から $\kappa$ への単射である。prop-hartogs-basic の 5 の証明と同じく、この単射で $\kappa$ の順序を引き戻せば $X$ は整列される。$\square$

1 ⇒ 2。 選択公理のもとで $Y$ は整列可能（整列可能定理）なので、ある無限基数 $\kappa$ と対等である。基数の「性質」節の定理「無限基数の平方」により $\kappa\times\kappa\approx\kappa$、したがって $Y\times Y\approx Y$。
2 ⇒ 1。 任意の集合 $X$ が整列可能であることを示せばよい。整列可能定理から選択公理が従うことは 選択公理の「性質」節の定理「整列可能定理との同値」の (2 ⇒ 1) で示されている。$X$ が有限なら整列可能である。$X$ が無限のとき、$\kappa:=h(X)$ とおき $Y:=X\sqcup\kappa$ とする。$Y$ は無限集合 $\{0\}\times X$ を含むので無限であり、仮定 2 により全単射 $e\colon Y\times Y\to Y$ がある。$(x,\alpha)\mapsto\bigl((0,x),(1,\alpha)\bigr)$ は $X\times\kappa$ から $Y\times Y$ への単射であり、$e$ と合成すると $X\times\kappa$ から $Y=X\sqcup\kappa$ への単射 $g$ が得られる。lem-hartogs-tarski により $X$ は整列可能である。$\square$