整列集合の比較定理
整列集合\(\left(X,\preceq\right)\)が与えられたとき、\(f:X\rightarrow X\)が順序を保つ単射であれば任意の\(x\in X\)に対し\(x\preceq f\left(x\right)\)が成り立つ。
順序を保つ単射であれば任意の\(a,b\in X\)に対し、\(a\boldsymbol{\precneqq}b\rightarrow f\left(a\right)\precneqq f\left(b\right)\)が成り立つ。
背理法で示す。
\(\lnot\left(x\preceq f\left(x\right)\right)\Leftrightarrow f\left(x\right)\precneqq x\)を満たす元\(x\)があると仮定する。
このとき、\(A=\left\{ x\in X;f\left(x\right)\precneqq x\right\} \)とおくと、\(A\)は整列集合の部分集合なので最小元\(a\)があり\(f\left(a\right)\precneqq a\)を満たす。
\(f\)は順序を保つ単射なのでもう一度作用させると\(f\left(f\left(a\right)\right)\precneqq f\left(a\right)\)となり、\(f\left(a\right)\in A\)となる。
これより、\(f\left(a\right)\in A\)で\(f\left(a\right)\precneqq a\)となり、\(A\)の最小元が\(a\)であったことに矛盾が生じる。
従って背理法より\(f\left(x\right)\precneqq x\)を満たす元\(x\)は存在しない。
故に任意の\(x\in X\)に対し\(x\preceq f\left(x\right)\)が成り立つので題意は成り立つ。
\(\lnot\left(x\preceq f\left(x\right)\right)\Leftrightarrow f\left(x\right)\precneqq x\)を満たす元\(x\)があると仮定する。
このとき、\(A=\left\{ x\in X;f\left(x\right)\precneqq x\right\} \)とおくと、\(A\)は整列集合の部分集合なので最小元\(a\)があり\(f\left(a\right)\precneqq a\)を満たす。
\(f\)は順序を保つ単射なのでもう一度作用させると\(f\left(f\left(a\right)\right)\precneqq f\left(a\right)\)となり、\(f\left(a\right)\in A\)となる。
これより、\(f\left(a\right)\in A\)で\(f\left(a\right)\precneqq a\)となり、\(A\)の最小元が\(a\)であったことに矛盾が生じる。
従って背理法より\(f\left(x\right)\precneqq x\)を満たす元\(x\)は存在しない。
故に任意の\(x\in X\)に対し\(x\preceq f\left(x\right)\)が成り立つので題意は成り立つ。
整列集合\(\left(X,\preceq\right)\)があり、\(a,b\in X\)のとき、\(a\ne b\)ならば\(\left(X\left\langle a\right\rangle ,\preceq\right)\ncong\left(X\left\langle b\right\rangle ,\preceq\right)\)で順序同型とならない。
\(a\ne b\)なので\(a\precneqq b\)とする。
背理法により示す。
順序同型\(\left(X\left\langle a\right\rangle ,\preceq\right)\simeq\left(X\left\langle b\right\rangle ,\preceq\right)\)であると仮定する。
このとき、順序同型であるので順序を保つ単射\(f:X\left\langle b\right\rangle \rightarrow X\left\langle a\right\rangle \)が存在する。
ここで包含写像を\(i:X\left\langle a\right\rangle \rightarrow X\left\langle b\right\rangle \)とすると、\(f\)と\(i\)は共に順序を保つ単射となるので合成写像\(i\circ f\)も順序を保つ単射となる。
従って\(f\left(a\right)\precneqq a\)なので\(\left(i\circ f\right)\left(a\right)=f\left(a\right)\precneqq a\)となる。
しかし補題より、\(i\circ f:X\left\langle a\right\rangle \rightarrow X\left\langle a\right\rangle \)は順序を保つ単射であるので、任意の\(a\in X\)に対し\(a\preceq\left(i\circ f\right)\left(a\right)\)となり矛盾。
従って背理法より、\(\left(X\left\langle a\right\rangle ,\preceq\right)\ncong\left(X\left\langle b\right\rangle ,\preceq\right)\)となる。
故に題意は成り立つ。
背理法により示す。
順序同型\(\left(X\left\langle a\right\rangle ,\preceq\right)\simeq\left(X\left\langle b\right\rangle ,\preceq\right)\)であると仮定する。
このとき、順序同型であるので順序を保つ単射\(f:X\left\langle b\right\rangle \rightarrow X\left\langle a\right\rangle \)が存在する。
ここで包含写像を\(i:X\left\langle a\right\rangle \rightarrow X\left\langle b\right\rangle \)とすると、\(f\)と\(i\)は共に順序を保つ単射となるので合成写像\(i\circ f\)も順序を保つ単射となる。
従って\(f\left(a\right)\precneqq a\)なので\(\left(i\circ f\right)\left(a\right)=f\left(a\right)\precneqq a\)となる。
しかし補題より、\(i\circ f:X\left\langle a\right\rangle \rightarrow X\left\langle a\right\rangle \)は順序を保つ単射であるので、任意の\(a\in X\)に対し\(a\preceq\left(i\circ f\right)\left(a\right)\)となり矛盾。
従って背理法より、\(\left(X\left\langle a\right\rangle ,\preceq\right)\ncong\left(X\left\langle b\right\rangle ,\preceq\right)\)となる。
故に題意は成り立つ。
2つの整列集合\(\left(X_{1},\preceq_{1}\right),\left(X_{2},\preceq_{2}\right)\)があり部分集合\(X_{3}\subseteq X_{1}\)を\(X_{3}=\left\{ x_{1}\in X_{1};\exists x_{2}\in X_{2},X_{1}\left\langle x_{1}\right\rangle \simeq X\left\langle x_{2}\right\rangle \right\} \)とする。
このとき、\(X_{3}=X_{1}\)またはある\(y_{1}\in X_{1}\)が唯1つ存在し\(X_{3}=X_{1}\left\langle y_{1}\right\rangle \)となる。
このとき、\(X_{3}=X_{1}\)またはある\(y_{1}\in X_{1}\)が唯1つ存在し\(X_{3}=X_{1}\left\langle y_{1}\right\rangle \)となる。
\(X_{3}=X_{1}\)のときは明らかに成り立つので\(X_{3}\ne X_{1}\)とする。
このとき、\(X_{1}\setminus X_{3}\ne\emptyset\)であり、\(X_{1}\setminus X_{3}\)\(\subseteq X_{1}\)は整列集合\(\left(X_{1},\preceq_{1}\right)\)の部分集合なので、\(\min\left(X_{1}\setminus X_{3}\right)\)が存在する。
\(\min\left(X_{1}\setminus X_{3}\right)\)は\(X_{1}\)の元かつ\(X_{3}\)の元ではない最小の元なのでそれより小さい元\(X_{1}\left\langle \min\left(X_{1}\setminus X_{3}\right)\right\rangle \)は全て\(X_{3}\)に含まれ\(X_{1}\left\langle \min\left(X_{1}\setminus X_{3}\right)\right\rangle \subseteq X_{3}\)となる。
ここで、ある\(a_{1}\in X_{3}\)が存在し、\(\min\left(X_{1}\setminus X_{3}\right)\prec_{1}a_{1}\)であると仮定する。
\(X_{3}\)の定義より、ある\(a_{2}\in X_{2}\)が存在し、\(X_{1}\left\langle a_{1}\right\rangle \simeq X_{2}\left\langle a_{2}\right\rangle \)となり順序同型写像\(f:X_{1}\left\langle a_{1}\right\rangle \rightarrow X_{2}\left\langle a_{2}\right\rangle ,x\mapsto f\left(x\right)\)が存在する。
このとき、\(\min\left(X_{1}\setminus X_{3}\right)\prec_{1}a_{1}\)より、\(f\)は\(X_{1}\left\langle \min\left(X_{1}\setminus X_{3}\right)\right\rangle \)から\(X_{2}\left\langle f\left(\min\left(X_{1}\setminus X_{3}\right)\right)\right\rangle \)への順序同型写像となり、\(X_{1}\left\langle \min\left(X_{1}\setminus X_{3}\right)\right\rangle \simeq X_{2}\left\langle f\left(\min\left(X_{1}\setminus X_{3}\right)\right)\right\rangle \)となる。
これより、\(X_{3}\)の定義から\(\min\left(X_{1}\setminus X_{3}\right)\in X_{3}\)となるが\(\min\left(X_{1}\setminus X_{3}\right)\notin X_{3}\)なので矛盾。
したがって背理法より、任意の\(a_{1}\in X_{3}\)に対し、\(a_{1}\preceq_{1}\min\left(X_{1}\setminus X_{3}\right)\)が成り立つが、\(a_{1}\ne_{1}\min\left(X_{1}\setminus X_{3}\right)\)なので\(a_{1}\prec_{1}\min\left(X_{1}\setminus X_{3}\right)\)となる。
これより、\(a_{1}\in X_{1}\left\langle \min\left(X_{1}\setminus X_{3}\right)\right\rangle \)なので、\(X_{3}\subseteq X_{1}\left\langle \min\left(X_{1}\setminus X_{3}\right)\right\rangle \)となり、また、\(X_{1}\left\langle \min\left(X_{1}\setminus X_{3}\right)\right\rangle \subseteq X_{3}\)であるので、\(X_{3}=X_{1}\left\langle \min\left(X_{1}\setminus X_{3}\right)\right\rangle \)となる。
故に\(y_{1}=\min\left(X_{1}\setminus X_{3}\right)\)とおくと、\(X_{3}=X_{1}\left\langle y_{1}\right\rangle \)となり、また、前の補題より一意的なので題意は成り立つ。
このとき、\(X_{1}\setminus X_{3}\ne\emptyset\)であり、\(X_{1}\setminus X_{3}\)\(\subseteq X_{1}\)は整列集合\(\left(X_{1},\preceq_{1}\right)\)の部分集合なので、\(\min\left(X_{1}\setminus X_{3}\right)\)が存在する。
\(\min\left(X_{1}\setminus X_{3}\right)\)は\(X_{1}\)の元かつ\(X_{3}\)の元ではない最小の元なのでそれより小さい元\(X_{1}\left\langle \min\left(X_{1}\setminus X_{3}\right)\right\rangle \)は全て\(X_{3}\)に含まれ\(X_{1}\left\langle \min\left(X_{1}\setminus X_{3}\right)\right\rangle \subseteq X_{3}\)となる。
ここで、ある\(a_{1}\in X_{3}\)が存在し、\(\min\left(X_{1}\setminus X_{3}\right)\prec_{1}a_{1}\)であると仮定する。
\(X_{3}\)の定義より、ある\(a_{2}\in X_{2}\)が存在し、\(X_{1}\left\langle a_{1}\right\rangle \simeq X_{2}\left\langle a_{2}\right\rangle \)となり順序同型写像\(f:X_{1}\left\langle a_{1}\right\rangle \rightarrow X_{2}\left\langle a_{2}\right\rangle ,x\mapsto f\left(x\right)\)が存在する。
このとき、\(\min\left(X_{1}\setminus X_{3}\right)\prec_{1}a_{1}\)より、\(f\)は\(X_{1}\left\langle \min\left(X_{1}\setminus X_{3}\right)\right\rangle \)から\(X_{2}\left\langle f\left(\min\left(X_{1}\setminus X_{3}\right)\right)\right\rangle \)への順序同型写像となり、\(X_{1}\left\langle \min\left(X_{1}\setminus X_{3}\right)\right\rangle \simeq X_{2}\left\langle f\left(\min\left(X_{1}\setminus X_{3}\right)\right)\right\rangle \)となる。
これより、\(X_{3}\)の定義から\(\min\left(X_{1}\setminus X_{3}\right)\in X_{3}\)となるが\(\min\left(X_{1}\setminus X_{3}\right)\notin X_{3}\)なので矛盾。
したがって背理法より、任意の\(a_{1}\in X_{3}\)に対し、\(a_{1}\preceq_{1}\min\left(X_{1}\setminus X_{3}\right)\)が成り立つが、\(a_{1}\ne_{1}\min\left(X_{1}\setminus X_{3}\right)\)なので\(a_{1}\prec_{1}\min\left(X_{1}\setminus X_{3}\right)\)となる。
これより、\(a_{1}\in X_{1}\left\langle \min\left(X_{1}\setminus X_{3}\right)\right\rangle \)なので、\(X_{3}\subseteq X_{1}\left\langle \min\left(X_{1}\setminus X_{3}\right)\right\rangle \)となり、また、\(X_{1}\left\langle \min\left(X_{1}\setminus X_{3}\right)\right\rangle \subseteq X_{3}\)であるので、\(X_{3}=X_{1}\left\langle \min\left(X_{1}\setminus X_{3}\right)\right\rangle \)となる。
故に\(y_{1}=\min\left(X_{1}\setminus X_{3}\right)\)とおくと、\(X_{3}=X_{1}\left\langle y_{1}\right\rangle \)となり、また、前の補題より一意的なので題意は成り立つ。
整列集合の比較定理
2つの整列集合\(\left(X_{1},\preceq_{X_{!}}\right),\left(X_{2},\preceq_{X_{2}}\right)\)に対し次の3つのうち1つのみが必ず成り立つ。
\[ X_{1}\simeq X_{2}\left\langle a_{2}\right\rangle \] が成り立つ。
\[ X_{1}\left\langle a_{1}\right\rangle \simeq X_{2} \] が成り立つ。
2つの整列集合\(\left(X_{1},\preceq_{X_{!}}\right),\left(X_{2},\preceq_{X_{2}}\right)\)に対し次の3つのうち1つのみが必ず成り立つ。
(a)
\[ X_{1}\simeq X_{2} \](b)
ある\(a_{2}\in X_{2}\)が存在し、\[ X_{1}\simeq X_{2}\left\langle a_{2}\right\rangle \] が成り立つ。
(c)
ある\(a_{1}\in X_{1}\)が存在し、\[ X_{1}\left\langle a_{1}\right\rangle \simeq X_{2} \] が成り立つ。
-
\(Y_{1}\subseteq X_{1},Y_{2}\subseteq X_{2}\)を\[ \begin{cases} Y_{1}=\left\{ a_{1}\in X_{1};\exists a_{2}\in X_{2},X_{1}\left\langle a_{1}\right\rangle \simeq X_{2}\left\langle a_{2}\right\rangle \right\} \\ Y_{2}=\left\{ a_{2}\in X_{2};\exists a_{1}\in X_{1},X_{1}\left\langle a_{1}\right\rangle \simeq X_{2}\left\langle a_{2}\right\rangle \right\} \end{cases} \] とする。
補題より、任意の\(a_{1}\in Y_{1}\)に対し、ある\(a_{2}\in X_{2}\)が一意的に存在し、\(X_{1}\left\langle a_{1}\right\rangle \simeq X_{2}\left\langle a_{2}\right\rangle \)が成り立つ。
このとき、\(a_{1}\)に\(a_{2}\)を対応させると、順序同型写像\(Y_{1}\rightarrow Y_{2}\)となるので\(Y_{1}\simeq Y_{2}\)となる。
(a)(b)(c)のどれか1つが成り立つ。
補題より、\(Y_{1}=X_{1}\)または、ある\(a_{1}\in X_{1}\)が存在し\(Y_{1}=X_{1}\left\langle a_{1}\right\rangle \)となる。同様に、\(Y_{2}=X_{2}\)または、ある\(a_{2}\in X_{2}\)が存在し\(Y_{2}=X_{2}\left\langle a_{2}\right\rangle \)となる。
ここで、\(Y_{1}=X_{1}\left\langle a_{1}\right\rangle \)かつ\(Y_{2}=X_{2}\left\langle a_{2}\right\rangle \)と仮定する。
このとき、\(Y_{1}\simeq Y_{2}\)より、\(X_{1}\left\langle a_{1}\right\rangle =Y_{1}\simeq Y_{2}=X_{2}\left\langle a_{2}\right\rangle \)となるが、\(Y_{1}\)の定義より、\(a_{1}\in Y_{1}=X_{1}\left\langle a_{1}\right\rangle \)となり、矛盾。
故に背理法より、\(Y_{1}\ne X_{1}\left\langle a_{1}\right\rangle \)または\(Y_{2}\ne X_{2}\left\langle a_{2}\right\rangle \)となる。
このとき、次の3パターンに分けられる。
\[ \begin{cases} Y_{1}\ne X_{1}\left\langle a_{1}\right\rangle \land Y_{2}\ne X_{2}\left\langle a_{2}\right\rangle \\ Y_{1}\ne X_{1}\left\langle a_{1}\right\rangle \land Y_{2}=X_{2}\left\langle a_{2}\right\rangle \\ Y_{1}=X_{1}\left\langle a_{1}\right\rangle \land Y_{2}\ne X_{2}\left\langle a_{2}\right\rangle \end{cases} \] \(Y_{1}\ne X_{1}\left\langle a_{1}\right\rangle \)かつ\(Y_{2}\ne X_{2}\left\langle a_{2}\right\rangle \)ならば、\(Y_{1}=X_{1}\)かつ\(Y_{2}=X_{2}\)となり\(X_{1}=Y_{1}\simeq Y_{2}=X_{2}\)となるので(a)の\(X_{1}\simeq X_{2}\)となる。
\(Y_{1}\ne X_{1}\left\langle a_{1}\right\rangle \)かつ\(Y_{2}=X_{2}\left\langle a_{2}\right\rangle \)ならば\(Y_{1}=X_{1}\)かつ\(Y_{2}=X_{2}\left\langle a_{2}\right\rangle \)となるので、\(Y_{1}\simeq Y_{2}\)より、(b)の\(X_{1}\simeq X_{2}\left\langle a\right\rangle \)となる。
\(Y_{1}=X_{1}\left\langle a_{1}\right\rangle \)かつ\(Y_{2}\ne X_{2}\left\langle a_{2}\right\rangle \)ならば\(Y_{1}=X_{1}\left\langle a_{1}\right\rangle \)かつ\(Y_{2}=X_{2}\)となるので、\(Y_{1}\simeq Y_{2}\)より、(c)の\(X_{1}\left\langle a\right\rangle \simeq X_{2}\)となる。
これらより、 (a)(b)(c)のどれか1つは必ず成り立つ。
(a)(b)または(a)(c)は同時に成り立たない
背理法により示す。(a)(b)が同時に成り立つと仮定する。
そうすると、ある\(a_{2}\in X_{2}\)が存在し、\(X_{2}\simeq X_{1}\simeq X_{2}\left\langle a_{2}\right\rangle \)となる。
このとき、順序を保つ単射\(f:X_{2}\rightarrow X_{2},x\mapsto f\left(x\right)\)が存在するので\(f\left(a_{2}\right)\precneqq a_{2}\)となるが補題より、\(a_{2}\preceq f\left(a_{2}\right)\)であるので矛盾。
故に背理法より(a)(b)が同時に成り立たない。
同様に(a)(c)も同時に成り立たない。
(b)(c)は同時に成り立たない
背理法により示す。(b)(c)が同時に成り立つと仮定する。
このとき、ある\(a_{1}\in X_{1},a_{2}\in X_{2}\)が存在し、\(X_{1}\simeq X_{2}\left\langle a_{2}\right\rangle \)かつ\(X_{1}\left\langle a_{1}\right\rangle \simeq X_{2}\)なので、\(X_{1}\simeq X_{2}\left\langle a_{2}\right\rangle \)\(\subseteq X_{2}\simeq X_{1}\left\langle a_{1}\right\rangle \)となる。
また、\(X_{1}\left\langle a_{1}\right\rangle \subseteq X_{1}\)でもあるので、\(X_{1}\simeq X_{1}\left\langle a_{1}\right\rangle \)となる。
従って順序を保つ単射\(f:X_{1}\rightarrow X_{1},x\mapsto f\left(x\right)\)が存在し\(f\left(a_{1}\right)\precneqq a_{1}\)となるが補題より\(a_{1}\preceq f\left(a_{1}\right)\)であるので矛盾。
故に背理法より (b)(c)は同時に成り立たない。
-
これらより、 (a)(b)(c)のどれか1つは必ず成り立ち、3つのうち2つが同時に成り立つことはないので題意は成り立つ。ページ情報
タイトル | 整列集合の比較定理 |
URL | https://www.nomuramath.com/b1o197sm/ |
SNSボタン |
有向集合と有向点列の定義
\[
\forall a,b\in\Lambda,\exists c\in\Lambda,a\preceq c\land b\preceq c
\]
整列可能定理
任意の集合は適当な順序を定めることによって整列集合にできる。
順序写像かつ順序単射であることと順序埋め込み写像は同値
デデキント切断の定義
\[
a\in A\land b\in B\rightarrow a\preceq b
\]