半順序集合の極大元の存在
半順序集合\(\left( X,\leq \right) \)が与えられているものとします。つまり、\(\leq \)は\(X\)上に定義された二項関係であり、反射律、反対称律、推移律を満たすということ、すなわち、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in X:x\leq x \\
&&\left( O_{2}\right) \ \forall x,y\in X:\left[ \left( x\leq y\wedge y\leq
x\right) \Rightarrow x=y\right] \\
&&\left( O_{3}\right) \ \forall x,y,z\in X:\left[ \left( x\leq y\wedge y\leq
z\right) \Rightarrow x\leq z\right]
\end{eqnarray*}が成り立つということです。
半順序集合\(X\)に属するある要素\(a\)より大きい要素が\(X\)の中に存在しない場合には、つまり、\begin{equation*}\exists a\in X,\ \forall x\in X:\lnot \left( a<x\right)
\end{equation*}が成り立つ場合には、この要素\(a\)を半順序集合\(X\)の極大元(maximal element)と呼びます。\(X\)の極大元は\(X\)の要素である必要があります。\(X\)に属さない要素は\(X\)の極大元にはなり得ません。以下の条件\begin{equation*}\exists a\in X,\ \forall x\in X:\left( a\leq x\Rightarrow x=a\right)
\end{equation*}が成り立つことは、\(a\)が\(X\)の極大元であるための必要十分条件です。
\end{equation*}に注目します。\(\left( \left[ 0,1\right] ,\leq \right) \)は全順序集合です。\(1\in \left[ 0,1\right] \)に対して、\begin{equation}1\leq x \quad \cdots (1)
\end{equation}を満たす\(x\in \left[ 0,1\right] \)を任意に選んだとき、\(\left[ 0,1\right] \)の定義より、\begin{equation}x\leq 1 \quad \cdots (2)
\end{equation}が成り立ちます。\(\left(1\right) ,\left( 2\right) \)および\(\leq \)の反射律より、\begin{equation*}x=1
\end{equation*}が成り立つため、\(1\)は\(\left[ 0,1\right] \)の極大元であることが明らかになりました。
半順序集合は極大元を持つとは限りません。
\end{equation*}が成り立ちます。つまり、\(a\)より大きい要素が\(\mathbb{Z} \)の中に存在しますが、以上の事実は\(a\)が\(\mathbb{Z} \)の極大元であることと矛盾します。したがって背理法より、\(\mathbb{Z} \)の極大元が存在しないことが明らかになりました。
半順序集合の中には極大元を持つものと極大元を持たないものの双方が存在することが明らかになりました。ツォルンの補題(Zorn’s lemma)は半順序集合が極大元を持つための条件を明らかにします。
ツォルンの補題の主張
半順序集合\(\left( X,\leq \right) \)の部分集合\(A\subset X\)が全順序部分集合であることとは、\(\leq \)が\(A\)上において反射律、反対称律、推移律に加えて完備律を満たすこと、すなわち、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in A:x\leq x \\
&&\left( O_{2}\right) \ \forall x,y\in A:\left[ \left( x\leq y\wedge y\leq
x\right) \Rightarrow x=y\right] \\
&&\left( O_{3}\right) \ \forall x,y,z\in A:\left[ \left( x\leq y\wedge y\leq
z\right) \Rightarrow x\leq z\right] \\
&&\left( O_{4}\right) \ \forall x,y\in A:x\leq y\vee y\leq x
\end{eqnarray*}が成り立つことを意味します。空集合\(\phi\subset X\)もまた全順序部分集合とみなします。
半順序集合\(X\)の全順序部分集合\(A\subset X\)を任意に選んだとき、\(A\)が上に有界であることが保証される場合は、すなわち、\begin{equation*}\exists U\in X,\ \forall x\in A:x\leq U
\end{equation*}が成り立つ場合には、\(X\)の極大元が必ず存在します。以上がツォルンの補題の主張です。
半順序集合\(\left( X,\leq \right) \)が与えられているものとする。\(X\)の任意の全順序部分集合が上に有界であるならば、\(X\)の極大元が存在する。
ツォルンの補題を証明する前に、具体例を通じて主張の意味を確認します。
\end{equation*}に注目します。\(\left( \left[ 0,1\right] ,\leq \right) \)は全順序集合です。部分集合\(A\subset \left[ 0,1\right] \)を任意に選んだとき、\(\left( A,\leq \right) \)は全順序部分集合になります。以上より、\(\left[ 0,1\right] \)のすべての部分集合が全順序部分集合であることが明らかになりました。しかも、\(A\subset \left[ 0,1\right] \)ゆえに、\begin{equation*}\exists 1\in \left[ 0,1\right] ,\ \forall x\in A:x\leq 1
\end{equation*}が成り立つため、\(A\)は上に有界です。以上より、\(\left[ 0,1\right] \)のすべての全順序部分集合が上に有界であることが明らかになりました。したがって、ツォルンの補題より、\(\left[ 0,1\right] \)は極大元を持つはずです。実際、先に確認したように、\(1\)は\(\left[ 0,1\right] \)の極大元です。以上の結果はツォルンの補題と整合的です。
\end{equation*}が成り立つからです。以上の結果はツォルンの補題と整合的です。
ツォルンの補題の証明
ツォルンの補題の対偶を証明します。つまり、半順序集合\(\left(X,\leq \right) \)の極大元が存在しない場合には、上に有界ではない\(X\)上の全順序部分集合\(A\)が存在することを示すことが目標です。背理法を用いてこれを証明します。つまり、\(X\)の極大元が存在せず、なおかつ\(X\)の任意の全順序部分集合\(A\)が上に有界であるものと仮定して矛盾を導きます。
全順序部分集合\(A\subset X\)を任意に選びます。仮定より\(A\)は上に有界であるため上界が存在します。つまり、\begin{equation}\exists U\in X,\ \forall x\in A:x\leq U \quad \cdots (1)
\end{equation}が成り立ちます。その一方で、仮定より\(X\)の極大元が存在しないため\(U\)は\(X\)の極大元ではなく、したがって、\begin{equation}\exists y\in X:U<y \quad \cdots (2)
\end{equation}が成り立ちます。\(\left(1\right) ,\left( 2\right) \)より、\begin{equation*}\exists y\in X,\ \forall x\in C:x<y
\end{equation*}が成り立つことが明らかになりました。そこで、このような\(X\)の要素\(y\)を\(A\)の狭義の上界(strict upper bound of \(A\))と呼ぶこととします。
以上の事実を踏まえると、選択公理を認める場合、それぞれの全順序部分集合\(A\subset X\)に対して、\(A\)の狭義の上界\(f\left( A\right) \in X\)を像として定める選択関数\(f\)の存在を保証できます。つまり、全順序部分集合\(A\subset X\)を任意に選んだとき、それに対して選択関数\(f\)が定める値\(f\left( A\right) \in X\)は、以下の条件\begin{equation*}\forall x\in A:x<f\left( A\right)
\end{equation*}を満たすということです。
半順序集合\(\left( X,\leq \right) \)の部分集合\(A\subset X\)が以下の2つの条件を満たす場合、\(A\)を適合集合(conforming set)と呼びます。
1つ目の条件は、適合集合\(A\)は整列集合であるということです。つまり、\(A\)は\(X\)の全順序部分集合であるとともに、\(A\)の任意の非空な部分集合が最小元を持つということです。
1つ目の条件より\(A\)は\(X\)上の全順序部分集合であるため、その要素\(x\in A\)を選んだとき、\(x\)に関する\(A\)の狭義の始切片\begin{equation*}I\left( A,x\right) =\left\{ y\in A\ |\ y<x\right\}
\end{equation*}が定義可能です。これは\(x\)より小さい\(A\)の要素をすべて集めることにより得られる集合です。\(I\left( A,x\right) \subset A\)であるため始切片\(\left(I\left( x\right) ,\leq \right) \)もまた\(X\)の全順序部分集合です。その上で、\begin{equation*}\forall x\in A:x=f\left( I\left( A,x\right) \right)
\end{equation*}が成り立つことを2つ目の条件とします。つまり、適合集合\(A\)の要素\(x\)を任意に選んだとき、\(x\)は狭義の始切片\(I\left( A,x\right) \)の狭義の上界であるということです。
改めて整理すると、半順序集合\(\left( X,\leq \right) \)の部分集合\(A\subset X\)が適合集合であることとは、\(A\)が整列集合であるとともに、\begin{equation*}\forall x\in A:x=f\left( I\left( A,x\right) \right)
\end{equation*}が成り立つことを意味します。
半順序集合の2つの異なる適合集合の間には以下の関係が成り立ちます。
\exists x &\in &B:A=I\left( B,x\right)
\end{eqnarray*}のどちらか一方が成り立つ。
以上の命題を踏まえた上で以下を示します。
\end{equation*}は\(X\)上の適合集合である。
以上を踏まえた上で、ツォルンの補題を証明します。
半順序集合\(\left( X,\leq \right) \)が与えられているものとする。さらに、選択公理を認めるものとする。\(X\)上の任意の全順序部分集合が上に有界であるならば、\(X\)の極大元が存在する。
ツォルンの補題において\(\left( X,\leq \right) \)は半順序集合であればよく、全順序集合である必要はありません。つまり、\(X\)の任意の2つの要素が比較可能であること、すなわち\(\leq \)が完備律を満たすことを要求しないということです。\(X\)の任意の全順序部分集合が上に有界であれば、\(X\)の極大元が存在することを保証できます。
ツォルンの補題は半順序集合の極大元が存在するための条件を明らかにしている一方で、極大元を具体的に特定する方法については何も語っていません。また、半順序集合の極大元は一意的であるとは限りませんが、ツォルンの補題は極大元の個数についても何も語っていません。
極小元に関するツォルンの補題
半順序集合\(\left( X,\leq \right) \)が与えられた状況を想定します。その上で、任意の\(x,y\in X\)について、以下の関係\begin{equation*}x\leq ^{\ast }y\Leftrightarrow y\leq x
\end{equation*}を満たすものとして\(X\)上の二項関係\begin{equation*}\leq ^{\ast }\subset A\times A
\end{equation*}を定義します。つまり、\(x,y\in X\)について、もとの半順序のもとで\(x\)が\(y\)以上である場合、そしてその場合にのみ、新たな二項関係\(\leq ^{\ast }\)のもとで\(y\)が\(x\)以上であるものとして\(\leq ^{\ast}\)を定義するということです。半順序\(\leq \)から以上の要領で定義される二項関係\(\leq ^{\ast }\)もまた半順序であるため、\begin{equation*}\left( X,\leq ^{\ast }\right)
\end{equation*}は半順序集合になります。
半順序集合\(\left( X,\leq \right) \)の極大元が存在するものとします。つまり、\begin{equation*}\exists a\in X,\ \forall x\in X:\lnot \left( a<x\right)
\end{equation*}が成り立つということです。半順序\(\leq ^{\ast }\)の定義より、この命題は、\begin{equation*}\exists a\in X,\ \forall x\in X:\lnot \left( x<^{\ast }a\right)
\end{equation*}と必要十分ですが、これは、半順序集合\(\left( X,\leq ^{\ast }\right) \)の極小元が存在することを意味します。逆の議論も成立するため、\(\leq \)のもとで\(X\)の極大元が存在することと、\(\leq ^{\ast }\)のもとで\(X\)の極小元が存在することは必要十分です。
半順序集合\(\left( X,\leq \right) \)の全順序部分集合\(A\subset X\)が上に有界であるものとします。つまり、\begin{equation*}\exists U\in X,\ \forall x\in A:x\leq U
\end{equation*}が成り立つということです。半順序\(\leq ^{\ast }\)の定義より、この命題は、\begin{equation*}\exists U\in X,\ \forall x\in A:U\leq ^{\ast }x
\end{equation*}と必要十分ですが、これは、半順序集合\(\left( X,\leq ^{\ast }\right) \)の全順序部分集合\(A\subset X\)が下に有界であることを意味します。逆の議論も成立するため、\(\leq \)のもとで\(A\)が上に有界であることと、\(\leq ^{\ast }\)のもとで\(A\)が下に有界であることは必要十分です。
以上の事実とツォルンの補題を踏まえると、極小元に関するツォルンの補題が導かれます。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】