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:\lnot \left( a<x\right)
\end{equation*}が成り立つならば、\(a\)を\(X\)の極大元(maximal element)と呼びます。定義より、\(X\)の極大元は\(X\)の要素でなければなりません。

逆に、\(X\)の要素である\(a\)が\(X\)の極大元でないことは、\begin{equation*}\exists x\in X:a<x
\end{equation*}が成り立つことを意味します。つまり、\(X\)の要素である\(a\)に対して、それよりも大きい\(X\)の要素が存在する場合、\(a\)は\(X\)の極大元ではありません。

極大元を以下のように定義することもできます。

命題(極大元の特徴づけ)
半順序集合\(\left( A,\leq \right) \)の非空な部分集合\(X\)について、\begin{equation*}\exists a\in X,\ \forall x\in X:\left( a\leq x\Rightarrow x=a\right)
\end{equation*}が成り立つことは、\(a\)が\(X\)の極大元であるための必要十分条件である。
証明

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

つまり、\(X\)の要素である\(a\)が\(X\)の極大元であることは、\(a\)以上の\(X\)の任意の要素が\(a\)と一致することと必要十分です。

例(実数の大小関係と極大元)
すべての実数からなる集合\(\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\)は\(\left[0,1\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]\)の極大元であることが示されました。
例(包含関係と極大元)
集合\(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\} \)は\(X\)の極小元です。実際、\(\left\{ a,b,c\right\} \in X\)であるとともに、\begin{equation*}\left\{ a,b,c\right\} \subset Y
\end{equation*}を満たす集合\(Y\in X\)を任意に選んだとき、\(X\)の定義より、\begin{equation*}Y=\left\{ a,b,c\right\}
\end{equation*}が成り立つため、先の命題より、\(\left\{ a,b,c\right\} \)が\(X\)の極大元であることが示されました。

 

順序部分集合の極小元

半順序集合\(\left( A,\leq \right) \)の非空な部分集合\(X\)について、そのある要素\(a\)よりも小さい要素が\(X\)の中に存在しない場合には、つまり、\begin{equation*}\exists a\in X,\ \forall x\in X:\lnot \left( x<a\right)
\end{equation*}が成り立つならば、\(a\)を\(X\)の極小元(minimal element)と呼びます。定義より、\(X\)の極小元は\(X\)の要素でなければなりません。

逆に、\(X\)の要素である\(a\)が\(X\)の極小元でないことは、\begin{equation*}\exists x\in X:x<a
\end{equation*}が成り立つことを意味します。つまり、\(X\)の要素である\(a\)に対して、それよりも小さい\(X\)の要素が存在する場合、\(a\)は\(X\)の極小元ではありません。

極小元を以下のように定義することもできます。

命題(極小元の特徴づけ)
半順序集合\(\left( A,\leq \right) \)の非空な部分集合\(X\)について、\begin{equation*}\exists a\in X,\ \forall x\in X:\left( x\leq a\Rightarrow x=a\right)
\end{equation*}が成り立つことは、\(a\)が\(X\)の極小元であるための必要十分条件である。
証明

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

つまり、\(X\)の要素である\(a\)が\(X\)の極小元であることは、\(a\)以下の\(X\)の任意の要素が\(a\)と一致することと必要十分です。

例(実数の大小関係と極小元)
すべての実数からなる集合\(\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\)は\(\left[0,1\right] \)の極小元です。実際、\(0\in \left[ 0,1\right] \)であるとともに、\begin{equation}x\leq 0 \quad \cdots (1)
\end{equation}を満たす\(x\in \left[ 0,1\right] \)を任意に選んだとき、\(\left[ 0,1\right] \)の定義より、\begin{equation}0\leq x \quad \cdots (2)
\end{equation}が成り立ちます。\(\left(1\right) ,\left( 2\right) \)および\(\leq \)の反対称律より、\begin{equation*}x=0
\end{equation*}が成り立つため、先の命題より、\(0\)が\(\left[ 0,1\right]\)の極小元であることが示されました。
例(包含関係と極小元)
集合\(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\} \)は\(X\)の極小元です。実際、\(\left\{ a\right\} \in X\)であるとともに、\begin{equation*}Y\subset \left\{ a\right\}
\end{equation*}を満たす集合\(Y\in X\)を任意に選んだとき、\(X\)の定義より、\begin{equation*}Y=\left\{ a\right\}
\end{equation*}が成り立つため、先の命題より、\(\left\{ a\right\} \)が\(X\)の極小元であることが示されました。

 

