順序部分集合の上限
集合\(A\)上に定義された二項関係\(\leq \)が半順序であることは、反射律と反対称律と推移律を満たすこと、すなわち、\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]
\end{eqnarray*}が成り立つことを意味します。集合\(A\)上の二項関係\(\leq \)が以上の3つの性質に加えて完備律\begin{equation*}\left( O_{4}\right) \ \forall x,y\in A:\left( x\leq y\vee y\leq x\right)
\end{equation*}を満たす場合には、\(\leq \)を全順序と呼びます。以降において「順序」と言う場合、それは半順序と全順序をともに指します。順序\(\leq \)が定義された集合\(A\)を順序集合と呼びます。集合\(A\)上の順序\(\leq \)が与えられたとき、任意の\(x,y\in A\)に対して、\begin{equation*}x<y\Leftrightarrow \left( x\leq y\wedge x\not=y\right)
\end{equation*}を満たすものとして定義される\(A\)上の二項関係\(<\)を狭義順序と呼びます。
順序集合\(A\)の空ではない部分集合\(X\)が与えられたとき、もとの集合\(A\)に属するある要素\(a\)が集合\(X\)に属する任意の要素以上である場合には、つまり、\begin{equation*}\exists a\in A,\ \forall x\in X:x\leq a
\end{equation*}が成り立つならば、この要素\(a\)を集合\(X\)の上界と呼びます。集合\(X\)の上界は存在するとは限りませんし、存在する場合にも一意的に定まるとは限りません。そこで、集合\(X\)の上界をすべて集めることにより得られる集合を、\begin{equation*}U\left( X\right) =\left\{ a\in A\ |\ \forall x\in X:x\leq a\right\}
\end{equation*}で表記します。\(X\)が上界を持つ場合には、すなわち、\begin{equation*}U\left( X\right) \not=\phi
\end{equation*}である場合には、\(X\)は上に有界であると言います。
順序集合\(A\)の空ではない部分集合\(X\)が上に有界である場合、その上界からなる集合\(U\left(X\right) \)は空ではない\(A\)の部分集合であるため、その最小元\begin{equation*}\min U\left( X\right)
\end{equation*}が存在するか検討できます。この最小元が存在する場合、それを\(X\)の上限(supremum)や最小上界(least upper bound)などと呼び、\begin{equation*}\sup X=\min U\left( X\right)
\end{equation*}で表記します。
上界\(\sup X\)は集合\(U\left( X\right) \)の最小元であるため、最小元の定義より、\(\sup X\)は以下の条件\begin{eqnarray*}&&\left( a\right) \ \sup X\in U\left( X\right) \\
&&\left( b\right) \ \forall y\in U\left( X\right) :\sup X\leq y
\end{eqnarray*}をともに満たす\(A\)の要素として定義されます。これらの条件をより具体的に表現すると、\begin{eqnarray*}
&&\left( a\right) \ \forall x\in X:x\leq \sup X \\
&&\left( b\right) \ \forall y\in A:\left[ \left( \forall x\in X:x\leq
y\right) \Rightarrow \sup X\leq y\right]
\end{eqnarray*}となります。\(\left( a\right) \)は\(\sup X\)が\(X\)の上界であることを意味し、\(\left( b\right) \)は\(\sup X\)が\(X\)の任意の上界以下であることを意味します。
上界\(\sup X\)は集合\(X\)の上界の1つであるため、これは\(X\)の要素であるとは限りません。その一方で、上界\(\sup X\)は集合\(X\)の上界からなる集合\(U\left( X\right) \)の最小元であるため、これは必ず\(U\left( X\right) \)の要素です。
\end{equation*}を定義します。この集合の上界からなる集合は、\begin{eqnarray*}
U\left( A\right) &=&\left\{ x\in \mathbb{R} \ |\ b\leq x\right\} \\
&=&[b,+\infty )
\end{eqnarray*}であり、この集合\(U\left(A\right) \)の最小元は、\begin{eqnarray*}\min U\left( A\right) &=&\min [b,+\infty ) \\
&=&b
\end{eqnarray*}であるため、もとの集合\(A\)の上限は、\begin{eqnarray*}\sup A &=&\min U\left( A\right) \\
&=&b
\end{eqnarray*}です。\(b\in A\)ゆえに、\begin{equation*}\sup A\in A
\end{equation*}でもあります。つまり、これは順序部分集合\(A\)の上限が\(A\)の要素になっている例です。
\end{equation*}を定義します。この集合の上界からなる集合は、\begin{eqnarray*}
U\left( A\right) &=&\left\{ x\in \mathbb{R} \ |\ b\leq x\right\} \\
&=&[b,+\infty )
\end{eqnarray*}であり、この集合\(U\left(A\right) \)の最小元は、\begin{eqnarray*}\min U\left( A\right) &=&\min [b,+\infty ) \\
&=&b
\end{eqnarray*}であるため、もとの集合\(A\)の上限は、\begin{eqnarray*}\sup A &=&\min U\left( A\right) \\
&=&b
\end{eqnarray*}です。\(b\not\in A\)ゆえに、\begin{equation*}\sup A\not\in A
\end{equation*}でもあります。つまり、これは順序部分集合\(A\)の上限が\(A\)の要素になっていない例です。
,\left\{ a,b\right\} ,\left\{ b,c\right\} ,\left\{ a,c\right\} ,\left\{
a,b,c\right\} \right\}
\end{equation*}上に定義された包含関係\(\subset \)は半順序です。\(2^{A}\)の部分集合\begin{equation*}X=\left\{ \left\{ a\right\} ,\left\{ b\right\} \right\}
\end{equation*}に注目します。\(X\)の上界からなる集合は、\begin{equation*}U\left( X\right) =\left\{ \left\{ a,b\right\} ,\left\{ a,b,c\right\}
\right\}
\end{equation*}であり、\(U\left( X\right) \)の要素の間には、\begin{eqnarray*}\left\{ a,b\right\} &\subset &\left\{ a,b\right\} \\
\left\{ a,b\right\} &\subset &\left\{ a,b,c\right\}
\end{eqnarray*}が成り立つため、\begin{equation*}
\min U\left( X\right) =\left\{ a,b\right\}
\end{equation*}を得ます。したがって、もとの集合\(X\)の上限は、\begin{eqnarray*}\sup X &=&\min U\left( X\right) \\
&=&\left\{ a,b\right\}
\end{eqnarray*}です。
\end{equation*}を満たすものとして\(|\)は定義されます。\(\mathbb{N} \)の部分集合\begin{equation*}X=\left\{ 2,4,6,8,10,30,60,120,240\right\}
\end{equation*}に注目します。\(X\)の上界からなる集合は、\begin{equation*}U\left( X\right) =\left\{ 240,480,720,\cdots \right\}
\end{equation*}であるとともに、その要素\(240\in U\left( X\right) \)について、\begin{equation*}\forall y\in U\left( X\right) :y\text{は}240\text{の倍数}
\end{equation*}すなわち、\begin{equation*}
\forall y\in U\left( X\right) :240|y
\end{equation*}が成り立つため、\begin{equation*}
\min U\left( X\right) =240
\end{equation*}を得ます。したがって、もとの集合\(X\)の上限は、\begin{eqnarray*}\sup X &=&\min U\left( X\right) \\
&=&240
\end{eqnarray*}です。
順序部分集合の下限
順序集合\(A\)の空ではない部分集合\(X\)が与えられたとき、もとの集合\(A\)に属するある要素\(a\)が集合\(X\)に属する任意の要素以下である場合には、つまり、\begin{equation*}\exists a\in A,\ \forall x\in X:a\leq x
\end{equation*}が成り立つならば、この要素\(a\)を集合\(X\)の下界と呼びます。集合\(X\)の下界は存在するとは限りませんし、存在する場合にも一意的に定まるとは限りません。そこで、集合\(X\)の上界をすべて集めることにより得られる集合を、\begin{equation*}L\left( X\right) =\left\{ a\in A\ |\ \forall x\in X:a\leq x\right\}
\end{equation*}で表記します。\(X\)が下界を持つ場合には、すなわち、\begin{equation*}L\left( X\right) \not=\phi
\end{equation*}である場合には、\(X\)は下に有界であると言います。
順序集合\(A\)の空ではない部分集合\(X\)が下に有界である場合、その下界からなる集合\(L\left(X\right) \)は空ではない\(A\)の部分集合であるため、その最大元\begin{equation*}\max L\left( X\right)
\end{equation*}が存在するか検討できます。この最大元が存在する場合、それを\(X\)の下限(infimum)や最大上界(greatest lower bound)などと呼び、\begin{equation*}\inf X=\max L\left( X\right)
\end{equation*}で表記します。
下界\(\inf X\)は集合\(L\left( X\right) \)の最大元であるため、最大元の定義より、\(\inf X\)は以下の条件\begin{eqnarray*}&&\left( a\right) \ \inf X\in L\left( X\right) \\
&&\left( b\right) \ \forall y\in L\left( X\right) :y\leq \inf X
\end{eqnarray*}をともに満たす\(A\)の要素として定義されます。これらの条件をより具体的に表現すると、\begin{eqnarray*}
&&\left( a\right) \ \forall x\in X:\inf X\leq x \\
&&\left( b\right) \ \forall y\in A:\left[ \left( \forall x\in X:y\leq
x\right) \Rightarrow y\leq \inf X\right]
\end{eqnarray*}となります。\(\left( a\right) \)は\(\inf X\)が\(X\)の下界であることを意味し、\(\left( b\right) \)は\(\inf X\)が\(X\)の任意の下界以上であることを意味します。
下限\(\inf X\)は集合\(X\)の下界の1つであるため、これは\(X\)の要素であるとは限りません。その一方で、下限\(\inf X\)は集合\(X\)の下界からなる集合\(L\left( X\right) \)の最大元であるため、これは必ず\(L\left( X\right) \)の要素です。
\end{equation*}を定義します。この集合の下界からなる集合は、\begin{eqnarray*}
L\left( A\right) &=&\left\{ x\in \mathbb{R} \ |\ x\leq a\right\} \\
&=&(-\infty ,a] \end{eqnarray*}であり、この集合\(L\left(A\right) \)の最大元は、\begin{eqnarray*}\max L\left( A\right) &=&\max (-\infty ,a] \\
&=&a
\end{eqnarray*}であるため、もとの集合\(A\)の下限は、\begin{eqnarray*}\inf A &=&\max L\left( A\right) \\
&=&a
\end{eqnarray*}です。\(a\in A\)ゆえに、\begin{equation*}\inf A\in A
\end{equation*}でもあります。つまり、これは順序部分集合\(A\)の下限が\(A\)の要素になっている例です。
\end{equation*}を定義します。この集合の下界からなる集合は、\begin{eqnarray*}
L\left( A\right) &=&\left\{ x\in \mathbb{R} \ |\ x\leq a\right\} \\
&=&(-\infty ,a] \end{eqnarray*}であり、この集合\(L\left(A\right) \)の最大元は、\begin{eqnarray*}\max L\left( A\right) &=&\max (-\infty ,a] \\
&=&a
\end{eqnarray*}であるため、もとの集合\(A\)の下限は、\begin{eqnarray*}\inf A &=&\max L\left( A\right) \\
&=&a
\end{eqnarray*}です。\(a\not\in A\)ゆえに、\begin{equation*}\inf A\not\in A
\end{equation*}でもあります。つまり、これは順序部分集合\(A\)の下限が\(A\)の要素になっていない例です。
,\left\{ a,b\right\} ,\left\{ b,c\right\} ,\left\{ a,c\right\} ,\left\{
a,b,c\right\} \right\}
\end{equation*}上に定義された包含関係\(\subset \)は半順序です。\(2^{A}\)の部分集合\begin{equation*}X=\left\{ \left\{ a\right\} ,\left\{ b\right\} \right\}
\end{equation*}に注目します。\(X\)の下界からなる集合は、\begin{equation*}L\left( X\right) =\left\{ \phi \right\}
\end{equation*}であり、\(U\left( X\right) \)の要素の間には、\begin{equation*}\phi \subset \phi
\end{equation*}が成り立つため、\begin{equation*}
\max L\left( X\right) =\phi
\end{equation*}を得ます。したがって、もとの集合\(X\)の下限は、\begin{eqnarray*}\inf X &=&\max L\left( X\right) \\
&=&\phi
\end{eqnarray*}です。
\end{equation*}を満たすものとして\(|\)は定義されます。\(\mathbb{N} \)の部分集合\begin{equation*}X=\left\{ 2,4,6,8,10,30,60,120,240\right\}
\end{equation*}に注目します。\(X\)の下界からなる集合は、\begin{equation*}L\left( X\right) =\left\{ 1,2\right\}
\end{equation*}であるとともに、その要素\(2\in L\left( X\right) \)について、\begin{equation*}\forall y\in L\left( X\right) :2\text{は}y\text{の倍数}
\end{equation*}すなわち、\begin{equation*}
\forall y\in L\left( X\right) :y|2
\end{equation*}が成り立つため、\begin{equation*}
\max L\left( X\right) =2
\end{equation*}を得ます。したがって、もとの集合\(X\)の下限は、\begin{eqnarray*}\inf X &=&\max L\left( X\right) \\
&=&2
\end{eqnarray*}です。
上限と下限は異なるとは限らない
以下は上限と下限が異なる順序部分集合の例です。
\end{equation*}を定義します。先に示したように、\begin{eqnarray*}
\sup A &=&b \\
\inf A &=&a
\end{eqnarray*}ですが、\(a<b\)ゆえに、\begin{equation*}\inf A<\sup A
\end{equation*}が成り立ちます。
以下は上限と下限が一致する順序部分集合の例です。
\end{equation*}を定義します。\(a\)以上の任意の実数が\(\left\{ a\right\} \)の上界であり、\(a\)以下の任意の実数が\(\left\{ a\right\} \)の下界であるため、\begin{eqnarray*}U\left( A\right) &=&\left\{ x\in \mathbb{R} \ |\ a\leq x\right\} \\
L\left( A\right) &=&\left\{ x\in \mathbb{R} \ |\ x\leq a\right\}
\end{eqnarray*}となります。したがって、\begin{eqnarray*}
\sup A &=&\min U\left( A\right) =a \\
\inf A &=&\max L\left( A\right) =a
\end{eqnarray*}となります。以上より、\begin{equation*}
\sup A=\inf A
\end{equation*}であることが明らかになりました。これは順序部分集合\(A\)の上限や下限が\(A\)の要素になっている例です。しかも両者は一致します。
上限や下限は存在するとは限らない
順序部分集合は上限や下限を持つとは限りません。
順序集合\(A\)の非空な部分集合\(X\)が上に有界ではない場合には\(U\left( X\right)=\phi \)となりますが、空集合の最小元は存在しないため、この場合、\(U\left( X\right) \)の最小元に相当する\(\sup X\)は存在しません。
順序集合\(A\)の非空な部分集合\(X\)が下に有界ではない場合には\(L\left( X\right)=\phi \)となりますが、空集合の最大元は存在しないため、この場合、\(L\left( X\right) \)の最大元に相当する\(\inf X\)は存在しません。
\end{equation*}という\(\mathbb{R} \)の部分集合を定義します。\(a\)は\(A\)の要素であるため\(A\)は非空です。このとき、\begin{equation*}U\left( A\right) =\phi
\end{equation*}であるため\(\min U\left( A\right) \)すなわち\(\sup A\)は存在しません。また、実数\(b\)を任意に選んだ上で、\begin{equation*}B=\left\{ x\in \mathbb{R} \ |\ x\leq b\right\}
\end{equation*}という\(\mathbb{R} \)の部分集合を定義します。\(b\)は\(A\)の要素であるため\(A\)は非空です。このとき、\begin{equation*}L\left( B\right) =\phi
\end{equation*}であるため\(\max L\left( B\right) \)すなわち\(\inf B\)は存在しません。
非空な順序部分集合が上に有界ではない場合には上限を持たず、下に有界ではない場合には下限を持たないことが明らかになりました。では、非空な順序部分集合が上に有界であるにも関わらず上限を持たない事態や、下に有界であるにも関わらず下限を持たない事態は起こり得るのでしょうか。詳細は場を改めて解説します。
上限や下限の一意性
順序部分集合の上限や下限は存在するとは限らないことが明らかになりました。ただ、上限や下限が存在する場合、それらはそれぞれ一意的に定まることが保証されます。
&&\left( b\right) \ \inf A\text{が存在するならば、それは一意的である}
\end{eqnarray*}が成り立つ。
上限と最大元・下限と最小元の関係
順序部分集合の最大元は存在するとは限りませんが、最大元が存在する場合、それは上限でもあります。
順序部分集合の最小元は存在するとは限りませんが、最小元が存在する場合、それは下限でもあります。
\\
&&\left( b\right) \ \min X\text{が存在するならば、}\min X=\inf X\text{が成り立つ}
\end{eqnarray*}が成り立つ。
順序部分集合の最大元が存在する場合には、それは上限と一致することが明らかになりました。また、順序部分集合の最小限が存在する場合には、それは下限と一致することが明らかになりました。では、順序部分集合の最大元が存在しない場合、上限もまた存在しないとまで言えるのでしょうか。また、順序部分集合の最小元が存在しない場合、下限もまた存在しないとまで言えるのでしょうか。これらの主張は成り立ちません。つまり、順序部分集合の最大元が存在しない一方で上限が存在する状況や、順序部分集合の最小限が存在しない一方で下限が存在する状況は起こり得ます。以下の例より明らかです。
\end{equation*}を定義します。このとき、\begin{eqnarray*}
U\left( A\right) &=&\left\{ x\in \mathbb{R} \ |\ b\leq x\right\} \\
L\left( A\right) &=&\left\{ x\in \mathbb{R} \ |\ x\leq a\right\}
\end{eqnarray*}であるため、\begin{eqnarray*}
\sup A &=&\min U\left( A\right) =b \\
\inf A &=&\max L\left( A\right) =a
\end{eqnarray*}である一方で、\(\max A\)や\(\min A\)は存在しません。
順序部分集合の上限が存在する場合、最大元は存在するとは限らないことが明らかになりました。しかし、順序部分集合の上限が存在するとともに、それがその集合の要素である場合には、上限は最大元でもあることが保証されます。同様に、順序部分集合の下限が存在するとともに、それがその集合の要素である場合には、下限は最小元でもあることが保証されます。
&&\left( b\right) \ \inf X\text{が存在するとともに}\inf X\in X\text{ならば、}\inf X=\min X\text{が成り立つ}
\end{eqnarray*}が成り立つ。
有限集合の上限と下限
全順序集合\(A\)の部分集合\(X\)が有限集合である場合、すなわち、\(X\)に属する要素の個数が有限である場合、\(X\)の上限と下限はともに存在することが保証されます。
\inf X &=&\min X
\end{eqnarray*}が成り立つ。
以上の命題は全順序集合の部分集合に関する主張であることに注意してください。半順序集合については、その部分集合が有限集合であっても、その上限や下限は存在するとは限りません。以下の例より明らかです。
A=\left\{ \left\{ a\right\} ,\left\{ b\right\} ,\left\{ c\right\} \right\}
\end{equation*}上に定義された包含関係\(\subset \)は半順序である一方で全順序ではありません。\(A\)の部分集合\begin{equation*}X=\left\{ \left\{ a\right\} ,\left\{ b\right\} \right\}
\end{equation*}は有限集合ですが、この集合\(X\)は上界や下界を持たないため、\(X\)の上限や下限もまた存在しません。
空集合の上限と下限
これまでは非空な順序部分集合を対象に、その上限や下限を考えてきました。空集合は任意の集合の部分集合であるため、空集合は任意の順序集合の部分順序集合です。では、空集合の上限や下限は存在するのでしょうか。以下の命題が答えを与えます。
\inf \phi &=&\max A
\end{eqnarray*}が成り立つ。
以上の命題より、順序集合の最小元が存在する場合には、それは空集合の上限と一致し、最大元が存在する場合には、それは空集合の下限と一致することが明らかになりました。
,\left\{ a,b\right\} ,\left\{ b,c\right\} ,\left\{ a,c\right\} ,\left\{
a,b,c\right\} \right\}
\end{equation*}上に定義された包含関係\(\subset \)は半順序です。半順序集合\(2^{A}\)について、\begin{eqnarray*}\max 2^{A} &=&\left\{ a,b,c\right\} \\
\min 2^{A} &=&\phi
\end{eqnarray*}が成り立つため、先の命題より、\begin{eqnarray*}
\sup \phi &=&\left\{ a,b,c\right\} \\
\inf \phi &=&\phi
\end{eqnarray*}となります。
順序集合が最小元や最大元を持たない場合、先の命題より、空集合の上限や下限は存在しません。
&&\min \mathbb{R} \end{eqnarray*}はともに存在しないため、先の命題より、\begin{eqnarray*}
&&\sup \phi \\
&&\inf \phi
\end{eqnarray*}もまた存在しません。
演習問題
A=\left\{ 2,3,4,5,8,10,12,24,30\right\}
\end{equation*}上に定義された整除関係\(|\)は半順序です。ただし、任意の\(x,y\in A\)に対して、\begin{equation*}x|y\Leftrightarrow y\text{は}x\text{の倍数}
\end{equation*}を満たすものとして\(|\)は定義されます。以下の集合\begin{equation*}X=\left\{ 4,8\right\}
\end{equation*}の上限と下限は存在するでしょうか。議論してください。
A=\left\{ 2,4,6,8,10,30,60,120,240\right\}
\end{equation*}上に定義された整除関係\(|\)は半順序です。ただし、任意の\(x,y\in A\)に対して、\begin{equation*}x|y\Leftrightarrow y\text{は}x\text{の倍数}
\end{equation*}を満たすものとして\(|\)は定義されます。以下の集合\begin{equation*}X=\left\{ 8,30,60\right\}
\end{equation*}の上限と下限は存在するでしょうか。議論してください。
A=\left\{ \phi ,\left\{ 2\right\} ,\left\{ 3\right\} ,\left\{ 4\right\}
,\left\{ 1,3\right\} ,\left\{ 2,3\right\} ,\left\{ 2,4\right\} ,\left\{
1,2,3\right\} ,\left\{ 2,3,4\right\} ,\left\{ 1,2,3,4\right\} \right\}
\end{equation*}上に定義された包含関係\(\subset \)は半順序です。以下の集合\begin{equation*}X=\left\{ \left\{ 1,3\right\} ,\left\{ 2,4\right\} \right\}
\end{equation*}の上限と下限は存在するでしょうか。議論してください。
A=\left\{ \phi ,\left\{ 2\right\} ,\left\{ 3\right\} ,\left\{ 4\right\}
,\left\{ 1,3\right\} ,\left\{ 2,3\right\} ,\left\{ 2,4\right\} ,\left\{
1,2,3\right\} ,\left\{ 2,3,4\right\} ,\left\{ 1,2,3,4\right\} \right\}
\end{equation*}上に定義された包含関係\(\subset \)は半順序です。以下の集合\begin{equation*}X=\left\{ \left\{ 1,2,3\right\} ,\left\{ 2,3,4\right\} \right\}
\end{equation*}の上限と下限は存在するでしょうか。議論してください。
A=\left\{ \left\{ 1\right\} ,\left\{ 3\right\} ,\left\{ 4\right\} ,\left\{
1,2\right\} ,\left\{ 2,3\right\} ,\left\{ 3,4\right\} ,\left\{ 1,2,3\right\}
,\left\{ 2,3,4\right\} ,\left\{ 1,2,3,4\right\} \right\}
\end{equation*}上に定義された包含関係\(\subset \)は半順序です。以下の集合\begin{equation*}X=\left\{ \left\{ 1,2\right\} ,\left\{ 3,4\right\} \right\}
\end{equation*}の上限と下限は存在するでしょうか。議論してください。
A=\left\{ \left\{ 1\right\} ,\left\{ 3\right\} ,\left\{ 4\right\} ,\left\{
1,2\right\} ,\left\{ 2,3\right\} ,\left\{ 3,4\right\} ,\left\{ 1,2,3\right\}
,\left\{ 2,3,4\right\} ,\left\{ 1,2,3,4\right\} \right\}
\end{equation*}上に定義された包含関係\(\subset \)は半順序です。以下の集合\begin{equation*}X=\left\{ \left\{ 3\right\} ,\left\{ 2,3\right\} \right\}
\end{equation*}の上限と下限は存在するでしょうか。議論してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】