WIIS

教材一覧
教材一覧
教材検索
RELATION

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

目次

Share on twitter
Twitterで共有
Share on email
メールで共有

順序部分集合の最大元

半順序集合\(\left( A,\leq \right) \)の非空な部分集合\(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*}で表記します。つまり、\(\max X\)は集合\(X\)の最大元を表す記号です。定義より、\(X\)の最大元は\(X\)の要素でなければなりません。

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

例(実数の大小関係と最大元)
すべての実数からなる集合\(\mathbb{R} \)上に大小関係\(\leq \)を定義します。\(\left( \mathbb{R} ,\leq \right) \)は全順序集合です。\(\mathbb{R} \)の部分集合\begin{equation*}\left[ 0,1\right] =\left\{ x\in \mathbb{R} \ |\ 0\leq x\leq 1\right\}
\end{equation*}に注目します。要素\(1\in \left[ 0,1\right] \)は、\begin{equation*}\forall x\in \left[ 0,1\right] :x\leq 1
\end{equation*}を満たすため、\begin{equation*}
\max \left[ 0,1\right] =1
\end{equation*}であることが明らかになりました。

例(包含関係と最大元)
集合\(A=\left\{ a,b,c\right\} \)のベキ集合\begin{equation*}2^{A}=\left\{ \phi ,\left\{ a\right\} ,\left\{ b\right\} ,\left\{ c\right\}
,\left\{ a,b\right\} ,\left\{ b,c\right\} ,\left\{ a,c\right\} ,\left\{
a,b,c\right\} \right\}
\end{equation*}上に包含関係\(\subset \)を定義します。\(\left( 2^{A},\subset \right) \)は半順序集合です。\(2^{A}\)の部分集合\begin{equation*}X=\left\{ \left\{ a\right\} ,\left\{ a,b\right\} ,\left\{ a,b,c\right\}
\right\}
\end{equation*}に注目します。要素\(\left\{ a,b,c\right\} \in X\)は、\begin{eqnarray*}\left\{ a\right\} &\subset &\left\{ a,b,c\right\} \\
\left\{ a,b\right\} &\subset &\left\{ a,b,c\right\} \\
\left\{ a,b,c\right\} &\subset &\left\{ a,b,c\right\}
\end{eqnarray*}を満たすため、\begin{equation*}
\max X=\left\{ a,b,c\right\}
\end{equation*}であることが明らかになりました。

 

順序部分集合の最小元

半順序集合\(\left( A,\leq \right) \)の非空な部分集合\(X\)について、そのある要素\(a\)が\(X\)の任意の要素以下である場合には、つまり、\begin{equation*}\exists a\in X,\ \forall x\in X:a\leq x
\end{equation*}が成り立つならば、\(a\)を\(X\)の最小元(minimum element)や最初の元(firstelement)などと呼び、これを、\begin{equation*}
a=\min X
\end{equation*}で表記します。つまり、\(\min X\)は集合\(X\)の最小元を表す記号です。定義より、\(X\)の最小元は\(X\)の要素でなければなりません。

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

例(実数の大小関係と最小元)
すべての実数からなる集合\(\mathbb{R} \)上に大小関係\(\leq \)を定義します。\(\left( \mathbb{R} ,\leq \right) \)は全順序集合です。\(\mathbb{R} \)の部分集合\begin{equation*}\left[ 0,1\right] =\left\{ x\in \mathbb{R} \ |\ 0\leq x\leq 1\right\}
\end{equation*}に注目します。要素\(0\in \left[ 0,1\right] \)は、\begin{equation*}\forall x\in \left[ 0,1\right] :0\leq x
\end{equation*}を満たすため、\begin{equation*}
\min \left[ 0,1\right] =0
\end{equation*}であることが明らかになりました。

例(包含関係と最小元)
集合\(A=\left\{ a,b,c\right\} \)のベキ集合\begin{equation*}2^{A}=\left\{ \phi ,\left\{ a\right\} ,\left\{ b\right\} ,\left\{ c\right\}
,\left\{ a,b\right\} ,\left\{ b,c\right\} ,\left\{ a,c\right\} ,\left\{
a,b,c\right\} \right\}
\end{equation*}上に包含関係\(\subset \)を定義します。\(\left( 2^{A},\subset \right) \)は半順序集合です。\(2^{A}\)の部分集合\begin{equation*}X=\left\{ \left\{ a\right\} ,\left\{ a,b\right\} ,\left\{ a,b,c\right\}
\right\}
\end{equation*}に注目します。要素\(\left\{ a\right\} \in X\)は、\begin{eqnarray*}\left\{ a\right\} &\subset &\left\{ a\right\} \\
\left\{ a\right\} &\subset &\left\{ a,b\right\} \\
\left\{ a\right\} &\subset &\left\{ a,b,c\right\}
\end{eqnarray*}を満たすため、\begin{equation*}
\min X=\left\{ a\right\}
\end{equation*}であることが明らかになりました。

 