極大元や極小元の存在

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

例(実数の大小関係と極大元・極小元)
すべての実数からなる集合\(\mathbb{R} \)上に大小関係\(\leq \)を定義します。\(\left( \mathbb{R} ,\leq \right) \)は全順序集合です。すべての整数からなる集合\(\mathbb{Z} \)は\(\mathbb{R} \)の非空な部分集合です。仮に\(\mathbb{Z} \)の極大元\(a\in \mathbb{Z} \)が存在するものと仮定した場合、\begin{equation*}\exists a+1\in \mathbb{Z} :a<a+1
\end{equation*}が成り立ちますが、これは\(a\)が\(\mathbb{Z} \)の極大元であることと矛盾です。したがって\(\mathbb{Z} \)の極大元は存在しません。同様に、\(\mathbb{Z} \)の極小元\(a\in \mathbb{Z} \)が存在するものと仮定した場合、\begin{equation*}\exists a-1\in \mathbb{Z} :a-1<a
\end{equation*}が成り立ちますが、これは\(a\)が\(\mathbb{Z} \)の極小元であることと矛盾です。したがって\(\mathbb{Z} \)の極小元は存在しません。

復習になりますが、順序集合\(\left( A,\leq \right) \)が全順序集合であるとともに非空な部分集合\(X\)が有限集合である場合、\(X\)の最大元最小元が存在することが保証されます。一方、非空な有限集合\(X\)の極大元や極小元が存在することを保証するためには、\(\left( A,\leq \right) \)は全順序集合である必要はなく、半順序集合であれば十分です。

命題(半順序集合の有限部分集合の極大元と極小元)
半順序集合\(\left( A,\leq \right) \)の非空な部分集合\(X\)が有限集合である場合には、\(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*}に注目します。自然数\(24\)は\(X\)の極大元です。実際、\(24\in X\)であるとともに、\begin{equation*}24|y
\end{equation*}を満たす自然数\(y\in X\)を任意に選んだとき、\(X\)の中には\(24\)とは異なる\(24\)の倍数は存在しないため、\begin{equation*}y=24
\end{equation*}となります。以上より、\(24\)が\(X\)の極大元であることが示されました。また、自然数\(30\)もまた\(X\)の極大元です。実際、\(30\in X\)であるとともに、\begin{equation*}30|y
\end{equation*}を満たす自然数\(y\in X\)を任意に選んだとき、\(X\)の中には\(30\)とは異なる\(30\)の倍数は存在しないため、\begin{equation*}y=30
\end{equation*}となります。以上より、\(30\)もまた\(X\)の極大元であることが示されました。同様にして、自然数\(2,3,5\)がいずれも\(X\)の極小元であることが示されます。

 

極大元と最大元・極小元と最小元の関係

一般に、順序集合の非空な部分集合が最大元を持つ場合、それは極大元でもあります。また、最小元は極小元でもあります。

