整列可能定理
整列可能定理
任意の集合\(X\)は適当な順序\(\preceq\)を定めることによって整列集合\(\left(X,\preceq\right)\)にできる。
任意の集合\(X\)は適当な順序\(\preceq\)を定めることによって整列集合\(\left(X,\preceq\right)\)にできる。
(1)
整列可能定理はツェルメロの整列可能定理ともいいます。(2)
整列可能定理は選択公理と同値である。(3)
実数全体の集合も通常とは違う順序を定めると整列集合とすることは可能である。選択公理と整列可能定理が同値であることを証明する。
選択公理を仮定しているので、\(X\)の空集合ではない部分集合から要素を1つ選ぶ選択関数\(f_{0}:2^{X}\setminus\emptyset\rightarrow X\)が存在する。
このとき\(X\)の要素でない\(a\notin X\)を選び\(f_{0}\left(\emptyset\right)\rightarrow a\)と定めると\(f_{0}\)を拡張して\(f:2^{X}\rightarrow X\cup\left\{ a\right\} \)とできる。
また写像\(g:\lambda\rightarrow X\)を\(g\left(\alpha\right)=f\left(X\setminus\left\{ g\left(\beta\right);\beta<\alpha\right\} \right)\)とする。
ここで、ある\(\alpha,\beta<\lambda\)が存在し\(g\left(\alpha\right)=g\left(\beta\right)\ne a\land\alpha\ne\beta\)と仮定する。
\(\alpha\ne\beta\)として\(\beta<\alpha\)とすると、\(g\left(\alpha\right)\ne a\)なので選択関数\(f\)の決め方より、\(a\ne g\left(\alpha\right)=f\left(X\setminus\left\{ g\left(\beta\right);\beta<\alpha\right\} \right)=f_{0}\left(X\setminus\left\{ g\left(\beta\right);\beta<\alpha\right\} \right)\in X\setminus\left\{ g\left(\beta\right);\beta<\alpha\right\} \)となる。
これより、\(g\left(\alpha\right)\in X\setminus\left\{ g\left(\beta\right);\beta<\alpha\right\} \)となり、\(g\left(\alpha\right)\notin\left\{ g\left(\beta\right);\beta<\alpha\right\} \)なので\(g\left(\alpha\right)\ne g\left(\beta\right)\)となり矛盾。
従って背理法より、任意の\(\alpha,\beta<\lambda\)に対し、\(\lnot\left(g\left(\alpha\right)=g\left(\beta\right)\ne a\land\alpha\ne\beta\right)\Leftrightarrow\lnot\left(g\left(\alpha\right)=g\left(\beta\right)\ne a\right)\lor\alpha=\beta\Leftrightarrow g\left(\alpha\right)=g\left(\beta\right)\ne a\rightarrow\alpha=\beta\)となる。
これより、\(g\left(\alpha\right)\ne a\)のときは\(g\)は単射となる。
ここで、任意の\(\alpha<\lambda\)に対し、\(g\left(\alpha\right)\ne a\)となると仮定する。
そうすると、\(g\left(\alpha\right)=g\left(\beta\right)\ne a\rightarrow\alpha=\beta\)より、\(g:\lambda\rightarrow X\)は単射となるが、\(\left|X\right|<\left|\lambda\right|\)なので矛盾。
従って背理法より、ある\(\alpha<\lambda\)が存在し、\(g\left(\alpha\right)=a\)となる。
これより、\(\gamma=\min\left\{ \alpha<\lambda;g\left(\alpha\right)=a\right\} \)とおくと、\(a=g\left(\gamma\right)=f\left(X\setminus\left\{ g\left(\beta\right);\beta<\gamma\right\} \right)\)より、\(X\setminus\left\{ g\left(\beta\right);\beta<\gamma\right\} =\emptyset\)となる。
従って、\(g\)を\(\gamma\)より小さいものに制限したものを\(g\mid_{\gamma}\)と書くと\(g\mid_{\gamma}\):\(\gamma\rightarrow X\)は全射となり、また単射でもあるので、全単射となる。
故に\(X\)は整列可能となるので\(\Rightarrow\)が成り立つ。
整列可能定理より、\(\bigcup_{\lambda\in\Lambda}X_{\lambda}\)から適当な順序\(\preceq\)を定め整列集合\(\left(\bigcup_{\lambda\in\Lambda}X_{\lambda},\preceq\right)\)を作る。
このとき、\(f:\lambda\rightarrow\bigcup_{\lambda\in\Lambda}X_{\lambda},f\left(\lambda\right)=\min\left(X_{\lambda}\right)\)とすれば\(f\)は選択関数となる。
故に選択公理を満たすので\(\Leftarrow\)は成り立つ。
\(\Rightarrow\)
集合\(X\)があり、順序数\(\lambda\)が\(\left|X\right|<\left|\lambda\right|\)を満たすようにとる。選択公理を仮定しているので、\(X\)の空集合ではない部分集合から要素を1つ選ぶ選択関数\(f_{0}:2^{X}\setminus\emptyset\rightarrow X\)が存在する。
このとき\(X\)の要素でない\(a\notin X\)を選び\(f_{0}\left(\emptyset\right)\rightarrow a\)と定めると\(f_{0}\)を拡張して\(f:2^{X}\rightarrow X\cup\left\{ a\right\} \)とできる。
また写像\(g:\lambda\rightarrow X\)を\(g\left(\alpha\right)=f\left(X\setminus\left\{ g\left(\beta\right);\beta<\alpha\right\} \right)\)とする。
ここで、ある\(\alpha,\beta<\lambda\)が存在し\(g\left(\alpha\right)=g\left(\beta\right)\ne a\land\alpha\ne\beta\)と仮定する。
\(\alpha\ne\beta\)として\(\beta<\alpha\)とすると、\(g\left(\alpha\right)\ne a\)なので選択関数\(f\)の決め方より、\(a\ne g\left(\alpha\right)=f\left(X\setminus\left\{ g\left(\beta\right);\beta<\alpha\right\} \right)=f_{0}\left(X\setminus\left\{ g\left(\beta\right);\beta<\alpha\right\} \right)\in X\setminus\left\{ g\left(\beta\right);\beta<\alpha\right\} \)となる。
これより、\(g\left(\alpha\right)\in X\setminus\left\{ g\left(\beta\right);\beta<\alpha\right\} \)となり、\(g\left(\alpha\right)\notin\left\{ g\left(\beta\right);\beta<\alpha\right\} \)なので\(g\left(\alpha\right)\ne g\left(\beta\right)\)となり矛盾。
従って背理法より、任意の\(\alpha,\beta<\lambda\)に対し、\(\lnot\left(g\left(\alpha\right)=g\left(\beta\right)\ne a\land\alpha\ne\beta\right)\Leftrightarrow\lnot\left(g\left(\alpha\right)=g\left(\beta\right)\ne a\right)\lor\alpha=\beta\Leftrightarrow g\left(\alpha\right)=g\left(\beta\right)\ne a\rightarrow\alpha=\beta\)となる。
これより、\(g\left(\alpha\right)\ne a\)のときは\(g\)は単射となる。
ここで、任意の\(\alpha<\lambda\)に対し、\(g\left(\alpha\right)\ne a\)となると仮定する。
そうすると、\(g\left(\alpha\right)=g\left(\beta\right)\ne a\rightarrow\alpha=\beta\)より、\(g:\lambda\rightarrow X\)は単射となるが、\(\left|X\right|<\left|\lambda\right|\)なので矛盾。
従って背理法より、ある\(\alpha<\lambda\)が存在し、\(g\left(\alpha\right)=a\)となる。
これより、\(\gamma=\min\left\{ \alpha<\lambda;g\left(\alpha\right)=a\right\} \)とおくと、\(a=g\left(\gamma\right)=f\left(X\setminus\left\{ g\left(\beta\right);\beta<\gamma\right\} \right)\)より、\(X\setminus\left\{ g\left(\beta\right);\beta<\gamma\right\} =\emptyset\)となる。
従って、\(g\)を\(\gamma\)より小さいものに制限したものを\(g\mid_{\gamma}\)と書くと\(g\mid_{\gamma}\):\(\gamma\rightarrow X\)は全射となり、また単射でもあるので、全単射となる。
故に\(X\)は整列可能となるので\(\Rightarrow\)が成り立つ。
\(\Leftarrow\)
空集合を要素に持たない集合族を\(\left\{ X_{\lambda}\right\} _{\lambda\in\Lambda}\)とする。整列可能定理より、\(\bigcup_{\lambda\in\Lambda}X_{\lambda}\)から適当な順序\(\preceq\)を定め整列集合\(\left(\bigcup_{\lambda\in\Lambda}X_{\lambda},\preceq\right)\)を作る。
このとき、\(f:\lambda\rightarrow\bigcup_{\lambda\in\Lambda}X_{\lambda},f\left(\lambda\right)=\min\left(X_{\lambda}\right)\)とすれば\(f\)は選択関数となる。
故に選択公理を満たすので\(\Leftarrow\)は成り立つ。
-
これらより、\(\Rightarrow\)と\(\Leftarrow\)が成り立つので\(\Leftrightarrow\)が成り立つ。ページ情報
タイトル | 整列可能定理 |
URL | https://www.nomuramath.com/auo1pq2p/ |
SNSボタン |
テューキーの補題
有限性をもつ空でない集合族$\mathcal{A}$に対し、包含関係を順序とする半順序集合$\left(\mathcal{A},\subseteq\right)$に極大元が存在する。
超限帰納法
\[
P\left(\min X\right)\land\forall x\in X,\left(\forall a\prec x,P\left(a\right)\right)\rightarrow P\left(x\right)\Rightarrow\forall x\in X,P\left(x\right)
\]
整列集合の定義
順序写像・順序単射・順序埋め込み写像の合成写像
順序写像同士の合成写像は順序写像になる。