最大要素と最小要素

Concept in mathematics

60 の約数集合のハッセ図。関係「÷ 」によって部分的に順序付けられている。赤色の部分集合には、最大元 30 と最小元 1 がそれ​​ぞれ存在する。これらの元は、赤色の部分集合のそれぞれ最大元と最小元でもある。 ${\displaystyle P}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle S=\{1,2,3,5,6,10,15,30\}}$

数学、特に順序論において、半順序集合（poset）の部分集合の最大元とは、 の元のうち、 の他のどの元よりも大きい元をいう。最小元という用語は双対的に定義され、 の元のうち、の他のどの元よりも小さい元をいう。 ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S.}$

定義

を順序付き集合とし、を とします。 要素が の最大要素であるとは、次も満たす場合です。 ${\displaystyle (P,\leq )}$ ${\displaystyle S\subseteq P.}$ ${\displaystyle g\in P}$ ${\displaystyle S}$ ${\displaystyle g\in S}$

${\displaystyle s\leq g}$すべての人のために ${\displaystyle s\in S.}$

上記の定義において関係の の側を切り替えることで、 の最小元 の定義が得られます。明示的に言うと、ある元が の最小元であるとは、 かつ が以下の条件も満たす場合を指します。 ${\displaystyle s}$ ${\displaystyle S}$ ${\displaystyle l\in P}$ ${\displaystyle S}$ ${\displaystyle l\in S}$

${\displaystyle l\leq s}$すべての人のために ${\displaystyle s\in S.}$

が半順序集合である場合、最大元は最大で1つ、最小元は最大で1つしか持ちません。最大元が存在し、かつそれが一意である場合、その元は の最大元と呼ばれます。「 の最小元」という用語も同様に定義されます。 ${\displaystyle (P,\leq )}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$

が最大要素（または最小要素）を持つ場合、この要素はトップ（またはボトム）とも呼ばれます。 ${\displaystyle (P,\leq )}$ ${\displaystyle (P,\leq ).}$

上限/下限との関係

最大要素は上限と密接に関係しています。

を順序付き集合とし、における の上限は、 であり、かつ すべてのに対してである元である。重要なのは、におけるの上限はの元である必要はないということである。 ${\displaystyle (P,\leq )}$ ${\displaystyle S\subseteq P.}$ ${\displaystyle S}$ ${\displaystyle (P,\leq )}$ ${\displaystyle u}$ ${\displaystyle u\in P}$ ${\displaystyle s\leq u}$ ${\displaystyle s\in S.}$ ${\displaystyle S}$ ${\displaystyle P}$ ${\displaystyle S.}$

の場合、が の最大元である場合、かつ がにおけるの上限である場合に限ります。特に、 の任意の最大元は( における)の上限でもありますが、におけるの上限が の最大元である場合、かつそれがに属する場合に限ります。「 がにおけるの上限である」の定義が 特別な場合では、次のようになります。 は、すべて に対してかつ となる元であり、これは前述の最大元の定義と完全に同一です。したがって、 がにおけるの上限である場合に限り、かつ がの最大元です。 ${\displaystyle g\in P}$ ${\displaystyle g}$ ${\displaystyle S}$ ${\displaystyle g}$ ${\displaystyle S}$ ${\displaystyle (P,\leq )}$ ${\displaystyle g\in S.}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle P}$ ${\displaystyle S}$ ${\displaystyle P}$ ${\displaystyle S}$ ${\displaystyle S.}$ ${\displaystyle P=S,}$ ${\displaystyle u}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle u}$ ${\displaystyle u\in S}$ ${\displaystyle s\leq u}$ ${\displaystyle s\in S,}$ ${\displaystyle g}$ ${\displaystyle S}$ ${\displaystyle g}$ ${\displaystyle S}$ ${\displaystyle S}$

がにおけるの上限であり、におけるの上限ではない場合（ の場合に限り起こり得る）、 はの最大元にはなり得ません（ただし、 の他の元がの最大元となる可能性はあります）。特に、が最大元を持たないことと、におけるの何らかの上限が存在することが同時に起こり得ます。 ${\displaystyle u}$ ${\displaystyle S}$ ${\displaystyle P}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle u\not \in S}$ ${\displaystyle u}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle P}$

集合に上限が存在する場合でも、負の実数の例が示すように、最大​​元が存在する必要はありません。また、この例は、最小の上限（この場合は0）が存在するからといって、最大元が存在するとは限らないことを示しています。

最大要素と局所的/絶対的最大値との対比

