集合と関係 (7)Tukeyの補題
順序集合$~(X,R)~$の部分集合$~C\subset X~$が、$R~$によって全順序集合になっているとき、$C~$を$~X~$の鎖という。
集合族$~\mathcal{A}~$が条件 $$ A\in\mathcal{A}\Longleftrightarrow({}^{\forall}B\subset A,B:有限\Longrightarrow B\in\mathcal{A}) $$ を満たすとき、$\mathcal{A}~$は有限特性をもつという。
補題6
$\mathcal{A}~$を有限特性をもつ空でない集合族とする。このとき、任意の鎖$~\mathcal{C}\subset\mathcal{A}~$に対して、$\displaystyle\bigcup\mathcal{C}\in\mathcal{A}~$となる。
$\mathcal{A}~$の任意の鎖$~\mathcal{C}~$をとる。
$\displaystyle B\subset\bigcup\mathcal{C}~$を任意の有限部分集合とする。
$B~$は有限なので$~B=\{b_1,b_2,\dots,b_n\}~$とおく。
$\displaystyle B\subset\bigcup\mathcal{C}~$より各$~i\in\{1,\dots,n\}~$に対して、$b_i\in C_i~$となるように$~C_i\in\mathcal{C}~$がとれる。
$\mathcal{C}~$は鎖なので、ある$~n_0\in\{1,\dots,n\}~$があり、 $$ {}^{\forall}i\in\{1,\dots,n\},C_i\subset C_{n_0} $$ となる。 よって、$B\subset C_{n_0}~$となる。
$C_{n_0}~$は$~\mathcal{A}~$の元であり、$B\subset C_{n_0}~$は有限なので、$\mathcal{A}~$の有限特性より$~B\in\mathcal{A}~$である。
$\displaystyle\bigcup\mathcal{C}~$の任意の有限部分集合$~B~$が$~B\in\mathcal{A}~$となったので、$\displaystyle\bigcup\mathcal{C}\in\mathcal{A}~$である。
$$\square$$
$\displaystyle B\subset\bigcup\mathcal{C}~$を任意の有限部分集合とする。
$B~$は有限なので$~B=\{b_1,b_2,\dots,b_n\}~$とおく。
$\displaystyle B\subset\bigcup\mathcal{C}~$より各$~i\in\{1,\dots,n\}~$に対して、$b_i\in C_i~$となるように$~C_i\in\mathcal{C}~$がとれる。
$\mathcal{C}~$は鎖なので、ある$~n_0\in\{1,\dots,n\}~$があり、 $$ {}^{\forall}i\in\{1,\dots,n\},C_i\subset C_{n_0} $$ となる。 よって、$B\subset C_{n_0}~$となる。
$C_{n_0}~$は$~\mathcal{A}~$の元であり、$B\subset C_{n_0}~$は有限なので、$\mathcal{A}~$の有限特性より$~B\in\mathcal{A}~$である。
$\displaystyle\bigcup\mathcal{C}~$の任意の有限部分集合$~B~$が$~B\in\mathcal{A}~$となったので、$\displaystyle\bigcup\mathcal{C}\in\mathcal{A}~$である。
定理7(Tukeyの補題)
有限特性をもつ空でない集合族$~\mathcal{A}~$に対して、順序集合$~(\mathcal{A},\subset)~$は極大元をもつ。
$(\mathcal{A},\subset)~$が極大元をもたないと仮定して矛盾を導く。
任意の$~A\in\mathcal{A}~$は極大元ではないので、$A\subsetneq A'~$となる$~A'\in\mathcal{A}~$がとれる。
各$~A\in\mathcal{A}~$に対して、そのような$~A'\in\mathcal{A}~$をとり$~f(A)~$とする。
部分族$~\mathcal{B}\subset\mathcal{A}~$が
$\mathcal{A}~$のすべての帰納的部分族の共通部分を$~\mathcal{B}_0~$とする。
\[
\mathcal{B}_1:=\{A\in\mathcal{B}_0\mid{}^{\forall}B\in\mathcal{B}_0,B\subsetneq A\Longrightarrow
f(B)\subset
A\}
\]
とおき、各$~A\in\mathcal{B}_1~$に対し
\[
\mathcal{B}_A:=\{B\in\mathcal{B}_0\mid B\subset A~または~f(A)\subset B\}
\]
とする。
任意の$~A\in\mathcal{B}_1~$について、$\mathcal{B}_A\subset\mathcal{B}_0~$で$~\mathcal{B}_A~$は帰納的なので、$\mathcal{B}_0~$の定義より$~\mathcal{B}_0\subset\mathcal{B}_A~$となり、$\mathcal{B}_0=\mathcal{B}_A~$となる。
$\mathcal{B}_1\subset\mathcal{B}_0~$で$~\mathcal{B}_1~$は帰納的なので、$\mathcal{B}_0~$の定義より$~\mathcal{B}_0\subset\mathcal{B}_1~$となり、$\mathcal{B}_0=\mathcal{B}_1~$となる。
任意に$~B,B'\in\mathcal{B}_0~$をとる。
このとき、$B\in\mathcal{B}_0=\mathcal{B}_1~$かつ$~B'\in\mathcal{B}_0=\mathcal{B}_B~$なので、$B'\subset B~$または$~B\subset f(B)\subset B'~$となる。
よって、$\mathcal{B}_0~$は$~\mathcal{A}~$の鎖である。
$\displaystyle A:=\bigcup\mathcal{B}_0~$とすると、$\mathcal{B}_0~$は$~\mathcal{A}~$の鎖、$\mathcal{B}_0\subset\mathcal{B}_0~$であり、$\mathcal{B}_0~$が帰納的なので、$A\in\mathcal{B}_0~$となる。
よって、 \[ \bigcup\mathcal{B}_0=A\subsetneq f(A)\in\mathcal{B}_0 \] となり、これは矛盾である。
以上よりTukeyの補題は示された。
$$\square$$
任意の$~A\in\mathcal{A}~$は極大元ではないので、$A\subsetneq A'~$となる$~A'\in\mathcal{A}~$がとれる。
各$~A\in\mathcal{A}~$に対して、そのような$~A'\in\mathcal{A}~$をとり$~f(A)~$とする。
部分族$~\mathcal{B}\subset\mathcal{A}~$が
\begin{align}
(1)&~\emptyset\in\mathcal{B}\\
(2)&~{}^{\forall}B\in\mathcal{B},f(B)\in\mathcal{B}\\
(3)&~\mathcal{A}~の任意の鎖~\mathcal{C}~に対し、\mathcal{C}\subset\mathcal{B}\Longrightarrow\bigcup\mathcal{C}\in\mathcal{B}
\end{align}
を満たすとき、$\mathcal{B}~$は($f~$に関して)帰納的であるという。主張7.1
$\mathcal{A}~$は帰納的である。
$\mathcal{A}\neq\emptyset~$なので元$~A\in\mathcal{A}~$がとれ、$\emptyset\subset\mathcal{A}~$は有限なので$~\emptyset\in\mathcal{A}~$となる。
$f~$の定義より、任意の$~A\in\mathcal{A}~$に対して$~f(A)\in\mathcal{A}~$となる。
補題6より、$\mathcal{A}~$の任意の鎖$~\mathcal{C}~$に対し$~\displaystyle\bigcup\mathcal{C}\in\mathcal{A}~$となる。
$$\square$$
$f~$の定義より、任意の$~A\in\mathcal{A}~$に対して$~f(A)\in\mathcal{A}~$となる。
補題6より、$\mathcal{A}~$の任意の鎖$~\mathcal{C}~$に対し$~\displaystyle\bigcup\mathcal{C}\in\mathcal{A}~$となる。
$\mathcal{A}~$のすべての帰納的部分族の共通部分を$~\mathcal{B}_0~$とする。
主張7.2
$\mathcal{B}_0~$は帰納的である。
すべての帰納的部分族は条件$(1)$より、空集合を含むので$~\emptyset\in\mathcal{B}_0~$である。
任意の元$~B\in\mathcal{B}_0~$をとると、$B~$はすべての帰納的部分族に含まれる。
よって、すべての帰納的部分族に$~f(B)~$が含まれるので、$~f(B)\in\mathcal{B}_0~$となる。
$\mathcal{A}~$の任意の鎖$~\mathcal{C}~$をとり、$\mathcal{C}\subset\mathcal{B}_0~$とする。
このとき、$\mathcal{C}~$は任意の帰納的部分族の部分集合なので、$\displaystyle\bigcup\mathcal{C}~$は任意の帰納的部分族に含まれる。
よって、$\displaystyle\bigcup\mathcal{C}\in\mathcal{B}_0~$である。
$$\square$$
任意の元$~B\in\mathcal{B}_0~$をとると、$B~$はすべての帰納的部分族に含まれる。
よって、すべての帰納的部分族に$~f(B)~$が含まれるので、$~f(B)\in\mathcal{B}_0~$となる。
$\mathcal{A}~$の任意の鎖$~\mathcal{C}~$をとり、$\mathcal{C}\subset\mathcal{B}_0~$とする。
このとき、$\mathcal{C}~$は任意の帰納的部分族の部分集合なので、$\displaystyle\bigcup\mathcal{C}~$は任意の帰納的部分族に含まれる。
よって、$\displaystyle\bigcup\mathcal{C}\in\mathcal{B}_0~$である。
主張7.3
任意の$~A\in\mathcal{B}_1~$に対して、$\mathcal{B}_A~$は帰納的である。
主張7.2より$~\emptyset\in\mathcal{B}_0~$であり、$\emptyset\subset
A~$なので$~\emptyset\in\mathcal{B}_A~$となる。
$B\in\mathcal{B}_A~$を任意にとると、$B\in\mathcal{B}_0~$なので$~f(B)\in\mathcal{B}_0~$である。
$B\subsetneq A~$なら、$A\in\mathcal{B}_1~$なので$~f(B)\subset A~$となる。
$B=A~$なら、$f(B)=f(A)~$なので$~f(A)\subset f(B)~$である。
$f(A)\subset B~$なら、$f(A)\subset B\subset f(B)~$となる。
よって、$f(B)\in\mathcal{B}_A~$である。
$\mathcal{A}~$の任意の鎖$~\mathcal{C}~$をとり、$\mathcal{C}\subset\mathcal{B}_A~$とする。
このとき、$\mathcal{C}\subset\mathcal{B}_0~$かつ$~\mathcal{B}_0~$が帰納的なので$~\displaystyle\bigcup\mathcal{C}\in\mathcal{B}_0~$である。
${}^{\forall}C\in\mathcal{C},C\subset A~$なら、$~\displaystyle\bigcup\mathcal{C}\subset A~$となる。
$C\not\subset A~$となる$~C\in\mathcal{C}~$があるなら、$C\in\mathcal{C}\subset\mathcal{B}_A~$より$~\displaystyle f(A)\subset C\subset\bigcup\mathcal{C}~$である。
よって、$\displaystyle\bigcup\mathcal{C}\in\mathcal{B}_A~$となる。
$$\square$$
$B\in\mathcal{B}_A~$を任意にとると、$B\in\mathcal{B}_0~$なので$~f(B)\in\mathcal{B}_0~$である。
$B\subsetneq A~$なら、$A\in\mathcal{B}_1~$なので$~f(B)\subset A~$となる。
$B=A~$なら、$f(B)=f(A)~$なので$~f(A)\subset f(B)~$である。
$f(A)\subset B~$なら、$f(A)\subset B\subset f(B)~$となる。
よって、$f(B)\in\mathcal{B}_A~$である。
$\mathcal{A}~$の任意の鎖$~\mathcal{C}~$をとり、$\mathcal{C}\subset\mathcal{B}_A~$とする。
このとき、$\mathcal{C}\subset\mathcal{B}_0~$かつ$~\mathcal{B}_0~$が帰納的なので$~\displaystyle\bigcup\mathcal{C}\in\mathcal{B}_0~$である。
${}^{\forall}C\in\mathcal{C},C\subset A~$なら、$~\displaystyle\bigcup\mathcal{C}\subset A~$となる。
$C\not\subset A~$となる$~C\in\mathcal{C}~$があるなら、$C\in\mathcal{C}\subset\mathcal{B}_A~$より$~\displaystyle f(A)\subset C\subset\bigcup\mathcal{C}~$である。
よって、$\displaystyle\bigcup\mathcal{C}\in\mathcal{B}_A~$となる。
任意の$~A\in\mathcal{B}_1~$について、$\mathcal{B}_A\subset\mathcal{B}_0~$で$~\mathcal{B}_A~$は帰納的なので、$\mathcal{B}_0~$の定義より$~\mathcal{B}_0\subset\mathcal{B}_A~$となり、$\mathcal{B}_0=\mathcal{B}_A~$となる。
主張7.4
$\mathcal{B}_1~$は帰納的である。
任意の$~B\in\mathcal{B}_0~$について、「$B\subsetneq\emptyset\Rightarrow f(B)\subset
\emptyset$」は無内容に成立する。
したがって、$\emptyset\in\mathcal{B}_1~$である。
$A\in\mathcal{B}_1~$を任意にとると、$A\in\mathcal{B}_0~$なので$~f(A)\in\mathcal{B}_0~$である。
任意に$~B\in\mathcal{B}_0~$をとり、$B\subsetneq f(A)~$とする。
$B\in\mathcal{B}_0=\mathcal{B}_A~$なので$~B\subset A~$となる。
$B\subsetneq A~$なら、$A\in\mathcal{B}_1~$より$~f(B)\subset A\subset f(A)~$である。
$B=A~$なら、$f(B)=f(A)~$なので$~f(B)\subset f(A)~$である。
よって、$f(A)\in\mathcal{B}_1~$となる。
$\mathcal{A}~$の任意の鎖$~\mathcal{C}~$をとり、$\mathcal{C}\subset\mathcal{B}_1~$とする。
このとき、$\mathcal{C}\subset\mathcal{B}_0~$かつ$~\mathcal{B}_0~$が帰納的なので$~\displaystyle\bigcup\mathcal{C}\in\mathcal{B}_0~$である。
任意に$~B\in\mathcal{B}_0~$をとり、$\displaystyle B\subsetneq \bigcup\mathcal{C}~$とする。
${}^{\forall}A\in\mathcal{C},f(A)\subset B~$なら、$\displaystyle B\subsetneq\bigcup\mathcal{C}\subset\bigcup\{f(A)\mid A\in\mathcal{C}\}\subset B~$となる。
したがって、矛盾となるので、$f(A)\not\subset B~$となる$~A\in\mathcal{C}~$がある。
このとき、$A\in\mathcal{C}\subset\mathcal{B}_1~$かつ$~B\in\mathcal{B}_0=\mathcal{B}_A~$なので、$B\subset A~$となる。
$B\subsetneq A~$なら、$A\in\mathcal{B}_1~$より$~\displaystyle f(B)\subset A\subset\bigcup\mathcal{C}~$となる。
$B=A~$なら、$\displaystyle\bigcup\mathcal{C}\in\mathcal{B}_0=\mathcal{B}_A~$より、$\displaystyle\bigcup\mathcal{C}\subset A=B~$または$~\displaystyle f(B)=f(A)\subset\bigcup\mathcal{C}~$が成り立つ。
今$~\displaystyle B\subsetneq \bigcup\mathcal{C}~$としているので$~\displaystyle f(B)\subset\bigcup\mathcal{C}~$となる。
よって、$\displaystyle\bigcup\mathcal{C}\in\mathcal{B}_1~$である。
$$\square$$
したがって、$\emptyset\in\mathcal{B}_1~$である。
$A\in\mathcal{B}_1~$を任意にとると、$A\in\mathcal{B}_0~$なので$~f(A)\in\mathcal{B}_0~$である。
任意に$~B\in\mathcal{B}_0~$をとり、$B\subsetneq f(A)~$とする。
$B\in\mathcal{B}_0=\mathcal{B}_A~$なので$~B\subset A~$となる。
$B\subsetneq A~$なら、$A\in\mathcal{B}_1~$より$~f(B)\subset A\subset f(A)~$である。
$B=A~$なら、$f(B)=f(A)~$なので$~f(B)\subset f(A)~$である。
よって、$f(A)\in\mathcal{B}_1~$となる。
$\mathcal{A}~$の任意の鎖$~\mathcal{C}~$をとり、$\mathcal{C}\subset\mathcal{B}_1~$とする。
このとき、$\mathcal{C}\subset\mathcal{B}_0~$かつ$~\mathcal{B}_0~$が帰納的なので$~\displaystyle\bigcup\mathcal{C}\in\mathcal{B}_0~$である。
任意に$~B\in\mathcal{B}_0~$をとり、$\displaystyle B\subsetneq \bigcup\mathcal{C}~$とする。
${}^{\forall}A\in\mathcal{C},f(A)\subset B~$なら、$\displaystyle B\subsetneq\bigcup\mathcal{C}\subset\bigcup\{f(A)\mid A\in\mathcal{C}\}\subset B~$となる。
したがって、矛盾となるので、$f(A)\not\subset B~$となる$~A\in\mathcal{C}~$がある。
このとき、$A\in\mathcal{C}\subset\mathcal{B}_1~$かつ$~B\in\mathcal{B}_0=\mathcal{B}_A~$なので、$B\subset A~$となる。
$B\subsetneq A~$なら、$A\in\mathcal{B}_1~$より$~\displaystyle f(B)\subset A\subset\bigcup\mathcal{C}~$となる。
$B=A~$なら、$\displaystyle\bigcup\mathcal{C}\in\mathcal{B}_0=\mathcal{B}_A~$より、$\displaystyle\bigcup\mathcal{C}\subset A=B~$または$~\displaystyle f(B)=f(A)\subset\bigcup\mathcal{C}~$が成り立つ。
今$~\displaystyle B\subsetneq \bigcup\mathcal{C}~$としているので$~\displaystyle f(B)\subset\bigcup\mathcal{C}~$となる。
よって、$\displaystyle\bigcup\mathcal{C}\in\mathcal{B}_1~$である。
$\mathcal{B}_1\subset\mathcal{B}_0~$で$~\mathcal{B}_1~$は帰納的なので、$\mathcal{B}_0~$の定義より$~\mathcal{B}_0\subset\mathcal{B}_1~$となり、$\mathcal{B}_0=\mathcal{B}_1~$となる。
任意に$~B,B'\in\mathcal{B}_0~$をとる。
このとき、$B\in\mathcal{B}_0=\mathcal{B}_1~$かつ$~B'\in\mathcal{B}_0=\mathcal{B}_B~$なので、$B'\subset B~$または$~B\subset f(B)\subset B'~$となる。
よって、$\mathcal{B}_0~$は$~\mathcal{A}~$の鎖である。
$\displaystyle A:=\bigcup\mathcal{B}_0~$とすると、$\mathcal{B}_0~$は$~\mathcal{A}~$の鎖、$\mathcal{B}_0\subset\mathcal{B}_0~$であり、$\mathcal{B}_0~$が帰納的なので、$A\in\mathcal{B}_0~$となる。
よって、 \[ \bigcup\mathcal{B}_0=A\subsetneq f(A)\in\mathcal{B}_0 \] となり、これは矛盾である。
以上よりTukeyの補題は示された。