結合して出会う

推移 二項関係 v t e
対称 反対称 連結 根拠のある 結合している 会っている 再帰的 非再帰的 非対称 トータル、セミコネックス 反射防止 同値関係 Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ 準順序（準順序） ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ 一部注文 ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ 完全予約注文 ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ 全秩序 ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ 前井戸秩序 ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ 準井戸秩序 ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ 整列 ✗ Y Y Y ✗ ✗ Y ✗ ✗ 格子 ✗ Y ✗ ✗ Y Y Y ✗ ✗ 半格子の結合 ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ 半格子の会合 ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ 厳密な半順序 ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y 厳密な弱順序 ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y 厳密な全順序付け ✗ Y Y ✗ ✗ ✗ ✗ Y Y 対称 反対称 連結 根拠のある 結合している 会っている 再帰的 非再帰的 非対称 定義、すべての${\displaystyle a,b}$ ${\displaystyle S\neq \varnothing :}$ ${\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}aRb{\text{ と }}&bRa\\\Rightarrow a={}&b\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ または }}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}\min S\\{\text{exists}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}}$ ${\displaystyle aRa}$ ${\displaystyle {\text{not }}aRa}$ ${\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}}$
Y列の特性が行の項（一番左）に対して常に真であることを示します。一方、 ✗は、その特性が一般的には保証されていない（成り立つかどうかはわからない）ことを示します。例えば、すべての同値関係は対称的であるが、必ずしも反対称的であるとは限らないことは、「対称」列では 、また「反対称」列では ✗で示されます。Y すべての定義では、同次関係が推移的であることが暗黙的に要求されます。つまり、すべての条件が満たされ、条件が満たされると、 用語の定義には、この表に記載されていない追加のプロパティが必要になる場合があります。 ${\displaystyle R}$ ${\displaystyle a,b,c,}$ ${\displaystyle aRb}$ ${\displaystyle bRc}$ ${\displaystyle aRc.}$

このハッセ図は、4つの要素a、b、aとbの接合に等しい最大要素a b、そしてaとbの交点に等しい最小要素a b を持つ半順序集合を表しています。最大/最小要素と別の要素の接合/交点は最大/最小要素であり、逆に、最大/最小要素と別の要素の接合/交点は別の要素です。したがって、このposet内のすべてのペアには交点と交点の両方があり、posetは束として分類できます。${\displaystyle \vee}$ ${\displaystyle \wedge}$

数学、特に順序理論において、半順序集合の部分集合の結合は の上限（最小の上限）であり、同様にの交わりは の下限（最大の下限）であり、 と表される。一般に、半順序集合の部分集合の結合と交わりは必ずしも存在する必要はない。結合と交わりは、順序反転に関して互いに 双対である。${\displaystyle S}$ ${\displaystyle P}$ ${\displaystyle S,}$ ${\textstyle \bigvee S,}$ ${\displaystyle S}$ ${\textstyle \bigwedge S.}$

すべてのペアが接合を持つ半順序集合は、接合半格子（join-semilattice）である。同様に、すべてのペアが接合を持つ半順序集合は、接合半格子（meet- semilattice）である。接合半格子と接合半格子の両方である半順序集合は、格子（ lattice）である。すべてのペアだけでなく、すべての部分集合が接合と接合を持つ格子は、完全格子（complete lattice）である。すべてのペアが接合または接合を持つわけではないが、その演算が（定義されている場合）特定の公理を満たす部分格子（partial lattice）を定義することも可能である。^{[ 1 ]}

完全に順序付けられたセットのサブセットの結合/会合は、そのような要素が存在する場合、単にそのサブセットの最大/最小要素です。

半順序集合の部分集合が（上向きの）有向集合でもある場合、その結合（存在する場合）は有向結合または有向上限と呼ばれます。同様に、が下向きの有向集合である場合、その交わり（存在する場合）は有向交わりまたは有向下限と呼ばれます。 ${\displaystyle S}$ ${\displaystyle P}$ ${\displaystyle S}$

定義

半順序アプローチ

を半順序を持つ集合とし、の 元を${\displaystyle A}$ ${\displaystyle \,\leq ,\,}$ ${\displaystyle x,y\in A.}$ ${\displaystyle m}$ ${\displaystyle A}$ 会う（または最大の下限またはの最小値) であり次の 2 つの条件が満たされる場合、 は で表されます${\displaystyle x{\text{ and }}y}$ ${\displaystyle x\wedge y,}$

