非可算順序数

1．$W$ を、$D\subseteq\omega$ と $D$ 上の狭義の整列順序 $R\subseteq D\times D$ の対 $\langle D,R\rangle$ の全体とする。$W$ は $\mathcal P(\omega)\times\mathcal P(\omega\times\omega)$ の部分集合なので、分出により集合である。$\langle D,R\rangle\in W$ に、それと順序同型なただ一つの順序数 $\operatorname{type}(D,R)$ を対応させる（順序数 の定理「整列集合の順序数による表現」）。置換により $T:=\{\operatorname{type}(D,R)\mid\langle D,R\rangle\in W\}$ は集合である。
$T$ が可算順序数の全体であることを示す。$\alpha=\operatorname{type}(D,R)$ なら、順序同型 $\alpha\to D$ は $\alpha$ から $\omega$ への単射なので $\alpha$ は可算である。逆に $\alpha$ が可算で $g\colon\alpha\to\omega$ が単射なら、$D:=g[\alpha]$、$R:=\{\langle g(\beta),g(\gamma)\rangle\mid\beta<\gamma<\alpha\}$ とおくと $g$ は $\alpha$ から $\langle D,R\rangle$ への順序同型であり、$\alpha=\operatorname{type}(D,R)\in T$ である。
2．$T$ は推移的である。実際 $\beta\in\alpha\in T$ なら $\beta\subseteq\alpha$ であり、包含写像と $\alpha$ から $\omega$ への単射を合成すれば $\beta$ も可算である。順序数からなる推移的な集合は順序数なので（順序数 の命題「順序数の集まりの整列性と上限」の 2）、$T$ は順序数である。$T$ が可算なら $T\in T$ となるが、どの順序数も自分自身を元にもたない（順序数 の命題「順序数の基本性質」）。よって $T$ は非可算である。順序数 $\alpha$ について $\alpha< T$ は $\alpha\in T$ を意味するので、1 から「$\alpha$ が可算」$\iff\alpha< T$ である。$\alpha$ が非可算なら $\alpha\notin T$ で、順序数は比較可能なので $T\leq\alpha$ である。
3．$\beta<\omega_1$ なら $\beta$ は可算で、$g\colon\beta\to\omega$ が単射のとき $\beta+1=\beta\cup\{\beta\}$ から $\omega$ への単射が $\gamma\mapsto2g(\gamma)$（$\gamma<\beta$）、$\beta\mapsto1$ で得られる。よって $\beta+1<\omega_1$ であり、$\omega_1$ は後続順序数でない。$\omega_1$ が基数であること、すなわち $\beta<\omega_1$ が $\omega_1$ と等濃度にならないことは、$\beta$ が可算で $\omega_1$ が非可算であることから従う。$\omega<\kappa$ となる基数 $\kappa$ が可算だとすると、$\kappa$ は $\omega$ のある無限部分集合と等濃度であり、$\omega$ の無限部分集合は $\omega$ と等濃度なので（小さい順に番号を付ければよい）、$\kappa$ は $\omega<\kappa$ と等濃度になって基数であることに反する。よって $\kappa$ は非可算で、2 により $\omega_1\leq\kappa$ である。
4．$\langle D,R\rangle\in W$ を $\operatorname{type}(D,R)$ に、それ以外の対を $0$ に送る写像は、1 によりこの直積から $\omega_1$ への全射である。$\square$

1．$\sup X=\bigcup X$ である（順序数 の命題「順序数の集まりの整列性と上限」の 3）。$X$ は可算で、その各元は可算順序数すなわち可算集合なので、$\bigcup X$ は可算個の可算集合の和集合であり、可算選択公理のもとで可算である（可算集合 の定理「可算個の可算集合の和集合」）。よって $\sup X<\omega_1$ であり、$\sup X+1<\omega_1$ が $X$ の真の上界になる。
2．$\beta<\omega_1$ と写像 $f\colon\beta\to\omega_1$ をとる。各 $\gamma\in f[\beta]$ に $f(\delta)=\gamma$ となる最小の $\delta<\beta$ を対応させると、$f[\beta]$ から可算集合 $\beta$ への単射になるので（ここでは選択公理を使わない）、$f[\beta]$ は可算である。1 により $f[\beta]$ は上に有界で、$f$ は共終でない。よって $\omega_1$ への共終写像をもつ最小の順序数は $\omega_1$ であり、$\operatorname{cf}(\omega_1)=\omega_1$ である（共終数 の命題「共終写像による特徴付け」）。
3．1 により $\lambda<\omega_1$ である。列は最大の項をもたないので $\lambda$ はどの $\alpha_n$ とも異なり、$\lambda=\gamma+1$ なら $\gamma<\lambda$ を超える $\alpha_n$ があって $\alpha_n\geq\lambda$ となり矛盾するから、$\lambda$ は極限順序数である。$\{\alpha_n\}$ は順序型 $\omega$ の共終な部分集合なので $\operatorname{cf}(\lambda)\leq\omega$ であり、極限順序数 $\lambda$ の共終な部分集合は有限でありえないので $\operatorname{cf}(\lambda)=\omega$ である。$\square$

1．有理数全体の番号付け $q_0,q_1,q_2,\dots$ を一つ固定する（可算集合 の例「有理数全体の可算性」）。$W$ の最大元でない $w\in W$ について、$\{v\in W\mid v>w\}$ は空でないので最小元 $w^+$ をもつ。$w< w^+$ なので、$w< q_n< w^+$ となる $n$ があり（有理数 の稠密性）、その最小のものを $c(w)$ とおく。
$w< w'$ を $W$ の最大元でない二元とすると、$w'$ は $w$ より大きい $W$ の元なので $w^+\leq w'$ であり、
$$ q_{c(w)}< w^+\leq w'< q_{c(w')} $$
となる。よって $c(w)\neq c(w')$ であり、$c$ は $W$ から最大元を除いた集合から $\omega$ への単射である。したがって $W$ は可算である。番号付けと最小の番号を使ったので、選択は行っていない。
2．狭義単調増加な $f$ があれば、$f[\omega_1]$ は $\omega_1$ と順序同型なので $<$ について整列した実数の集合であり、1 により可算である。$f$ は単射なので $\omega_1$ も可算となり、thm-uo-existence に反する。減少の場合は $-f$ を考えればよい。$\square$

値の集合 $V:=f[\omega_1]$ は $<$ について整列している。実際、空でない $U\subseteq V$ に対し $f(\alpha)\in U$ となる最小の $\alpha$ をとると、$f(\beta)\in U$ なら $\beta\geq\alpha$ なので $f(\beta)\geq f(\alpha)$ であり、$f(\alpha)$ は $U$ の最小元である。thm-uo-reals の 1 により $V$ は可算である。
$v\in V$ ごとに $f(\alpha)=v$ となる最小の $\alpha$ を $\alpha_v$ とおく。$v\mapsto\alpha_v$ は単射なので $\{\alpha_v\mid v\in V\}$ は可算であり、thm-uo-bounded の 1 により $\gamma:=\sup_{v\in V}\alpha_v<\omega_1$ である。$\alpha\geq\gamma$ をとり $v:=f(\alpha)$ とすると、$\alpha_v\leq\gamma\leq\alpha$ と単調性から $v=f(\alpha_v)\leq f(\gamma)\leq f(\alpha)=v$ となり、$f(\alpha)=f(\gamma)$ である。減少の場合は $-f$ を考えればよい。$\square$