上記の割り切れる順序において、赤の部分集合には3と4という2つの極大元があり、どちらも最大ではありません。赤の部分集合には1という1つの極小元があり、これはまた、赤の部分集合の最小元でもあります。 ${\displaystyle S=\{1,2,3,4\}}$

順序付けされた集合のサブセットの最大要素は、集合内の他のどの要素よりも厳密に小さくない要素である集合の 最大要素と混同しないでください。

を順序付き集合とし、次の条件が満たされる場合、 要素はの最大要素であるといわれます。 ${\displaystyle (P,\leq )}$ ${\displaystyle S\subseteq P.}$ ${\displaystyle m\in S}$ ${\displaystyle S}$

が満たされるときは必ず ${\displaystyle s\in S}$ ${\displaystyle m\leq s,}$ ${\displaystyle s\leq m.}$

が半順序集合である場合、が の最大元となるのは、 が存在しないときのみである。の 最大元は、部分集合の最大元を意味するように定義される。 ${\displaystyle (P,\leq )}$ ${\displaystyle m\in S}$ ${\displaystyle S}$ ${\displaystyle s\in S}$ ${\displaystyle m\leq s}$ ${\displaystyle s\neq m.}$ ${\displaystyle (P,\leq )}$ ${\displaystyle S:=P.}$

集合には、最大元がなくても複数の極大元が存在することがあります。上限や極大元と同様に、最大元は存在しないこともあります。

全順序集合において、最大元と最大元は一致し、これは最大値とも呼ばれます。関数値の場合は、局所最大値との混同を避けるため、絶対最大値とも呼ばれます。^[1]最小 値と絶対最小値は双対であり、これらを合わせて絶対極値と呼ばれます。最小元についても同様の結論が成り立ちます。

最大要素と最大要素を区別する際の比較可能性（非）の役割

順序付き集合の最大元と極大元との間の最も重要な違いの一つは、それらがどの要素と比較できるかという点にあります。2つの要素は、またはの場合には比較可能とされ、 の場合には比較不可能とされます。順序付けは反射的であるため（つまり、すべての要素 について が成り立つため）、すべての要素は常にそれ自身と比較可能です。したがって、比較不可能となり得る要素のペアは、互いに異なるペアのみです。しかし、一般に、順序付き集合（さらには有向半順序付き集合）には、比較不可能な要素が含まれる場合があります。 ${\displaystyle g}$ ${\displaystyle m}$ ${\displaystyle (P,\leq )}$ ${\displaystyle x,y\in P}$ ${\displaystyle x\leq y}$ ${\displaystyle y\leq x}$ ${\displaystyle x\leq x}$ ${\displaystyle x}$ ${\displaystyle x}$

定義により、任意の に対して であるならば、その元は の最大元である。したがって、 の最大元は、特にの全ての元と比較可能でなけれ ばならない。これは、最大元には要求されない。 の最大元は の全ての元と比較可能である必要はない。 これは、「最大元」の定義とは異なり、「最大元」の定義には重要なif文が含まれているためである。が の最大元であるための条件は、次のように言い換えることができる。 ${\displaystyle g\in P}$ ${\displaystyle (P,\leq )}$ ${\displaystyle s\leq g,}$ ${\displaystyle s\in P}$ ${\displaystyle (P,\leq )}$ ${\displaystyle P.}$ ${\displaystyle (P,\leq )}$ ${\displaystyle P.}$ ${\displaystyle m\in P}$ ${\displaystyle (P,\leq )}$

すべてのIF（比較できない要素は無視される）の場合、 ${\displaystyle s\in P,}$ ${\displaystyle m\leq s}$ ${\displaystyle m}$ ${\displaystyle s\leq m.}$

すべての要素が最大だが、どれも最大ではない例

が少なくとも2つの（異なる）要素を含む集合であるとし、 がに属する 場合、 もも成り立たないことを宣言することでにおける半順序を定義する。これは、 における異なる（すなわち、等しくない）要素のすべてのペアが において比較可能であることを示す。したがって、が最大元を持つことはできない（ の最大元は、特に のすべての要素と比較可能でなければならないが、 にはそのような要素がないため）。しかし、 には と比較可能であり、かつその要素が 自身である要素が1つだけ存在するため（もちろん）、 のすべての要素は の最大元となる。^{[注 1]} ${\displaystyle S}$ ${\displaystyle \,\leq \,}$ ${\displaystyle S}$ ${\displaystyle i\leq j}$ ${\displaystyle i=j.}$ ${\displaystyle i\neq j}$ ${\displaystyle S}$ ${\displaystyle i\leq j}$ ${\displaystyle j\leq i}$ ${\displaystyle S}$ ${\displaystyle (S,\leq )}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle m\in S}$ ${\displaystyle (S,\leq )}$ ${\displaystyle S}$ ${\displaystyle m}$ ${\displaystyle \geq m,}$ ${\displaystyle m}$ ${\displaystyle \leq m}$