最大元や最小元の存在

一般に、順序集合の非空な部分集合について、その最大元や最小元は存在するとは限りません。以下の例より明らかです。

例(実数の大小関係と最大元・最小元)
すべての実数からなる集合\(\mathbb{R} \)上に大小関係\(\leq \)を定義します。\(\left( \mathbb{R} ,\leq \right) \)は全順序集合です。\(\mathbb{R} \)は\(\mathbb{R} \)自身の部分集合です。仮に\(\max \mathbb{R} \)が存在するものと仮定した場合、\begin{equation*}\exists \max \mathbb{R} +1\in \mathbb{R} :\max \mathbb{R} <\max \mathbb{R} +1
\end{equation*}が成り立ちますが、これは\(\max \mathbb{R} \)が\(\mathbb{R} \)の最大元であることと矛盾です。したがって\(\max \mathbb{R} \)は存在しません。同様に、\(\min \mathbb{R} \)が存在するものと仮定した場合、\begin{equation*}\exists \max \mathbb{R} -1\in \mathbb{R} :\min \mathbb{R} -1<\min \mathbb{R} \end{equation*}が成り立ちますが、これは\(\min \mathbb{R} \)が\(\mathbb{R} \)の最小元であることと矛盾です。したがって\(\min \mathbb{R} \)は存在しません。
例(包含関係と最大元・最小元)
集合\(A=\left\{ a,b,c\right\} \)のベキ集合\begin{equation*}2^{A}=\left\{ \phi ,\left\{ a\right\} ,\left\{ b\right\} ,\left\{ c\right\}
,\left\{ a,b\right\} ,\left\{ b,c\right\} ,\left\{ a,c\right\} ,\left\{
a,b,c\right\} \right\}
\end{equation*}上に包含関係\(\subset \)を定義します。\(\left( 2^{A},\subset \right) \)は半順序集合です。\(2^{A}\)の部分集合\begin{equation*}X=\left\{ \left\{ a\right\} ,\left\{ b\right\} ,\left\{ c\right\} \right\}
\end{equation*}に注目します。\(X\)のすべての要素を部分集合として持つ集合は\(X\)の中に存在しないため\(\max X\)は存在しません。また、\(X\)のすべての要素の部分集合であるような集合は\(X\)の中に存在しないため\(\min X\)は存在しません。

ただし、問題としている順序集合\(\left( A,\leq \right) \)が全順序集合であり、なおかつその非空な部分集合\(X\)が有限集合である場合には、\(X\)の最大元や最小元が存在することが保証されます。

命題(全順序集合の有限部分集合の最大元と最小元)
全順序集合\(\left( A,\leq \right) \)の非空な部分集合\(X\)が有限集合である場合には、最大元\(\max A\)と最小元\(\min A\)がそれぞれ存在する。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

 

最大元や最小元の一意性

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

命題(最大元や最小元の一意性)
半順序集合\(\left( A,\leq \right) \)の非空な部分集合\(X\)に対して、最大元\(\max X\)が存在する場合には一意的である。また、最小元\(\min X\)が存在する場合には一意的である。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

 

演習問題

