テューキーの補題
テューキーの補題
有限性をもつ空でない集合族\(\mathcal{A}\)に対し、包含関係を順序とする半順序集合\(\left(\mathcal{A},\subseteq\right)\)に極大元が存在する。
ただし、選択公理を認めるとする。
有限性をもつ空でない集合族\(\mathcal{A}\)に対し、包含関係を順序とする半順序集合\(\left(\mathcal{A},\subseteq\right)\)に極大元が存在する。
ただし、選択公理を認めるとする。
テューキーの補題は選択公理と同値である。
選択公理とツォルンの補題は同値なので、ツォルンの補題とテューキーの補題が同値なのを証明する。
このとき\(\mathcal{A}\)の任意の鎖を\(\mathcal{C}\)として\(C=\bigcup\mathcal{C}\)とおき、任意の有限部分集合\(D=\left\{ d_{1},d_{2},\cdots,d_{n}\right\} \subseteq C\)をとる。
すると、任意の\(i\in\left\{ 1,2,\cdots,n\right\} \)に対しある\(A_{i}\in\mathcal{C}\)が存在して、\(d_{i}\in A_{i}\)となる。
また、\(\mathcal{C}\)は包含関係\(\subseteq\)を順序とする全順序集合なのでその部分集合\(A_{1},A_{2},\cdots,A_{n}\)も全順序集合となり、ある\(j\in\left\{ 1,2,\cdots,n\right\} \)が存在して、\(D\subseteq A_{j}\)となる。
これより、\(A_{j}\in\mathcal{C}\)\(\subseteq\mathcal{A}\)から\(A_{j}\in\mathcal{A}\)であり、集合族\(\mathcal{A}\)は有限性をもつので\(D\subseteq A_{j}\in\mathcal{A}\)より\(D\in\mathcal{A}\)となり、\(D\)の任意性より\(C\in\mathcal{A}\)となる。
従って半順序集合\(\left(\mathcal{A},\subseteq\right)\)の任意の鎖\(\mathcal{C}\)に対して、\(C=\bigcup\mathcal{C}\)は上界となるので\(\mathcal{A}\)は帰納的となる。
故にツォルンの補題より\(\mathcal{A}\)は極大元をもつのでテューキーの補題が成り立つ。
このとき、\(C\in\mathcal{C}\)ならば任意の有限部分集合\(A\subseteq C\)は\(A\in\mathcal{C}\)を満たす。
また、部分集合\(C\subseteq X\)に対し、任意の有限部分集合\(A\subseteq C\)が\(A\in\mathcal{C}\)を満たすならば\(A\)の任意性より、\(C\in\mathcal{C}\)となる。
これより、\(C\in\mathcal{C}\Leftrightarrow A\subseteq C\land\left|A\right|<\infty\rightarrow A\in\mathcal{C}\)となるので\(\mathcal{C}\)は有限性をもち、\(\left(\mathcal{C},\subseteq\right)\)にテューキーの補題を使うと、\(\mathcal{C}\)は極大元\(C_{0}\in\mathcal{C}\)をもつ。
また\(\left(X,\preceq\right)\)は帰納的で\(C_{0}\)は鎖なので\(C_{0}\)は\(X\)に上界\(x\in X\)をもつ。
このとき、ある\(y\in X\)が存在し、\(x\prec y\)を満たすと仮定すると、\(y\notin C_{0}\)となるので\(C_{0}\cup\left\{ y\right\} \supsetneq C_{0}\)も全順序集合\(\left(C_{0}\cup\left\{ y\right\} ,\preceq\right)\)となり\(X\)の鎖となるが\(C_{0}\)が\(\left(\mathcal{C},\subseteq\right)\)の極大元であることに矛盾。
従って、背理法より任意の\(y\in X\)に対し、\(x\prec y\)を満たさないので\(x\)は極大元となる。
すなわち、帰納的順序集合\(\left(X,\preceq\right)\)は極大元\(x\in X\)をもつ。
故にツォルンの補題が成り立つので\(\Leftarrow\)が示される。
また、選択公理とツォルンの補題は同値なので、選択公理とテューキーの補題が同値であることが示される。
\(\Rightarrow\)
集合族\(\mathcal{A}\)を有限性をもち空でなく、包含関係\(\subseteq\)を順序とする半順序集合\(\left(\mathcal{A},\subseteq\right)\)とする。このとき\(\mathcal{A}\)の任意の鎖を\(\mathcal{C}\)として\(C=\bigcup\mathcal{C}\)とおき、任意の有限部分集合\(D=\left\{ d_{1},d_{2},\cdots,d_{n}\right\} \subseteq C\)をとる。
すると、任意の\(i\in\left\{ 1,2,\cdots,n\right\} \)に対しある\(A_{i}\in\mathcal{C}\)が存在して、\(d_{i}\in A_{i}\)となる。
また、\(\mathcal{C}\)は包含関係\(\subseteq\)を順序とする全順序集合なのでその部分集合\(A_{1},A_{2},\cdots,A_{n}\)も全順序集合となり、ある\(j\in\left\{ 1,2,\cdots,n\right\} \)が存在して、\(D\subseteq A_{j}\)となる。
これより、\(A_{j}\in\mathcal{C}\)\(\subseteq\mathcal{A}\)から\(A_{j}\in\mathcal{A}\)であり、集合族\(\mathcal{A}\)は有限性をもつので\(D\subseteq A_{j}\in\mathcal{A}\)より\(D\in\mathcal{A}\)となり、\(D\)の任意性より\(C\in\mathcal{A}\)となる。
従って半順序集合\(\left(\mathcal{A},\subseteq\right)\)の任意の鎖\(\mathcal{C}\)に対して、\(C=\bigcup\mathcal{C}\)は上界となるので\(\mathcal{A}\)は帰納的となる。
故にツォルンの補題より\(\mathcal{A}\)は極大元をもつのでテューキーの補題が成り立つ。
\(\Leftarrow\)
\(\left(X,\preceq\right)\)を帰納的順序集合として\(\mathcal{C}\)を\(X\)の鎖全体の集合とすると\(\mathcal{C}\)は空集合ではない。このとき、\(C\in\mathcal{C}\)ならば任意の有限部分集合\(A\subseteq C\)は\(A\in\mathcal{C}\)を満たす。
また、部分集合\(C\subseteq X\)に対し、任意の有限部分集合\(A\subseteq C\)が\(A\in\mathcal{C}\)を満たすならば\(A\)の任意性より、\(C\in\mathcal{C}\)となる。
これより、\(C\in\mathcal{C}\Leftrightarrow A\subseteq C\land\left|A\right|<\infty\rightarrow A\in\mathcal{C}\)となるので\(\mathcal{C}\)は有限性をもち、\(\left(\mathcal{C},\subseteq\right)\)にテューキーの補題を使うと、\(\mathcal{C}\)は極大元\(C_{0}\in\mathcal{C}\)をもつ。
また\(\left(X,\preceq\right)\)は帰納的で\(C_{0}\)は鎖なので\(C_{0}\)は\(X\)に上界\(x\in X\)をもつ。
このとき、ある\(y\in X\)が存在し、\(x\prec y\)を満たすと仮定すると、\(y\notin C_{0}\)となるので\(C_{0}\cup\left\{ y\right\} \supsetneq C_{0}\)も全順序集合\(\left(C_{0}\cup\left\{ y\right\} ,\preceq\right)\)となり\(X\)の鎖となるが\(C_{0}\)が\(\left(\mathcal{C},\subseteq\right)\)の極大元であることに矛盾。
従って、背理法より任意の\(y\in X\)に対し、\(x\prec y\)を満たさないので\(x\)は極大元となる。
すなわち、帰納的順序集合\(\left(X,\preceq\right)\)は極大元\(x\in X\)をもつ。
故にツォルンの補題が成り立つので\(\Leftarrow\)が示される。
-
これらより、\(\Rightarrow\)と\(\Leftarrow\)が示されたので\(\Leftrightarrow\)となり、ツォルンの補題とテューキーの補題が同値であることが示された。また、選択公理とツォルンの補題は同値なので、選択公理とテューキーの補題が同値であることが示される。
ページ情報
タイトル | テューキーの補題 |
URL | https://www.nomuramath.com/r3qvb94t/ |
SNSボタン |
半順序関係と狭義半順序関係
\[
x\prec y\Leftrightarrow x\preceq y\land x\ne y
\]
順序写像・単調写像・順序反映・順序埋め込み・順序同型写像の定義
\[
a\preceq_{X}b\Rightarrow f\left(a\right)\preceq_{Y}f\left(b\right)
\]
順序を反映する写像(順序単射)ならば単射
順序集合の双対順序集合と狭義順序集合の狭義逆順序
\[
\succeq:=\left\{ \left(a,b\right)\in X^{2};b\preceq a\right\}
\]