対照的に、順序付けされたセット に最大要素がある場合、は必然的にの最大要素になります。さらに、最大要素が のすべての要素と比較可能であることの結果として、も半順序付けされている場合、 が の唯一の最大要素であると結論付けることができます。ただし、順序付けされたセットも半順序付けされていない 場合、一意性の結論は保証されなくなります。たとえば、 が空でないセットであり、が常にすべてに対して成り立つと宣言することによっての順序付けを定義するとします。有向順序付けされたセットが半順序付けされている場合、かつ に要素が 1 つだけある場合に限ります。 のすべての要素のペアは比較可能であり、のすべての要素はの最大要素 (したがって最大要素でもある) です。したがって特に、に少なくとも 2 つの要素がある場合、 には複数の異なる最大要素が存在します。 ${\displaystyle (P,\leq )}$ ${\displaystyle g}$ ${\displaystyle g}$ ${\displaystyle (P,\leq )}$ ${\displaystyle g}$ ${\displaystyle P,}$ ${\displaystyle (P,\leq )}$ ${\displaystyle g}$ ${\displaystyle (P,\leq ).}$ ${\displaystyle (P,\leq )}$ ${\displaystyle R}$ ${\displaystyle \,\leq \,}$ ${\displaystyle R}$ ${\displaystyle i\leq j}$ ${\displaystyle i,j\in R.}$ ${\displaystyle (R,\leq )}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle (R,\leq ).}$ ${\displaystyle R}$ ${\displaystyle (R,\leq )}$

プロパティ

全体を通して、半順序集合とし、 ${\displaystyle (P,\leq )}$ ${\displaystyle S\subseteq P.}$

• 集合は最大で1 つの最大要素を持つことができます。^{[注 2]}したがって、集合に最大要素がある場合、その集合は必ず一意です。 ${\displaystyle S}$
• もしそれが存在するなら、の最大元はの上限であり、それは にも含まれる。 ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S.}$
• がの最大元である場合、 も の最大元である^{[注 3]。}さらに、 の他の任意の最大元は必然的に に等しい^{[注 4]。} ${\displaystyle g}$ ${\displaystyle S}$ ${\displaystyle g}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle g.}$
  • したがって、集合に複数の最大要素がある場合、最大要素を持つことはできません。 ${\displaystyle S}$
• が昇順連鎖条件を満たす場合、の部分集合が最大元を持つのは、 が 1 つの最大元を持つ場合のみである。^{[注 5]} ${\displaystyle P}$ ${\displaystyle S}$ ${\displaystyle P}$
• への制約が全順序である場合（一番上の図は例です）、最大元と最大元の概念は一致します。^{[注 6]} ${\displaystyle \,\leq \,}$ ${\displaystyle S}$ ${\displaystyle S=\{1,2,4\}}$
  • しかし、これは必要条件ではありません。なぜなら、最大要素を持つ場合は常に、上記のように概念も一致するからです。 ${\displaystyle S}$
• の最大元と最大元の概念がの2元部分集合のすべてにおいて一致する場合、 は[^{注 7]}上の全順序となる。 ${\displaystyle S}$ ${\displaystyle P,}$ ${\displaystyle \,\leq \,}$ ${\displaystyle P.}$

十分な条件

• 有限チェーンには常に最大要素と最小要素が存在します。

上と下

半順序集合全体の最小元と最大元は特別な役割を果たし、それぞれボトム（⊥）とトップ（⊤）、あるいはゼロ（0）とユニット（1）とも呼ばれます。両方が存在する場合、そのポセットは有界ポセットと呼ばれます。0と1の表記は、ポセットが補格子であり、混乱の可能性がない場合、つまり、ボトムとトップとは異なる要素0と1を既に含む数の半順序について言及していない場合に、好ましく使用されます。最小元と最大元の存在は、半順序の 特別な完全性特性です。

さらに詳しい入門情報については、順序理論に関する記事をご覧ください。

例

例2のハッセ図

