順序部分集合の最大元・最小元

順序部分集合の最大元

集合\(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\)が与えられたとき、この集合\(X\)に属するある要素\(a\)が、同じ集合\(X\)に属する任意の要素以上である場合には、つまり、\begin{equation*}\exists a\in X,\ \forall x\in X:x\leq a
\end{equation*}が成り立つならば、この要素\(a\)を集合\(X\)の最大元（maximum element）や最後の元（last element）などと呼び、そのことを、\begin{equation*}a=\max X
\end{equation*}で表記します。つまり、集合\(X\)の最大元\(\max X\)は以下の条件\begin{equation*}\forall x\in X:x\leq \max X
\end{equation*}を満たす\(X\)の要素として定義されるということです。集合\(X\)の最大元は\(X\)の要素である必要があります。つまり、\begin{equation*}\max X\in X
\end{equation*}です。\(X\)に属さない要素は\(X\)の最大元にはなり得ません。

逆に、集合\(X\)に属する要素\(a\)がその集合\(X\)の最大元でないことは、\begin{equation*}\exists x\in X:\lnot \left( x\leq a\right)
\end{equation*}が成り立つことを意味します。特に、\(\leq \)が完備律を満たす場合、すなわち\(\leq \)が全順序である場合には以下の関係\begin{equation*}\lnot \left( x\leq a\right) \Leftrightarrow a<x
\end{equation*}が成り立つため、\(a\)が\(X\)の最大元でないことは、\begin{equation*}\exists x\in X:a<x
\end{equation*}が成り立つことと必要十分です。つまり、\(\leq \)が全順序である場合、集合\(X\)の要素である\(a\)に対して、それよりも大きい要素が\(X\)の中に存在する場合、\(a\)は\(X\)の最大元ではありません。

順序部分集合の最小元

順序集合\(A\)の空でない部分集合\(X\)が与えられたとき、この集合\(X\)に属するある要素\(a\)が、同じ集合\(X\)に属する任意の要素以下である場合には、つまり、\begin{equation*}\exists a\in X,\ \forall x\in X:a\leq x
\end{equation*}が成り立つならば、この要素\(a\)を集合\(X\)の最小元（minimum element）や最初の元（first element）などと呼び、そのことを、\begin{equation*}a=\min X
\end{equation*}で表記します。つまり、集合\(X\)の最大元\(\min X\)は以下の条件\begin{equation*}\forall x\in X:\min X\leq x
\end{equation*}を満たす\(X\)の要素として定義されるということです。集合\(X\)の最小元は\(X\)の要素である必要があります。つまり、\begin{equation*}\min X\in X
\end{equation*}です。\(X\)に属さない要素は\(X\)の最小元にはなり得ません。

逆に、集合\(X\)に属する要素\(a\)がその集合\(X\)の最小元でないことは、\begin{equation*}\exists x\in X:\lnot \left( a\leq x\right)
\end{equation*}が成り立つことを意味します。特に、\(\leq \)が完備律を満たす場合、すなわち\(\leq \)が全順序である場合には以下の関係\begin{equation*}\lnot \left( a\leq x\right) \Leftrightarrow x<a
\end{equation*}が成り立つため、\(a\)が\(X\)の最小元でないことは、\begin{equation*}\exists x\in X:x<a
\end{equation*}が成り立つことと必要十分です。つまり、\(\leq \)が全順序である場合、集合\(X\)の要素である\(a\)に対して、それよりも小さい要素が\(X\)の中に存在する場合、\(a\)は\(X\)の最小元ではありません。

最大元と最小元は異なるとは限らない

以下は最大元と最小元が異なる部分順序集合の例です。

部分順序集合の最大元と最小値が一致する事態も起こり得ます。以下の例より明らかです。

最大元や最小元は存在するとは限らない

順序部分集合の最大元や最小元は存在するとは限りません。以下の例より明らかです。

順序部分集合の最大元と最小元のどちらか一方が存在するような状況は起こり得ます。以下は最小値を持つ一方で最大値を持たない順序部分集合の例です。

有限集合は最大元と最小元を持つ

全順序集合の順序部分集合が有限集合である場合、すなわち、全順序部分集合に属する要素の個数が有限である場合、その全順序部分集合の最大元と最小元がともに存在することが保証されます。これは有限集合に含まれる要素の個数\(n\)に関する数学的帰納法より証明可能です

以上の命題は全順序集合の部分集合に関する主張であることに注意してください。半順序集合については、その部分集合が有限集合であっても、その最大元や最小元は存在するとは限りません。以下の例より明らかです。

最大元や最小元の一意性

先に示したように、順序部分集合は最大元や最小元を持つとは限りません。ただ、最大元や最小元が存在する場合、それらはそれぞれ一意的であることが保証されます。

空集合の最大元と最小元

これまでは順序集合\(A\)の非空な部分集合を対象に、その最大元や最小元を考えてきました。空集合は任意の集合の部分集合であるため\(\phi \subset A\)です。では、空集合の最大元や最小元は存在するのでしょうか。

空集合\(\phi \)の最大元に相当する要素\(\max \phi \in A\)が存在するものと仮定します。最大元の定義より\(\max \phi \in \phi \)でなければなりませんが、空集合は要素を持たないためこれは矛盾です。したがって背理法より\(\phi \)は最大元を持たないことが明らかになりました。

空集合\(\phi \)が最小元を持たないことの証明も同様です。

演習問題