1. ${\displaystyle m\leq x{\text{ and }}m\leq y}$ (つまり、はの下限値です)。${\displaystyle m}$ ${\displaystyle x{\text{ and }}y}$
2. 任意の に対して の場合、 （つまり は の他の任意の下限以上）となります。${\displaystyle w\in A,}$ ${\displaystyle w\leq x{\text{ and }}w\leq y,}$ ${\displaystyle w\leq m}$ ${\displaystyle m}$ ${\displaystyle x{\text{ and }}y}$

ペアに下限が全く存在しないか、いずれの下限も他のすべての下限よりも大きくないため、必ずしも交わりが存在する必要はない。しかし、もし の交わりが存在するならば、それは一意である。なぜなら、もし の両方がの最大の下限であれば、となり、したがって^{[ 2 ]}となるからである。たとえ の全ての要素のペアが交わりを持たないとしても、その交わりは^{[ 1 ]}の部分二項演算と見なすことができる。${\displaystyle x{\text{ and }}y,}$ ${\displaystyle m{\text{ and }}m^{\prime }}$ ${\displaystyle x{\text{ and }}y,}$ ${\displaystyle m\leq m^{\prime }{\text{ and }}m^{\prime }\leq m,}$ ${\displaystyle m=m^{\prime }.}$ ${\displaystyle A}$ ${\displaystyle A.}$

交点が存在する場合、それは と表記されます。の全ての要素のペアが交点を持つ場合、交点はの二項演算であり、この演算が以下の3つの条件を満たすことは容易にわかります。任意の要素に対して${\displaystyle x\wedge y.}$ ${\displaystyle A}$ ${\displaystyle A,}$ ${\displaystyle x,y,z\in A,}$

1. ${\displaystyle x\wedge y=y\wedge x}$ （可換性）、
2. ${\displaystyle x\wedge (y\wedge z)=(x\wedge y)\wedge z}$ （結合性）、および
3. ${\displaystyle x\wedge x=x}$ （べき等性）。

結合は、存在する場合の結合と双対的に定義され、の 要素は${\displaystyle x{\text{ and }}y,}$ ${\displaystyle x\vee y.}$ ${\displaystyle j}$ ${\displaystyle A}$ 参加する（または最小上限または次の 2 つの条件が満たされる場合、 のsupremumになります${\displaystyle x{\text{ and }}y}$ ${\displaystyle A}$

1. ${\displaystyle x\leq j{\text{ and }}y\leq j}$ (つまり、はの上限です)。${\displaystyle j}$ ${\displaystyle x{\text{ and }}y}$
2. 任意の の場合、（つまり、は の他の任意の上限以下です）。${\displaystyle w\in A,}$ ${\displaystyle x\leq w{\text{ and }}y\leq w,}$ ${\displaystyle j\leq w}$ ${\displaystyle j}$ ${\displaystyle x{\text{ and }}y}$

普遍代数アプローチ

定義により、集合上の二項演算 は、3つの条件a、b、cを満たす場合、 meet（会合）です。したがって、そのペアはmeet-semilattic（会合半格子）です。さらに、 A上の二項関係を、次の場合に限って定義できます。 実際、この関係は 任意の要素に対して半順序です${\displaystyle \,\wedge \,}$ ${\displaystyle A}$ ${\displaystyle (A,\wedge )}$ ${\displaystyle \,\leq \,}$ ${\displaystyle x\leq y}$ ${\displaystyle x\wedge y=x.}$ ${\displaystyle A.}$ ${\displaystyle x,y,z\in A,}$

• ${\displaystyle x\leq x,}$ cによってなので;${\displaystyle x\wedge x=x}$
• もし、aによって;そして${\displaystyle x\leq y{\text{ and }}y\leq x}$ ${\displaystyle x=x\wedge y=y\wedge x=y}$
• if then since then by b .${\displaystyle x\leq y{\text{ and }}y\leq z}$ ${\displaystyle x\leq z}$ ${\displaystyle x\wedge z=(x\wedge y)\wedge z=x\wedge (y\wedge z)=x\wedge y=x}$