• 実数の集合において、整数の部分集合には上限がありません。 ${\displaystyle \mathbb {R} }$
• 上の関係が で与えられるとします。この集合には上限と下限がありますが、最小上限はなく、最大元もありません (図を参照)。 ${\displaystyle \,\leq \,}$ ${\displaystyle \{a,b,c,d\}}$ ${\displaystyle a\leq c,}$ ${\displaystyle a\leq d,}$ ${\displaystyle b\leq c,}$ ${\displaystyle b\leq d.}$ ${\displaystyle \{a,b\}}$ ${\displaystyle c}$ ${\displaystyle d,}$
• 有理数では、平方数が 2 未満の数の集合には上限はありますが、最大元と最小上限はありません。
• 1 未満の数の集合には最小の上限、つまり 1 はありますが、最大の要素はありません。 ${\displaystyle \mathbb {R} ,}$
• 1 以下の数の集合には、最大の要素、つまり 1 があり、これが最小の上限でもあります。 ${\displaystyle \mathbb {R} ,}$
• 積順序を持つでは、を持つペアの集合には上限がありません。 ${\displaystyle \mathbb {R} ^{2}}$ ${\displaystyle (x,y)}$ ${\displaystyle 0<x<1}$
• 辞書式順序では、このセットには上限があります。たとえば、最小の上限はありません。 ${\displaystyle \mathbb {R} ^{2}}$ ${\displaystyle (1,0).}$

参照

• 本質的な上流と本質的な下流
• 始端目的語と終端目的語
• 最大要素と最小要素
• 上限と下限(下限)
• 上限と下限
• 整列順序— 空でないすべての集合が最小の要素を持つような非厳密な順序

注記

1. もちろん、この特定の例では、 に比較可能な要素が 1 つしか存在せず、それが必然的にそれ自身であるため、2 番目の条件「および」は冗長でした。 ${\displaystyle S}$ ${\displaystyle m,}$ ${\displaystyle m}$ ${\displaystyle \geq m,}$
2. と が両方とも最大であれば、 であり、したがって反対称性によりとなります。 ${\displaystyle g_{1}}$ ${\displaystyle g_{2}}$ ${\displaystyle g_{1}\leq g_{2}}$ ${\displaystyle g_{2}\leq g_{1},}$ ${\displaystyle g_{1}=g_{2}}$
3. がの最大元である場合、反対称性により、(および) は不可能になります。 ${\displaystyle g}$ ${\displaystyle S}$ ${\displaystyle s\in S,}$ ${\displaystyle s\leq g.}$ ${\displaystyle g\leq s}$ ${\displaystyle g\neq s}$
4. が最大元である場合、 が最大なので、したがってが最大です。 ${\displaystyle M}$ ${\displaystyle M\leq g}$ ${\displaystyle g}$ ${\displaystyle M=g}$ ${\displaystyle M}$
5. 場合のみ:上記を参照。 —場合:最大要素が 1 つだけあり、最大要素がない矛盾を と仮定します。は最大でないため、と比較できないものが存在する必要があります。したがって、 は最大になることはできません。つまり、がいくつかに対して成立する必要があります。後者はとも比較できない必要があります。は の最大性と矛盾し、 はおよびの比較不可能性と矛盾するためです。この議論を繰り返すと、無限の上昇チェーンが見つかります (それぞれがと比較できず、最大ではありません)。 これは、上昇チェーン条件と矛盾します。 ${\displaystyle S}$ ${\displaystyle m,}$ ${\displaystyle m}$ ${\displaystyle s_{1}\in S}$ ${\displaystyle m.}$ ${\displaystyle s_{1}\in S}$ ${\displaystyle s_{1}<s_{2}}$ ${\displaystyle s_{2}\in S.}$ ${\displaystyle m,}$ ${\displaystyle m<s_{2}}$ ${\displaystyle m}$ ${\displaystyle s_{2}\leq m}$ ${\displaystyle m}$ ${\displaystyle s_{1}.}$ ${\displaystyle s_{1}<s_{2}<\cdots <s_{n}<\cdots }$ ${\displaystyle s_{i}}$ ${\displaystyle m}$
6. を最大元とすると、 または のいずれかに対して2番目のケースでは、最大元の定義により が要求されるため、 が成り立ちます。言い換えると、は最大元です。 ${\displaystyle m\in S}$ ${\displaystyle s\in S}$ ${\displaystyle s\leq m}$ ${\displaystyle m\leq s.}$ ${\displaystyle m=s,}$ ${\displaystyle s\leq m.}$ ${\displaystyle m}$
7. 比較できない場合、最大値は 2 つあるが最大要素は存在せず、一致と矛盾します。 ${\displaystyle a,b\in P}$ ${\displaystyle S=\{a,b\}}$

参考文献

1. 局所性の概念は、関数の定義域が少なくとも位相空間であることを要求する。

• Davey, BA; Priestley, HA (2002). 『格子と秩序入門』（第2版）. Cambridge University Press . ISBN 978-0-521-78451-1。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Greatest_element_and_least_element&oldid=1320031333"