ここでは選択公理 $($公理1.2.14$)$ から導出される重要な事実であるZornの補題と整列定理について紹介します。また、その応用として集合の濃度についての基礎的な事実をまとめます。
選択公理 $($公理1.2.14$)$ を認めることで従う、応用上非常に重要なZornの補題を紹介します。一つだけ用語の準備として、順序集合が帰納的順序集合 $($inductive ordered set$)$ であるということを、その任意の全順序部分集合が上に有界であることとして定義します。
帰納的順序集合は少なくとも $1$ つ極大元を持つ。つまり、順序集合 $(X, \leq)$ に対してその任意の全順序部分集合が上界を持つならば $(X, \leq)$ は少なくとも $1$ つ極大元を持つ。
$X$ の全順序部分集合全体からなる集合族を $\mathcal{A}$ と定め、各 $A\in \mathcal{A}$ に対して $\hat{A}$ により部分集合 $\{x\in X\mid {}^{\forall}a\in A, \ a < x\}$ を表すとします$A$ の上界全体からなる集合を $U(A)$ で表すとして $\hat{A} = U(A)\setminus A$ です。よって、$\hat{A}\neq \varnothing$ であればその元 $1$ つを $A$ に付け加えることで $A$ より真に大きな全順序部分集合が得られます。。また、\[\mathcal{A}' := \{A\mid A\in \mathcal{A}, \ \hat{A}\neq \varnothing\},\]\[\mathcal{B} := \{\hat{A}\mid A\in \mathcal{A}'\}\]と定め、選択公理 $($公理1.2.14$)$ より選択関数 $\varphi : \mathcal{B}\to X : B\mapsto \varphi(B)\in B$ を取ります。$X$ の全順序部分集合 $K$ であって次の条件を満たすもの全体を $\mathcal{K}$ とおきます。
次のことを示しますあらかじめ言っておくと、各 $K\in \mathcal{K}$ はこのあと紹介する整列集合 $($定義1.4.3$)$ になり、$\mathcal{K}$ はある $1$ つの整列部分集合とその切片全体からなります。。
(step 1) $A\in \mathcal{A}$ が $A\subset K\sqcup \{\varphi(\hat{K})\}$ かつ $(K\sqcup \{\varphi(\hat{K})\})\cap \hat{A}\neq \varnothing$ を満たすとします。もし $\varphi(\hat{K})\in A$ とすると、$\max(K\sqcup \{\varphi(\hat{K})\}) = \varphi(\hat{K})$ と $\hat{A}$ の定義から $x\in (K\sqcup \{\varphi(\hat{K})\})\cap \hat{A}$ に対して $x\leq \varphi(\hat{K}) < x$ となって矛盾するので $\varphi(\hat{K})\notin A$ であり、$A\subset K$ が分かります。
次のそれぞれに対して $\min ((K\sqcup \{\varphi(\hat{K})\})\cap \hat{A}) = \varphi(\hat{A})$ を示せばよいです。
(a) $K\in \mathcal{K}$ かつ $A\subset K$ かつ $K\cap \hat{A}\neq \varnothing$ なので $\min (K\cap\hat{A}) = \varphi(\hat{A})$ であり、$\hat{K}$ の定義から $\min (K\cap \hat{A}) < \varphi(\hat{K})$ なので $\min ((K\sqcup \{\varphi(\hat{K})\})\cap \hat{A}) = \min (K\cap \hat{A}) = \varphi(\hat{A})$ です。
(b) $K\cap \hat{A} = \varnothing$ のときは $(K\sqcup \{\varphi(\hat{K})\})\cap \hat{A} = \{\varphi(\hat{K})\}$ なので $\min((K\sqcup \{\varphi(\hat{K})\})\cap \hat{A}) = \varphi(\hat{K})$ です。よって、$\hat{A} = \hat{K}$ を示せばよいですが、$A\subset K$ よりただちに $\hat{K}\subset \hat{A}$ が分かるので、その逆の包含関係を示せばよいです。$\hat{a}\in \hat{A}$ とします。$K\cap \hat{A} = \varnothing$ は $k\in K$ であって任意の $a\in A$ に対して $a < k$ となるものが存在しないという意味であり、つまり、任意の $k\in K$ に対してある $a\in A$ が存在して $k\leq a$ となります。よって、任意の $k\in K$ に対してそのような $a\in A$ を取れば $k\leq a < \hat{a}$ であり、$\hat{a}\in \hat{K}$ です。よって、$\hat{A}\subset \hat{K}$ も分かり、$\hat{A} = \hat{K}$ です。
(step 2) $k'\in K'\setminus K$ を取ります。$A := \{x\in K\cap K'\mid x < k'\}$ と定めるとき、当然 $A\subset K'$ かつ $k'\in K'\cap \hat{A}$ なので $\varphi(\hat{A}) = \min (K'\cap \hat{A})\in K'$ であり、$\varphi(\hat{A})\leq k'$ です。
もし $K\cap \hat{A}\neq \varnothing$ とすると、$A\subset K$ と合わせて $\varphi(\hat{A}) = \min (K\cap \hat{A})\in K$ ですが、$k'\notin K$ と $\varphi(\hat{A})\leq k'$ から $\varphi(\hat{A}) < k'$ なので $\varphi(\hat{A})\in K\cap K'$ と合わせて $\varphi(\hat{A})\in A$ が従い、$\varphi(\hat{A})\in \hat{A} = U(A)\setminus A$ に矛盾します。よって、$K\cap \hat{A} = \varnothing$ であり、任意の $k\in K$ に対してある $a\in A$ が存在して $k\leq a$ となります。任意の $a\in A$ に対して $a < k'$ なので、任意の $k\in K$ に対して $k < k'$ であり、$k'\in \hat{K}$ です。以上より $K'\setminus K\subset \hat{K}$ が示されました。
(step 3) 仮に $K'\setminus K\neq \varnothing$ かつ $K\setminus K'\neq \varnothing$ であったとして $k'\in K'\setminus K$ と $k\in K\setminus K'$ を取ると(step 2)から $k < k' < k$ となって矛盾します。よって、$K'\setminus K = \varnothing$ または $K\setminus K' = \varnothing$、つまり、$K'\subset K$ または $K\subset K'$ です。
(step 4) $\tilde{K}$ が全順序部分集合であることは容易。$A\in \mathcal{A}$ が $A\subset \tilde{K}$ かつ $\tilde{K}\cap \hat{A}\neq \varnothing$ を満たしているとします。$k\in \tilde{K}\cap \hat{A}$ を取り、$k\in K$ となる $K\in \mathcal{K}$ を取ります。もし $A\setminus K\neq \varnothing$ とすると $a\in A\setminus K$ に対して $a\in K'$ となる $K'\in \mathcal{K}$ を取ることで $a\in K'\setminus K\subset \hat{K}$ から $k < a$ が従い、$k\in \hat{A}$ に矛盾するので $A\setminus K = \varnothing$、つまり、$A\subset K$ です。
いま、$A\subset K$ かつ $K\cap \hat{A}\neq \varnothing$ なので $\min (K\cap \hat{A}) = \varphi(\hat{A})\in K$ です。任意の $\tilde{k}\in \tilde{K}\setminus K$ に対して $\varphi(\hat{A}) < \tilde{k}$ なので $\min(\tilde{K}\cap \hat{A}) = \min(K\cap \hat{A}) = \varphi(\hat{A})$ です。以上で $\tilde{K}\in \mathcal{K}$ が示されました。
(step 5) もし $\tilde{K}\in \mathcal{A}'$ とすると(step 1)から $\tilde{K}\sqcup \{\varphi(\hat{\tilde{K}})\}\in \mathcal{K}$ であり、$\tilde{K}$ の定義から $\varphi(\hat{\tilde{K}})\in \tilde{K}$ ですがこれは矛盾。よって、$\tilde{K}\notin \mathcal{A}'$、つまり、$\hat{\tilde{K}} = \varnothing$ です。
$\tilde{k}$ を $\tilde{K}$ の上界とします。もし $\tilde{k} < x$ となる $x\in X$ が存在すると $x\in \hat{\tilde{K}} = \varnothing$ となり矛盾するのでそのような $x\in X$ は存在せず、$\tilde{k}$ は $X$ の極大元です。
$X$ が帰納的順序集合なので全順序部分集合である $\tilde{K}$ には上界が存在し、よって、$X$ には極大元が存在します。
順序集合 $\mathcal{S}$ について、これが帰納的順序集合であることは次の $2$ つの条件を満たすこと同値です。
非常に細かい注意ですが、与えられた順序集合が帰納的順序集合であることを確認する際に、全順序部分集合に対する上界の存在を示す議論を空集合に対して適用できない場合もあり、その場合の証明はこの $2$ つを確認する形を取ります。(全体集合が空じゃないから空集合に自明に上界が存在する、ということまで言わないというだけのことです。まあ、そもそも空集合のことまで気を遣わず適当に済ますことも多いですが…)
整列集合を定義します。
整列集合に関する基本的な性質として次が挙げられます。
$(X, \leq_{X}), (Y, \leq_{Y})$ を整列集合とする。
(1) 任意の空でない部分集合 $B\subset A$ に対して $\leq_{X}$ に関する最小元が $\leq_{A}$ に関する最小元です。
(2) 定義より $X\langle x\rangle^{c} = \{x'\in X\mid x' <_{X} x\}^{c} = \{x'\in X\mid x\leq_{X} x'\}$ です。明らかに $x\in X\langle x\rangle^{c}$ であり、$\min X\langle x\rangle^{c} = x$ です。
(3) $A\neq X$ の場合に $A = X\langle\min A^{c}\rangle$ であることを示します。$a\in A$ とすると $A$ に課した仮定から任意の $x\in X$ に対して $x\notin A\Rightarrow a < x$ であるので、$\min A^{c}\notin A$ より $a < \min A^{c}$ となり $a\in X\langle\min A^{c}\rangle$ です。よって、$A\subset X\langle\min A^{c}\rangle$ です。$X\langle\min A^{c}\rangle\subset A$ は明らかです。
(4) $\varphi, \psi : X\to Y$ を順序同型写像とします。$\varphi\neq \psi$ として矛盾を導きます。$A := \{x\in X\mid \varphi(x)\neq \psi(x)\}$ とすれば、$\varphi\neq \psi$ より $A\neq \varnothing$ なので $a := \min A$ が取れます。$\varphi(a)\neq \psi(a)$ です。対称性より $\varphi(a) < \psi(a)$ として矛盾を導けば十分です「一般性を失わずに $\varphi(a) < \psi(a)$ としてよい。」という言い回しがされることも。つまりは、$\psi(a) < \varphi(a)$ の場合も全く同じ議論が通用するので省略しますと言ってるだけです。。
$\psi$ は全射なので、ある $b\in X$ であって $\psi(b) = \varphi(a)$ となるものが取れますが、もし $b < a$ とすると $a = \min A$ としていたことから $\varphi(b) = \psi(b) = \varphi(a)$ であり、$\varphi$ の単射性から $a = b$ となり矛盾。もし $a = b$ ならば $\varphi(a) = \psi(b) = \psi(a)$ であり $\varphi(a)\neq \psi(a)$ に矛盾。もし $a < b$ とすると $\psi(b) = \varphi(a) < \psi(a)$ から $\psi$ が順序を保たず矛盾。よって、いずれの場合も矛盾が導かれたので $\varphi = \psi$ です。つまり、整列集合の間の順序同型写像は存在すれば一意です。
(5) 順序同型写像 $\varphi : X\to X\langle x\rangle$ が存在したとして矛盾を導きます。$A := \{x'\in X\mid \varphi(x')\neq x'\}$ と定めるとき、$\varphi(x)\in X\langle x\rangle$ より $\varphi(x) \neq x$ なので $x\in A$ です。よって、$a := \min A$ が取れます。$a\leq x$ ですが、$a = x$ とすると $\varphi(X\langle a\rangle) = X\langle a\rangle = X\langle x\rangle$ となり $\varphi$ の単射性に矛盾するので $a < x$ です。この場合、$\varphi(b) = a$ となる $b\in X$ が取れますが、$b < a$ ならば $\varphi(b) = b < a = \varphi(b)$ となり矛盾。$a < b$ とすると $\varphi(b) = a < \varphi(a)$ から矛盾。$a = b$ とすると $a = \varphi(b) = \varphi(a)$ となり矛盾です。よって、いずれの場合も矛盾が導けたため、順序同型 $\varphi : X\to X\langle x\rangle$ は存在しません。
整列集合どうしの直和と直積は次のようにしてまた整列集合とみなすことができます。
$(X, \leq_{X}), (Y, \leq_{Y})$ を整列集合とする。
(1) 順序になっていることは簡単です。空でない部分集合 $A\subset X\sqcup Y$ について $A\cap X\neq \varnothing$ ならば $\leq_{X}$ に関する $A\cap X$ の最小元が $\leq$ に関する最小元。$A\cap X = \varnothing$ ならば $A\cap Y\neq \varnothing$ であり、$\leq_{Y}$ に関する $A$ の最小元が $\leq$ に関する最小元になります。
(2) まず順序になっていることですが、反射律は明らか。対称律は $(x_{1}, y_{1})\leq (x_{2}, y_{2})$ かつ $(x_{2}, y_{2})\leq (x_{1}, y_{1})$ のとき、関係 $\leq$ の定義から $x_{1}\leq x_{2}$ かつ $x_{2}\leq x_{1}$ が直ちに分かるので $x_{1} = x_{2}$ であり、よって、$y_{1}\leq y_{2}$ かつ $y_{2}\leq y_{1}$ となり $y_{1} = y_{2}$ も分かるので $(x_{1}, y_{1}) = (x_{2}, y_{2})$ です。推移律を示します。$(x_{1}, y_{1})\leq (x_{2}, y_{2})$ かつ $(x_{2}, y_{2})\leq (x_{3}, y_{3})$ とします。$x_{1} < x_{2}$ か $x_{2} < x_{3}$ のうち一方でも成立する場合、$x_{1} < x_{3}$ なので $(x_{1}, y_{1})\leq (x_{3}, y_{3})$ です。$x_{1} = x_{2} = x_{3}$ の場合、$y_{1}\leq y_{2}$ かつ $y_{2}\leq y_{3}$ であり、よって、$x_{1} = x_{3}$ かつ $y_{1}\leq y_{3}$ となるので $(x_{1}, y_{1})\leq (x_{3}, y_{3})$ です。つまり、推移律も満たします。
$A\subset X\times Y$ を空でない部分集合とします。$X$ 成分への射影による $A$ の像 $\pr_{X}(A)$ の最小元 $a := \min \pr_{X}(A)$ を取り、$B := \{y\in Y\mid (a, y)\in Y\}$ の最小元 $b$ を取れば $(a, b)$ が $A$ の最小元となるので $(X\times Y, \leq)$ は整列集合です。
$X, Y, Z$ を整列集合とします。このとき、直和と直積の両方について結合律\[(X\sqcup Y)\sqcup Z = X\sqcup (Y\sqcup Z), \ (X\times Y)\times Z = X\times (Y\times Z)\]が成立します。しかし、交換法則 $X\sqcup Y\cong Y\sqcup X$, $X\times Y\cong Y\times X$ については一般には成立しません。例えば $X = \{0, 1\}$, $Y = \N$ とすると、直和に関して $X\sqcup Y$ には最大値は存在しないですが $Y\sqcup X$ には最大値 $1\in X$ 存在するので順序同型にはならず、直積に関して $(X\times Y)\langle(1, 0)\rangle$ は切片であって無限集合となるものの例ですが、$Y\times X$ の任意の切片 $(Y\times X)\langle(y, x)\rangle$ はちょうど $2y + x$ 個の元からなり無限集合にはなりえないのでこちらも順序同型になりません。
次は通常の数学的帰納法の一般化です。
整列集合 $X$ の元に関する条件 $P(x)$ が与えられ、次の条件が成立しているとする。
このとき、任意の $x\in X$ に対して $P(x)$ が成立する。
$P(x)$ が成立しない $x\in X$ 全体からなる集合を $A$ とします。もし $A\neq \varnothing$ とすると、$X$ が整列集合であることから $\min A$ が存在しますが、$A$ の定義より任意の $x\in X\langle\min A\rangle$ に対して $P(x)$ が成立します。仮定より $P(\min A)$ が成立しますが、これは $\min A\in A$ に矛盾です。よって、$A = \varnothing$ なので任意の $x\in X$ に対して $P(x)$ が成立します。
次の比較定理は、ある意味で任意の整列集合どうしが比較可能であることを意味します。
$X, Y$ を整列集合とする。このとき、次のうちのいずれか一つのみが必ず成立する。
概略だけ。$x\in X$ であって順序同型 $X\langle x\rangle\cong Y\langle y\rangle$ を成立させる $y\in Y$ が存在するもの全体からなる集合を $A\subset X$ とします。このとき、命題1.4.5から各 $x\in A$ に対してそのような $y\in Y$ が一意に対応するので常に $X\langle x\rangle\cong Y\langle f(x)\rangle$ を満たす写像 $f : A\to Y$ が構成されます。同様に、$y\in Y$ であって順序同型 $X\langle x\rangle\cong Y\langle y\rangle$ を成立させる $x\in X$ が存在するもの全体からなる集合を $B\subset Y$ とし、写像 $g : B\to X$ を構成します。
$\Img f\subset B$, $\Img g\subset A$ は明らか。また、合成について $g\circ f = \Id_{A}$ と $f\circ g = \Id_{B}$ も明らか。$f, g$ が順序を保つことも容易であり、順序同型 $A\cong B$ が成立します。
任意の $a\in A$ と $x\in X$ に対して $x\leq a\Rightarrow x\in A$ であることから $A$ は切片 $X\langle x\rangle$ か全体集合 $X$ のどちらかになり、$B$ についても同様に切片 $Y\langle y\rangle$ か全体集合 $Y$ のどちらかです。$A = X\langle x\rangle$ かつ $B = Y\langle y\rangle$ のパターンは $x\in A = X\langle x\rangle$ を導き矛盾するので、主張の $3$ つの条件のうち少なくとも $1$ つが成立することが従います。
そして、主張の $3$ つの条件のうち複数が同時に成立しないことは命題1.4.5から従います。
整列集合の同型類のことを順序数 $($ordinal number$)$ といいます。順序数の間には全順序、加法、乗法が定義でき、ある意味での非負整数の拡張概念と考えることができます。
まず、命題1.4.5の結果によって順序数 $\lambda, \mu$ の間の順序 $\leq$ をそれらの代表元 $X, Y$ を用いて、$X\cong Y$ または $X\cong Y\langle y\rangle$ であるときに $\lambda \leq \mu$ としてwell-definedに定義できます。比較定理 $($定理1.4.9$)$ は任意の順序数どうしが比較可能であることを意味します。加法と乗法については、命題1.4.6から加法 $\lambda + \mu = [X\sqcup Y]$、乗法 $\lambda\cdot \mu = [X\times Y]$ として定義できます。結合法則は成立しますが、交換法則は成立しません。非負整数 $n\in \N$ に整列集合 $\{x\in \N\mid x < n\}$ の定める順序数に対応させるとき、この対応は順序・加法・乗法をいずれも保ち有限集合を台集合とする整列集合の同型類が台集合の元の個数によって一意に決まるという事が比較定理の系として従うことに注意。つまり、同じ個数の元からなる有限整列集合の間には必ず順序同型が存在しています。また、異なる個数の元からなる有限整列集合は順序同型になりえないので、異なる非負整数は異なる順序数に対応しています。、この意味で順序数を非負整数を拡張した概念とみなせます。
ちなみに、有限整列集合の定める順序数を有限順序数といい、無限整列集合の定める順序数を無限順序数といいます。一つ重要な事実として、非負整数集合 $\N$ 自体は無限整列集合ですが、その任意の切片が有限集合であることから $\N$ は最小の無限順序数を定めており、それを通常 $\omega$ と書きます。
任意の集合に整列順序が存在することをZornの補題 $($定理1.4.1$)$ を用いて示したいと思います。
任意の集合 $X$ にはある順序 $\leq$ が存在して $(X, \leq)$ は整列集合となる。
$\mathcal{S}$ を $X$ の部分集合 $A$ とその上の整列順序 $\leq$ の対 $(A, \leq)$ 全体からなる集合とします。$(A, \leq_{A}), (B, \leq_{B})\in \mathcal{S}$ に対し、$b\in B$ であって $(A, \leq_{A}) = (B\langle b\rangle, \leq_{B})$ となるものが存在するときに $(A, \leq_{A})\prec (B, \leq_{B})$ であるとして $\mathcal{S}$ の順序 $\preceq$ を定めますつまり、$(A, \leq_{A})\prec (B, \leq_{B})$ または $(A, \leq_{A}) = (B, \leq_{B})$ により $(A, \leq_{A})\preceq (B, \leq_{B})$ を定義。これが実際に順序を与えることは容易。。
$(\mathcal{S}, \preceq)$ が帰納的順序集合であることを示すため、全順序部分集合 $\mathcal{A}\subset \mathcal{S}$ に対して $\tilde{A} = \underset{(A, \leq_{A})\in \mathcal{A}}{\bigcup}A$ に適切な順序 $\leq$ を与えることで $\mathcal{A}$ の上界となることを示します。まずは次のことを示します。
(i) $x\in A$, $y\in B$ となる $(A, \leq_{A}), (B, \leq_{B})\in \mathcal{A}$ を取ります。$\mathcal{A}$ が全順序なので、$(A, \leq_{A})\preceq (B, \leq_{B})$ または $(B, \leq_{B})\preceq (A, \leq_{A})$ ですが、前者なら $A\subset B$ より $x, y\in B$ であり、後者なら $B\subset A$ より $x, y\in A$ です。
(ii) $(A, \preceq_{A}), (B, \preceq_{B})\in \mathcal{A}$ が比較可能なので、一方は他方の部分順序集合であり明らか。
よって、$x, y\in \tilde{A}$ に対して $x, y\in A$ を適当に固定して $x\leq y\Leftrightarrow x\leq_{A} y$ と定めることで $\tilde{A}$ の関係 $\leq$ がwell-definedに定まります。$(\tilde{A}, \leq)$ が $\mathcal{A}$ の上界になることを以下の順で示します。
(step 1) 推移律のみ示します。他も容易です。$x, y, z\in \tilde{A}$ に対して $x\leq y$ かつ $y\leq z$ であったとします。$x, y, z\in A$ となる $(A, \leq_{A})\in \mathcal{A}$ を取れば $x\leq_{A} y$ かつ $y\leq_{A} z$ から $x\leq_{A} z$ であり、よって、$x\leq z$ です。
(step 2) 空でない部分集合 $C\subset \tilde{A}$ を取ります。$A\cap C\neq \varnothing$ を満たす $(A, \leq_{A})\in \mathcal{A}$ を取り、$(A, \leq_{A})$ における $A\cap C$ の最小元 $c$ を取ります。この $c$ が $(\tilde{A}, \leq)$ に関する $C$ の最小元であることを示します。$c'\in A\cap C$ に対して $c\leq c'$ であることは明らかなので $c'\in (\tilde{A}\setminus A)\cap C$ に対して $c\leq c'$ を示せばよいです。$c'\in B$ となる $(B, \leq_{B})\in \mathcal{A}$ を取ります。$\mathcal{A}$ が全順序であることと $c'\notin A$ より $(A, \leq_{A})\prec (B, \leq_{B})$ であり、よって、ある $b\in B$ が存在して $(A, \leq_{A}) = (B\langle b\rangle, \leq_{B})$ です。よって、$c < b = \min (B\setminus B\langle b\rangle) = \min (B\setminus A)\leq c'$ です。
(step 3) $(A, \leq_{A})\in \mathcal{A}$ とします。集合として $A = \tilde{A}$ の場合、$\tilde{A}$ の順序 $\leq$ の定め方より $\leq = \leq_{A}$ なので $(A, \leq_{A}) = (\tilde{A}, \leq)$ です。集合として $A\neq \tilde{A}$ のとき、$A\subset \tilde{A}$ から $b\in \tilde{A}\setminus A$ が存在します。$b\in B$ となる $(B, \leq_{B})\in \mathcal{A}$ を取れば $(A, \leq_{A})\prec (B, \leq_{B})$ であり、ある $\tilde{a}\in B$ が存在して $A = B\langle \tilde{a}\rangle$ です。この $\tilde{a}$ に対して $B\langle \tilde{a}\rangle = \tilde{A}\langle \tilde{a}\rangle$ であることを示せばよいです。
まず、$B\langle \tilde{a}\rangle \subset \tilde{A}\langle \tilde{a}\rangle$ は明らか。逆の包含関係を示すために $x\in \tilde{A}\langle \tilde{a}\rangle\setminus B\langle \tilde{a}\rangle$ が存在したとして矛盾を導きます。$x\in C$ を満たす $(C, \leq_{C})\in \mathcal{A}$ を取ります。$x\notin B$ から $(B, \leq_{B})\prec (C, \leq_{C})$ であり、ある $c\in C$ が存在して $B = C\langle c\rangle$ です。$\tilde{a}\in B$ より $\tilde{a} < c$ であり $x\notin B$ より $c\leq x$ となりますが、これは $x < \tilde{a}$ に矛盾です。よって、$\tilde{A}\langle\tilde{a}\rangle\subset B\langle\tilde{a}\rangle$ であり $B\langle \tilde{a}\rangle = \tilde{A}\langle \tilde{a}\rangle$ です。
以上により $\mathcal{S}$ が帰納的順序集合であることが分かりました。よって、Zornの補題 $($定理1.4.1$)$ より $\mathcal{S}$ の極大元 $(A, \leq_{A})$ が取れます。もし $A\neq X$ とすると、$x\in X\setminus A$ を取って $A\sqcup \{x\}$ に明らかな整列順序 $\leq$ を入れることで $(A, \leq_{A})\prec (A\sqcup \{x\}, \leq)$ $A = (A\sqcup \{x\})\langle x\rangle$ です。なので $(A, \leq_{A})$ の極大性に矛盾。よって、$A = X$ であり主張が示されました。
選択公理について。ZF公理系において
の $3$ つが同値であるということが知られています。つまり、実はこのうちのどれか $1$ つを仮定すれば他の $2$ つも成立することが示されます。ここでは選択公理のみを使用してZornの補題を証明し、Zornの補題のみを用いて整列定理を証明しているので、あとは $($選択公理を認めていたことは一旦忘れて$)$ 整列定理のみを用いて選択公理を証明すればよいです。しかしこれは、空でない集合による族 $\{A_{\lambda}\}_{\lambda\in\Lambda}$ が与えられたとき、整列定理から $\bigcup_{\lambda\in\Lambda}A_{\lambda}$ に整列順序を与えれば $\prod_{\lambda\in\Lambda}A_{\lambda}$ の元を具体的に $(\min A_{\lambda})_{\lambda\in\Lambda}$ と構成できるのでよいです。
集合 $X, Y$ に対してそれぞれの元の「個数」の大小を比較したいことがあり、そのために濃度とその大小を導入します。まず、集合 $X, Y$ が同じ「個数」の元からなる集合であるということをその間の全単射が存在することと考えることは当然ですが、実際に $X$ から $Y$ への全単射が存在するとき、$X$ と $Y$ は対等 $($equipotent$)$ であるといいます。このことを $X\sim Y$ と書くことにすれば、これは任意の集合 $X, Y, Z$ に対して
と反射律、対称律、推移律を満たしています。この対等というのが集合に関する同型概念になります。集合 $X$ の代表する同型類を $X$ の濃度 $($cardinality$)$ と呼び、$\#X$, $|X|$ や $\card X$ により表されます。
集合 $X, Y$ の濃度 $\#X, \#Y$ の大小について、単射 $f : X\to Y$ が存在することを $X$ の濃度は $Y$ の濃度以下、もしくは $Y$ の濃度は $X$ の濃度以上ということにして\[\#X\leq \#Y\]と表します。$\#X\leq \#Y$, $X\sim X'$, $Y\sim Y'$ ならば $\#X'\leq \#Y'$ なので単射 $X\to Y$ と全単射 $X'\to X$, $Y\to Y'$ を合成して得られる写像 $X'\to Y'$ は単射というだけです。同型類としての濃度の間の関係としてwell-definedになっています。また、通常の順序と同様に $\#X\leq \#Y$ かつ $\#X\neq \#Y$ であることを $\#X < \#Y$ と書くことにします。
そして、この濃度に関する関係は以下に紹介するように「全順序関係」になっています。
$X, Y, Z$ を集合とする。
(1) 恒等写像 $\Id_{X} : X\to X$ は単射なのでそう。
(2) $X$ の部分集合による減少列 $X_{0}\supset X_{1}\supset X_{2}\supset \cdots$ を $X_{0} := X$, $X_{k + 1} := (g\circ f)(X_{k})$ により定め、同様に $Y$ の部分集合による減少列 $Y_{0}\supset Y_{1}\supset Y_{2}\supset \cdots$ を $Y_{0} := Y$, $Y_{k + 1} := (f\circ g)(Y_{k})$ により定めます。また、$X_{\infty} := \bigcap_{k\in\N}X_{k}$, $Y_{\infty} := \bigcap_{k\in\N}Y_{k}$ とおきます。このとき、
が成立しています。次のことを示せばよいです。
つまり、これらが $X, Y$ の直和分解の各成分の間の全単射となっているので、明らかな方法で全体の全単射 $h : X\to Y$ が構成されます。
(i) 次のことを示します。
これが示されれば、$X_{k}\setminus X_{k + 1} = X_{k}\setminus g(Y_{k})\sqcup g(Y_{k})\setminus X_{k + 1}$ と $Y_{k}\setminus Y_{k + 1} = Y_{k}\setminus f(X_{k})\sqcup f(X_{k})\setminus Y_{k + 1}$ から $h_{k} : X_{k}\setminus X_{k + 1}\to Y_{k}\setminus Y_{k + 1}$ を\[h_{k} : x\mapsto \left\{\begin{array}{ll}h'_{k}(x) & (x\in X_{k}\setminus g(Y_{k})) \\(h''_{k})^{-1}(x)& (x\in g(Y_{k})\setminus X_{k + 1})\end{array}\right.\]と定めることで全単射 $h_{k}$ が構成されます。
(a)$f$ が単射なので $f(X_{k}\setminus g(Y_{k})) = f(X_{k})\setminus Y_{k + 1}$ を示せばよいです。$y\in f(X_{k}\setminus g(Y_{k}))$ とします。$f(x) = y$ を満たす $x\in X_{k}\setminus g(Y_{k})$ を取ります。$f(x)\in f(X_{k})$ です。$f(x)\notin Y_{k + 1}$ を背理法より示します。$f(x)\in Y_{k + 1}$ とします。$Y_{k + 1} = f(g(Y_{k}))$ よりある $x'\in g(Y_{k})$ であって $f(x') = f(x)$ となるものが取れます。$f$ が単射なので $x' = x\notin g(Y_{k})$ であり矛盾です。よって、$f(x)\notin Y_{k + 1}$ が分かり、$y = f(x)\in f(X_{k})\setminus Y_{k + 1}$ です。従って、$f(X_{k}\setminus g(Y_{k}))\subset f(X_{k})\setminus Y_{k + 1}$ です。
$y\in f(X_{k})\setminus Y_{k + 1}$ とします。$y\in f(X_{k})$ から $f(x) = y$ となる $x\in X_{k}$ を取ります。$x\in g(Y_{k})$ であったとすると、$y = f(x)\in f(g(Y_{k})) = Y_{k + 1}$ となって矛盾するので $x\notin g(Y_{k})$ です。よって、$x\in X_{k}\setminus g(Y_{k})$ であり、$y = f(x)\in f(X_{k}\setminus g(Y_{k}))$ です。従って、$f(X_{k})\setminus Y_{k + 1}\subset f(X_{k}\setminus g(Y_{k}))$ です。
両方の向きの包含関係が示されたので $f(X_{k}\setminus g(Y_{k})) = f(X_{k})\setminus Y_{k + 1}$ です。
(b) (a)と同じです。
(ii) $h_{\infty}$ の単射性は明らか。全射性を示します。$y\in Y_{\infty}$ とします。任意の $k\in \N$ に対し、$y\in Y_{k + 1} = g(f(Y_{k}))\subset g(X_{k})$ により $x_{k}\in X_{k}$ であって $f(x_{k}) = y$ となるものが取れます。任意の $k\in \N$ に対して $f$ の単射性と $f(x_{0}) = y = f(x_{k})$ から $x_{0} = x_{k}\in X_{k}$ であり、$x_{0}\in X_{\infty}$ です。$x_{0}\in X_{\infty}$ かつ $h_{\infty}(x_{0}) = f(x_{0}) = y$ です。よって、$h_{\infty}$ の全射性が示されました。
(3) 単射どうしの合成は単射なのでそうです。
通常、非負整数全体からなる集合 $\N$ の濃度を $\aleph_{0}$ と書きます。集合 $X$ が $\#X < \aleph_{0}$ を満たすとき $X$ は有限集合であるといい、$\#X \geq \aleph_{0}$ を満たすとき $X$ は無限集合であるといいます。$\#X$ 自体は有限濃度、無限濃度といいます。有限集合 $X, Y$ に対して $\#X = \#Y$ であることはそれぞれの元の個数が等しい場合に限るので、通常はその濃度を単に非負整数 $0, 1, 2, \dots, n, \dots$ を用いて表します。
$\mathfrak{n}, \mathfrak{m}$ を濃度とします。$\mathfrak{n} = \#X$, $\mathfrak{m} = \#Y$ を満たす集合 $X, Y$ を取り、濃度に関する和、積、冪乗を\begin{eqnarray*}\mathfrak{n} + \mathfrak{m} & = & \#(X\sqcup Y), \\\mathfrak{n}\mathfrak{m} & = & \#(X\times Y), \\\mathfrak{m}^{\mathfrak{n}} & = & \#Y^{X}\end{eqnarray*}により定義します。この定義は集合 $X, Y$ の取り方によらずに定義できていることには注意します。
これらの濃度に関する演算について次が成立します。
$\mathfrak{n}, \mathfrak{m}$ を濃度とする。次が成立する。
集合 $X, Y$ を $\#X = \mathfrak{n}$, $\#Y = \mathfrak{m}$ となるように取っておきます。
(1) 明らかに写像 $X\to 2^{X} : x\mapsto \{x\}$ は単射であるので $\mathfrak{n}\leq 2^{\mathfrak{n}}$ です。等号が成立していたとして矛盾を導きます。全単射 $f : X\to 2^{X}$ を取ります。部分集合 $A := \{x\in X\mid x\notin f(x)\}$ を考えるとき、$f^{-1}(A)\in A$ とすると $A$ の定義から $f^{-1}(A)\notin A$ となり矛盾。$f^{-1}(A)\notin A$ としても $A$ の定義から $f^{-1}(A)\in A$ となり矛盾します。よって、いずれにせよ矛盾が導かれることから $\mathfrak{n}\neq 2^{\mathfrak{n}}$ が従いますこのような議論は対角線論法と呼ばれます。。
(2) 集合 $\Lambda$ であって $Y\sim \Lambda\times \N$ となるものを構成します。これができれば、$\N\sim\N\sqcup \N$ から\[Y\sim \Lambda\times \N\sim \Lambda\times (\N\sqcup \N)\sim (\Lambda\times \N)\sqcup (\Lambda\times \N)\sim Y\sqcup Y\]なので $\mathfrak{m}\leq \mathfrak{n} + \mathfrak{m}\leq \mathfrak{m} + \mathfrak{m} = \mathfrak{m}$ となり、$\mathfrak{n} + \mathfrak{m} = \mathfrak{m}$ です。
まず、$Z = 2^{Y}$ に整列順序を与えて整列集合とみなします$Z$ は $Y$ の濃度より大きい濃度を持てばなんでもいいです。。$z\in Z$ と単射 $f : Z\langle z\rangle\times \N\to Y$ の対 $(z, f)$ 全体からなる集合 $\mathcal{S}$ を考えます。$\mathcal{S}$ に対して\[(z, f)\leq (w, g) :\Leftrightarrow z\leq w\wedge g|_{Z\langle z\rangle\times \N} = f\]による順序を定めれば帰納的順序集合になるため$\mathcal{S}$ の全順序部分集合 $\mathcal{A}$ が与えられたとき、そこに属する写像たちを全て明らかな方法で「重ね合わせる」ことで上界が作れます。この重ね合わせて作った写像の定義域が $Z\langle z\rangle\times \N$ の形であること $($$Z\times \N$ でないこと$)$ も要確認ですが、これは $\#Y < \#(Z\times \N)$ から分かります。、Zornの補題 $($定理1.4.1$)$ よりその極大元 $(z_{0}, f_{0})$ が取れますが、その極大性より $N := Y\setminus \Img f_{0}$ は有限集合であり $Y\sim (Z\langle z_{0}\rangle\times \N)\sqcup N$ が得られます$\#Y < \#(Z\times \N) = \#((Z\setminus \{z_{0}\})\times \N)$ より $z_{0}$ は最大元ではないので $Z\langle z_{1}\rangle = Z\langle z_{0}\rangle\sqcup \{z_{0}\}$ となる $z_{1}\in Z$ が取れます。もし $N := Y\setminus \Img f_{0}$ が無限集合とすると $f_{0}$ は単射 $f_{1} : Z\langle z_{1}\rangle\to Y$ に拡張でき、これについて $(z_{0}, f_{0}) < (z_{1}, f_{1})$ となり極大性に矛盾です。。$Y$ が無限集合であることから $\min Z < z_{0}$ であり、$\{\min Z\}\times \N\sqcup N\sim \{\min Z\}\times \N$ から有限集合 $N$ を $\Img f_{0}$ に組み込めば $Y\sim Z\langle z_{0}\rangle\times \N$ が得られます。
(3) まず、$\N\sim \N\times \N$ が全単射\[\varphi : \N\times \N\to \N : (n, m)\mapsto \tfrac{1}{2}(n + m)(n + m + 1) + m\]により確かめられ、よって、空でない有限集合 $M$ に対して $\N^{M}\sim \N\sim \N^{M}\times \N^{M}$ が分かります。また、無限集合 $M$ に対しては(2)より $\N^{M}\sim \N^{M\sqcup M}\sim \N^{M}\times \N^{M}$ です。つまり、任意の空でない集合 $M$ に対して $\N^{M}\sim \N^{M}\times \N^{M}$ となります。
集合 $M$ であって $Y\sim \N^{M}$ となるものを構成します。これができれば、上記のことから\[Y\sim \N^{M}\sim \N^{M}\times \N^{M}\sim Y\times Y\]なので $\mathfrak{m}\leq \mathfrak{n}\mathfrak{m}\leq \mathfrak{m}\mathfrak{m} = \mathfrak{m}$ となり、$\mathfrak{n}\mathfrak{m} = \mathfrak{m}$ です。
まず、$Y$ に整列順序を与えて整列集合とみなし、それを $Z$ と書くことにします。そして、各切片 $Z\langle z\rangle$ に対して単射 $\N^{Z\langle z\rangle}\to \N^{Z}$ を\[(a_{z})_{z\in Z\langle z\rangle}\mapsto (a_{z})_{z\in Z\langle z\rangle}\sqcup (0)_{z\in Z\setminus Z\langle z\rangle}\]と取ることにより $\N^{Z\langle z\rangle}\subset \N^{Z}$ とみなしておきます。$z\in Z$ と単射 $f : \N^{Z\langle z\rangle}\to Y$ の対 $(z, f)$ 全体からなる集合 $\mathcal{S}$ を考えます。$\mathcal{S}$ に対して\[(z, f)\leq (w, g) :\Leftrightarrow z\leq w\wedge g|_{\N^{Z\langle z\rangle}} = f\]による順序を定めれば帰納的順序集合になるため、その極大元 $(z_{0}, f_{0})$ が取れますが、その極大性より $\#Y\setminus \Img f_{0} < \#\Img f_{0} = \#\N^{Z\langle z_{0}\rangle}$ であり\[Y = \Img f_{0}\sqcup (Y\setminus \Img f_{0})\sim \Img f_{0}\sim \N^{Z\langle z_{0}\rangle} \]が得られます。細かい部分はだいたい(2)と一緒です。
(4) (3)から $2^{\mathfrak{m}} = 2^{\mathfrak{m}\mathfrak{m}} = (2^{\mathfrak{m}})^{\mathfrak{m}}$ であり、$2\leq \mathfrak{n}\leq \mathfrak{m}\leq 2^{\mathfrak{m}}$ と合わせて $2^{\mathfrak{m}}\leq \mathfrak{n}^{\mathfrak{m}}\leq (2^{\mathfrak{m}})^{\mathfrak{m}} = 2^{\mathfrak{m}}$ です。よって、$\mathfrak{n}^{\mathfrak{m}} = 2^{\mathfrak{m}}$ が成立します。
(5) (3)の繰り返し適用により示されます。
濃度の比較に関して特別重要なのは\[\#\N = \#\Z = \#\Z^{n} = \#\Q = \#\Q^{n} = \aleph_{0},\]\[\#\R = \#\C = \#\R^{n} = \#2^{\N} = \#\N^{\N} = 2^{\aleph_{0}}\]であること、そして\[\#\N = \aleph_{0} < 2^{\aleph_{0}} = \#\R\]であることです。
$\#\N = \#\Z$ は写像 $f : \N\to \Z$ を\[f(n) = \left\{\begin{array}{ll}n/2 & (n : \text{even}) \\-(n + 1)/2 & (n : \text{odd})\end{array}\right.\]により定めれば全単射なのよいです。
$\#\N = \#\Q$ を示します。正整数 $n\in \N_{+}$ に対して部分集合 $A_{n}\subset \Q$ を\[A_{n} = \{p/q\mid p, q\in\Z, \ 1\leq q\leq n, \ |p|\leq nq\}\]により定めますつまり、有理数 $r$ であって $|r|\leq n$ かつ既約分数で表したときの分母 $q$ が $n$ 以下であるもの全体からなる集合。。$A_{n}$ は有限集合かつ部分集合の列として単調増加であり、$\underset{n\in\N_{+}}{\bigcup}A_{n} = \Q$ です。よって、添字 $n$ の小さい $A_{n}$ に属する有理数から順番に $\N$ の元を対応させていけば全単射 $\N\to \Q$ が構成されます。(いろいろ準備したので、写像 $\Z\times \Np\to \Q : (p, q)\mapsto p/q$ の全射性から $\#\Q\leq \#(\Z\times \Np) = \#\N$ というのが単純ですが。)
以上です。
特になし。
参考文献
更新履歴