会合と結合はどちらもこの定義を等しく満たします。つまり、関連する会合操作と結合操作を組み合わせると、互いに逆の順序を持​​つ部分順序が生成されます。これらの順序のどちらかを主要な順序として選択する際には、どちらの操作が会合（同じ順序を与える操作）で、どちらが結合（もう一方の順序）とみなされるかを決定します。

アプローチの同値性

が半順序集合で、 の各要素のペアがの交わりを持つ場合、 であることと、後者の場合 は確かにの下限値であるため、 であることと、 が の最大の下限値であるため、が下限値である場合と、 がの最大値となることと、 が の最大値となることとが同値である。したがって、普遍代数アプローチにおける の交わりによって定義される半順序は、元の半順序と一致する ${\displaystyle (A,\leq )}$ ${\displaystyle A}$ ${\displaystyle x\wedge y=x}$ ${\displaystyle x\leq y,}$ ${\displaystyle x}$ ${\displaystyle x{\text{ and }}y,}$ ${\displaystyle x}$

逆に、 がmeet-semilatticeであり、部分順序が普遍代数アプローチで として定義され、いくつかの要素に対してがに関しての最大下限である場合、となり 、したがって となる 。同様に、がの別の下限である場合、となり、したがって と なる。したがって、元の meet によって定義された部分順序によって定義される meet が存在し、2 つの meet は一致します。 ${\displaystyle (A,\wedge )}$ ${\displaystyle \,\leq \,}$ ${\displaystyle z=x\wedge y}$ ${\displaystyle x,y\in A,}$ ${\displaystyle z}$ ${\displaystyle x{\text{ and }}y}$ ${\displaystyle \,\leq ,\,}$ $${\displaystyle z\wedge x=x\wedge z=x\wedge (x\wedge y)=(x\wedge x)\wedge y=x\wedge y=z}$$ ${\displaystyle z\leq x.}$ ${\displaystyle z\leq y,}$ ${\displaystyle w}$ ${\displaystyle x{\text{ and }}y,}$ ${\displaystyle w\wedge x=w\wedge y=w,}$ $${\displaystyle w\wedge z=w\wedge (x\wedge y)=(w\wedge x)\wedge y=w\wedge y=w.}$$

言い換えれば、2 つのアプローチは本質的に同等の概念、つまり 2 項関係と 2 項演算の両方を備えたセットを生み出し、これらの構造のそれぞれが他方を決定し、それぞれ半順序または一致の条件を満たします。

一般サブセットの会合

がmeet-semilatticeである場合、反復二項演算で説明されている手法によって、 meetを任意の空でない有限集合のwell-defined meetに拡張できます。あるいは、meetが半順序を定義するか、半順序によって定義される場合、 のいくつかのサブセットは実際にこれに関して下限を持ち、そのような下限をサブセットのmeetと見なすのは合理的です。空でない有限サブセットの場合、2つのアプローチは同じ結果をもたらすため、どちらもmeetの定義として採用できます。 の各サブセットにmeetがある場合、 は実際には完全束です。詳細については、完全性（順序理論）を参照してください。 ${\displaystyle (A,\wedge )}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle (A,\leq )}$

例

ある冪集合 が通常の方法（によって）で部分的に順序付けられている場合、結合は和集合、交わりは積集合です。記号では、 （これらの記号の類似性は、が結合／上限を表し、が交わり／下限を表すことを覚えるための記憶法として使用できます^{[注1 ]}）。 ${\displaystyle 2^{X}}$ ${\displaystyle \,\subseteq }$ ${\displaystyle \,\vee \,=\,\cup \,{\text{ and }}\,\wedge \,=\,\cap \,}$ ${\displaystyle \,\vee \,}$ ${\displaystyle \,\wedge \,}$