問題(自然数の整除関係と最大元)
すべての自然数からなる集合\(\mathbb{N} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{N} \times \mathbb{N} \)に対して、\begin{equation*}x|y\Leftrightarrow y\text{は}x\text{の倍数}
\end{equation*}を満たす整除関係\(|\)を定義します。\(\left( \mathbb{N} ,|\right) \)は半順序集合です。\(\mathbb{N} \)の部分集合\begin{equation*}X=\left\{ 2,4,6,8,10,30,60,120,240\right\}
\end{equation*}に注目します。\(X\)の最大元や最小元は存在しますか。議論してください。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(自然数の整除関係と最大元)
すべての自然数からなる集合\(\mathbb{N} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{N} \times \mathbb{N} \)に対して、\begin{equation*}x|y\Leftrightarrow y\text{は}x\text{の倍数}
\end{equation*}を満たす整除関係\(|\)を定義します。\(\left( \mathbb{N} ,|\right) \)は半順序集合です。\(\mathbb{N} \)の部分集合\begin{equation*}X=\left\{ 2,3,4,5,8,10,12,24,30\right\}
\end{equation*}に注目します。\(X\)の最大元や最小元は存在しますか。議論してください。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(自然数の整除関係と最大元)
すべての自然数からなる集合\(\mathbb{N} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{N} \times \mathbb{N} \)に対して、\begin{equation*}x|y\Leftrightarrow y\text{は}x\text{の倍数}
\end{equation*}を満たす整除関係\(|\)を定義します。\(\left( \mathbb{N} ,|\right) \)は半順序集合です。\(\mathbb{N} \)の部分集合\begin{equation*}X=\left\{ 2,4,6,8,10,30,60,120,240\right\}
\end{equation*}に注目します。\(X\)の最大元や最小元は存在しますか。議論してください。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(実数の大小関係と最大元・最小元)
すべての実数からなる集合\(\mathbb{R} \)上に大小関係\(\leq \)を定義します。\(\left( \mathbb{R} ,\leq \right) \)は全順序集合です。すべての自然数からなる集合\begin{equation*}\mathbb{N} =\left\{ 1,2,3,\cdots \right\} \end{equation*}は\(\mathbb{R} \)の非空な部分集合ですが、その最大元や最小元は存在しますか。議論してください。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(実数の大小関係と最大元・最小元)
すべての実数からなる集合\(\mathbb{R} \)上に大小関係\(\leq \)を定義します。\(\left( \mathbb{R} ,\leq \right) \)は全順序集合です。\(a<b\)を満たす実数\(a,b\in \mathbb{R} \)を任意に選んだ上で、\(\mathbb{R} \)の非空な部分集合\begin{equation*}A=\left\{ x\in \mathbb{R} \ |\ a<x<b\right\}
\end{equation*}を定義します。\(A\)の最大元や最小元は存在しますか。議論してください。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(最大元と最小元)
最大元を持たない一方で最小元を持つような順序部分集合の例を具体的に挙げてください。

解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

最大値・最小値
1変数関数の大域的最適解

関数の値を最大化するような点が定義域上に存在する場合、そのような点を最大点や大域的最大点と呼びます。また、関数が最大点に対して定める値を最大値や大域的最大値と呼びます。

最大値・最小値
1変数関数の局所最適解

関数の値を最大化するような点が定義域上に存在しない場合でも、変数がとり得る値を限定することにより、その範囲内において関数の値を最大化するような点が存在する状況は起こり得ます。そのような点を極大点や局所的最大点と呼びます。また、関数が極大点に対して定める値を極大値や大域的最大値と呼びます。

1階の必要条件
1変数関数の最適化のための1階の必要条件

関数が定義域において局所最適解(極大点・極小点)を持つための1階の必要条件を明らかにするとともに、関数の大域的最適解(最小点・最大点)を具体的に求める方法について解説します。

2階の必要条件
1変数凸関数・凹関数の無制約最適化

1変数の凸関数を目的関数とする制約条件のない最小化問題や、1変数の凹関数を目的関数とする制約条件のない最大化問題を解く方法を解説します。

最大・最小
実数集合の最大値・最小値

実数集合 R の空でない部分集合 A について、そのある要素 a が A の任意の実数以上ならば、a を A の最大値と呼びます。また、a が A の任意の実数以下ならば、a を A の最小値と呼びます。

最大値・最小値
多変数関数の大域的最適解

多変数関数の値を最大化するような点が定義域上に存在する場合、そのような点を最大点や大域的最大点と呼びます。また、多変数関数が最大点に対して定める値を最大値や大域的最大値と呼びます。

最大値・最小値
多変数関数の局所最適解

多変数関数の値を最大化するような点が定義域上に存在しない場合でも、変数がとり得る値を限定することにより、その範囲内において関数の値を最大化するような点が存在する状況は起こり得ます。そのような点を極大点や局所的最大点と呼びます。また、関数が極大点に対して定める値を極大値や大域的最大値と呼びます。

1階の必要条件
多変数関数の最適化のための1階の必要条件

多変数関数が定義域において局所最適解(極大点・極小点)を持つための1階の必要条件を明らかにするとともに、関数の大域的最適解(最小点・最大点)を具体的に求める方法について解説します。

凸関数・凹関数
多変数凸関数・凹関数の無制約最適化

多変数の凸関数を目的関数とする制約条件のない最小化問題や、多変数の凹関数を目的関数とする制約条件のない最大化問題を解く方法を解説します。

全順序
順序部分集合

順序集合A上に定義されている順序のもとで、Aの非空な部分集合Xが順序集合になっている場合、XをAの順序部分集合と呼びます。

極大値・極小値
順序部分集合の極大元・極小元

非空な順序部分集合のある要素よりも大きい要素がその集合の中に存在しない場合、その要素を極大元と呼びます。また、非空な順序部分集合のある要素よりも小さい要素がその集合の中に存在しない場合、その要素を極小元と呼びます。

DISCUSSION

質問とコメント

プレミアム会員専用コンテンツです
ログイン】【会員登録

関係