参加して会う

Concept in order theory

推移的な 二項関係 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{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&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]}の全ての要素のペアが交差を持つわけではないとしても、その交差は^[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-semilatticeである。さらに、 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. p. 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。

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