命題(最大元は極大元・最小元は極小元)
半順序集合\(\left( A,\leq \right) \)の非空な部分集合\(X\)を任意に選んだとき、最大元\(\max X\)が存在するならば、それは\(X\)の極大元でもある。また、最小元\(\min X\)が存在するならば、それは\(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*}に注目します。自然数\(240\in X\)は\(X\)の任意の要素の倍数であるため、すなわち、\begin{equation*}\exists 240\in X,\ \forall x\in X:x|240
\end{equation*}が成り立つため、\(240\)は\(X\)の最大元です。したがって、先の命題より、\(240\)は\(X\)の極大元でもあります。実際、\begin{equation*}240|y
\end{equation*}を満たす自然数\(y\in X\)を任意に選んだとき、\(X\)の中には\(240\)とは異なる\(240\)の倍数は存在しないため、\begin{equation*}y=240
\end{equation*}となります。以上より\(240\)が\(X\)の極大元であることが示されましたが、これは先の命題の主張と整合的です。同様にして、自然数\(2\in X\)が\(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\)のすべての要素の倍数であるような自然数は\(X\)の中に存在しないため\(\max X\)は存在しません。その一方で、\(24\)は\(X\)の極大元です。実際、\(24\in X\)であるとともに、\begin{equation*}24|y
\end{equation*}を満たす\(y\in X\)を任意に選んだとき、\(X\)の中には\(24\)とは異なる\(24\)の倍数は存在しないため、\begin{equation*}y=24
\end{equation*}が成り立ちます。以上より、\(24\)が\(X\)の極大元であることが示されました。また、\(X\)のすべての要素の約数であるような自然数は\(X\)の中に存在しないため\(\min X\)は存在しません。その一方で、\(2\)は\(X\)の極小元です。実際、\(2\in X\)であるとともに、\begin{equation*}x|2
\end{equation*}を満たす\(x\in X\)を任意に選んだとき、\(X\)の中には\(2\)とは異なる\(2\)の約数は存在しないため、\begin{equation*}x=2
\end{equation*}が成り立ちます。以上より、\(2\)が\(X\)の極小元であることが示されました。

ただし、問題としている順序集合\(\left( A,\leq \right) \)が全順序集合である場合には、最大元と極大元は概念として一致し、最小元と極小元は概念として一致します。

命題(極大元と最大元・極小元と最小元の関係)
全順序集合\(\left( A,\leq \right) \)の非空な部分集合\(X\)を任意に選んだとき、要素\(a\in A\)が\(X\)の極大元であることは、\(a\)が\(X\)の最大元であるための必要十分条件である。また、要素\(a\in 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*}について、\begin{eqnarray*}
\max \left[ 0,1\right] &=&1 \\
\min \left[ 0,1\right] &=&0
\end{eqnarray*}が成り立ちますが、大小関係\(\leq \)は全順序であるため、先の命題より、\(1\)は\(\left[ 0,1\right] \)の極大元であり、\(0\)は\(\left[0,1\right] \)の極小元です。
例(実数の大小関係)
すべての実数からなる集合\(\mathbb{R} \)上に大小関係\(\leq \)を定義します。\(\left( \mathbb{R} ,\leq \right) \)は全順序集合です。\(\mathbb{R} \)の部分集合\begin{equation*}\left( 0,1\right) =\left\{ x\in \mathbb{R} \ |\ 0<x<1\right\}
\end{equation*}について、\(\max \left( 0,1\right) \)と\(\min \left( 0,1\right) \)はともに存在しません。大小関係\(\leq \)は全順序であるため、先の命題より、\(\left( 0,1\right) \)の極大元や極小元もまた存在しません。

 

演習問題

問題(最大元・最小元)
すべての自然数からなる集合\(\mathbb{N} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{N} \times \mathbb{N} \)に対して、\begin{equation*}x\leq y\Leftrightarrow x\text{で}y\text{は割り切れる}
\end{equation*}を満たすものとして定義される二項関係\(\leq \)は半順序です。\(\mathbb{N} \)の部分集合\begin{equation*}A=\mathbb{N} \backslash \left\{ 1\right\} =\left\{ 2,3,4,\cdots \right\}
\end{equation*}に注目します。\(A\)の極大元や極小元は存在しますか。議論してください。
解答を見る

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

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

関連知識

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

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

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

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

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

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

全順序
順序部分集合

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

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

非空な順序部分集合のある要素が、他の任意の要素以上である場合、それを最大元と呼びます。また、非空な順序部分集合のある要素が、他の任意の要素以下である場合、それを最小元と呼びます。

DISCUSSION

質問とコメント

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

関係