より一般的には、 が、 によって部分的に順序付けられているある集合の部分集合の族であるとします 。が任意の和集合および任意の積集合の下で閉じており、 が に属する場合、 しかし 、 が和集合の下で閉じていない場合、 が存在するのは、 となる唯一の最小の - が存在する場合のみです。 たとえば 、の場合、一方、の場合はは存在しません。 なぜなら、 は におけるの唯一の上限であり、 は最小の上限である可能性がありますが、の場合、にはの上限がないため、 は存在しません。${\displaystyle {\mathcal {F}}\neq \varnothing }$ ${\displaystyle X}$ ${\displaystyle \,\subseteq .\,}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle A,B,\left(F_{i}\right)_{i\in I}}$ ${\displaystyle {\mathcal {F}}}$ $${\displaystyle A\vee B=A\cup B,\quad A\wedge B=A\cap B,\quad \bigvee _{i\in I}F_{i}=\bigcup _{i\in I}F_{i},\quad {\text{ and }}\quad \bigwedge _{i\in I}F_{i}=\bigcap _{i\in I}F_{i}.}$$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle A\vee B}$ ${\displaystyle ({\mathcal {F}},\subseteq )}$ ${\displaystyle \,\subseteq }$ ${\displaystyle J\in {\mathcal {F}}}$ ${\displaystyle A\cup B\subseteq J.}$ ${\displaystyle {\mathcal {F}}=\{\{1\},\{2\},\{1,2,3\},\mathbb {R} \}}$ ${\displaystyle \{1\}\vee \{2\}=\{1,2,3\}}$ ${\displaystyle {\mathcal {F}}=\{\{1\},\{2\},\{1,2,3\},\{0,1,2\},\mathbb {R} \}}$ ${\displaystyle \{1\}\vee \{2\}}$ ${\displaystyle \{0,1,2\}{\text{ and }}\{1,2,3\}}$ ${\displaystyle \{1\}{\text{ and }}\{2\}}$ ${\displaystyle ({\mathcal {F}},\subseteq )}$ ${\displaystyle \{1\}\vee \{2\}}$ ${\displaystyle \{0,1,2\}\not \subseteq \{1,2,3\}}$ ${\displaystyle \{1,2,3\}\not \subseteq \{0,1,2\}.}$ ${\displaystyle {\mathcal {F}}=\{\{1\},\{2\},\{0,2,3\},\{0,1,3\}\}}$ ${\displaystyle \{1\}\vee \{2\}}$ ${\displaystyle \{1\}{\text{ and }}\{2\}}$ ${\displaystyle ({\mathcal {F}},\subseteq ).}$

参照

• 局所凸ベクトル格子

注記

1. Grätzer, George (2002年11月21日).一般格子理論：第2版. Springer Science & Business Media. 52ページ. ISBN 978-3-7643-6996-5。
2. Hachtel, Gary D.; Somenzi, Fabio (1996).論理合成と検証アルゴリズム. Kluwer Academic Publishers. p. 88. ISBN 0792397460。

1. この標準的な単純な例における上限とあることがすぐに分かります。 記号 と の類似性は、最も一般的な設定では が上限が「上」、上からの境界であるため）「下」と同様に、下からの境界であるため）ことを覚えるためのか で表すかを覚えるのにも使用できます。直感的に、2つの集合を「結合」すると、 に似た和集合が生成されるので「結合」は で表す必要があります。同様に、2つの集合は交差点で「会合」する必要があり、 に似たので、「会合」は で表す必要があります。${\displaystyle (2^{X},\subseteq )}$ ${\displaystyle \,\cup \,{\text{ and }}\,\cap \,,}$ ${\displaystyle \,\vee \,}$ ${\displaystyle \,\cup \,}$ ${\displaystyle \,\wedge \,}$ ${\displaystyle \,\cap \,}$ ${\displaystyle \,\vee \,}$ ${\displaystyle A\cup B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \,\wedge \,}$ ${\displaystyle A\cap B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \,\vee \,}$ ${\displaystyle \,\wedge .\,}$ ${\displaystyle A\cup B,}$ ${\displaystyle A\vee B,}$ ${\displaystyle \,\vee .\,}$ ${\displaystyle A\cap B,}$ ${\displaystyle A\wedge B,}$ ${\displaystyle \,\wedge .\,}$

参考文献

• Davey, BA; Priestley, HA (2002).格子と秩序入門（第2版）. ケンブリッジ:ケンブリッジ大学出版局. ISBN 0-521-78451-4. Zbl  1002.06001 .
• スティーブン・ヴィッカース(1989).論理によるトポロジー. ケンブリッジ理論計算機科学論文集. 第5巻. ISBN 0-521-36062-5. Zbl  0668.54001 .