定義
部分順序アプローチ
させて
部分順序を持つ集合である
そして
要素
の
と呼ばれる会う(または最大下限または(下限)
そして、で表されます。
以下の2つの条件が満たされる場合:
(つまり、
は下限値です
)- いかなる場合でも
もし
それから
(つまり、
他の下限値以上である
)
ペアに下限がまったくない場合、または下限のいずれも他のすべての下限より大きくない場合、その交点は存在しない可能性があります。ただし、交点が存在する場合は、
そうなると、両方ともユニークになります。
は最大の下限値です
それから
そしてこうして
[ 2 ]要素のすべてのペアが
会合がある場合、会合は部分的な二項演算として見なすことができる。
[ 1 ]
会合が存在する場合は、次のように示されます。
要素のすべてのペアが
ミーティングを行うと、ミーティングはバイナリ操作になります
そして、この操作が次の3つの条件を満たすことは容易にわかる。任意の要素に対して
(可換性)
(結合性)および
(冪等性)
結合は、結合と二重に定義されます。
存在する場合は、
要素
の
は参加する(または最小上限またはsupremum ) の
で
以下の2つの条件が満たされる場合:
(つまり、
は上限です
)- いかなる場合でも
もし
それから
(つまり、
他の上限値以下である
)
アプローチの同等性
もし
は半順序集合であり、 の各要素のペアは
会合があるなら、確かに
かつその場合に限り
後者の場合、確かに
は下限値です
そしてそれ以来
が最大の下限であるのは、それが下限である場合に限る。したがって、普遍代数アプローチにおける交わりによって定義される半順序は、元の半順序と一致する。
逆に、
はミートセミラティスであり、部分順序は
は普遍代数アプローチで定義され、
一部の要素については
それから
は最大の下限値です
に関して
以来
そのため
同様に、
そしてもし
は別の下限値です
それから
そこから
したがって、元の会合によって定義される部分順序によって定義される会合が存在し、2つの会合は一致する。
言い換えれば、この2つのアプローチは本質的に同等の概念、すなわち二項関係と二項演算の両方を備えた集合を生み出し、これらの構造のそれぞれが他方を決定し、それぞれ部分順序または交点の条件を満たす。
例
あるべき集合が
通常の方法で部分的に順序付けられています(
) 結合は和集合であり、交わりは交差です。記号では、
(これらの記号の類似性は、次のことを覚えるための記憶術として使用できる)
結合/上限と
は上限/下限を表します[注1 ] )。
より一般的には、
ある集合の部分集合の族である
それは部分的に順序付けられています
もし
任意の和集合と任意の積集合の下で閉じられており、
に属する
それから
しかしもし
組合の下で閉鎖されていない
存在する
一意の
-最小
そのため
例えば、
それから
一方、
それから
集合が存在しないのは、
は、
で
それはおそらく最小上限値である
しかし
そして
もし
それから
上限がないため存在しない
で
注記
- 1 2グレーツァー、ジョージ( 2002年11月21日)。一般格子理論:第2版。シュプリンガー・サイエンス&ビジネス・メディア。p.52。ISBN 978-3-7643-6996-5。
- ↑ハクテル、ゲイリー・D.、ソメンツィ、ファビオ(1996)。論理合成と検証アルゴリズム。クルーワー・アカデミック・パブリッシャーズ。p. 88。ISBN 0792397460。
- ↑この典型的な単純な例では、上限と下限がすぐに判明します
は
それぞれ。
に
そして
に
したがって、最も一般的な状況では、
は上限を表します(上限は上からの制限であり、
「上」
そして
) その間
は下限を表します(下限は、
「以下」
そして
) これは、ミーティング/ジョインが何で示されるかを記憶するためにも使用できます。
または
直感的には、 2つの集合を「結合」すると、それらの和集合が得られるはずだ。
に似ている
したがって、「結合」は次のように表す必要があります。
同様に、2つの集合は交差部分で「出会う」べきである。
に似ている
したがって、「meet」は次のように表記されなければならない。