結びと交わり
From Wikipedia, the free encyclopedia
半順序集合 P において、部分集合 S の結び (join) と交わり (meet) はそれぞれ S の上限（最小上界）⋁S と S の下限（最大下界）⋀S である。一般に、半順序集合の部分集合の結びや交わりは存在するとは限らない；存在するときには、それらは P の元である。
結びと交わりは P の元の対上の可換結合的冪等部分二項演算として定義することもできる。a と b が P の元であるとき、結びは a ∨ b と書かれ、交わりは a ∧ b と書かれる。
結びと交わりは順序の反転に関して対称双対である。全順序集合の部分集合の結び/交わりは単にその極大/極小元である。
すべての対が結びを持つような半順序集合は join-semilattice である。双対的に、すべての対が交わりを持つような半順序集合は meet-semilattice である。join-semilattice でも meet-semilattice でもあるような半順序集合は束である。単にすべての対ではなくすべての部分集合が結びと交わりを持つような束は完備束である。すべての対が結びや交わりをもつわけではないがその演算が（定義されるときに）ある公理を満たすような partial lattice を定義することもできる[1]。
半順序からのアプローチ
A を半順序 ≤ を持った集合とし、x と y を A の2つの元とする。A の元 z が x と y の交わり（あるいは最大下界あるいは下限）であるとは、以下の2条件が満たされることをいう。
- z ≤ x かつ z ≤ y（すなわち z は x と y の下界である）。
- w ≤ x かつ w ≤ y なる A の任意の w に対して、w ≤ z となる（すなわち z は x と y の任意の他の下界よりも大きいか等しい）。
x と y の交わりが存在すれば、一意である。なぜならば z と z′ がともに x と y の最大下界とすると、z ≤ z′ かつ z′ ≤ z だから z = z′ となるからである。交わりが存在するとき、x ∧ y と書かれる。A の元の対には交わりを持たないものがあるかもしれない。それは、そもそも可解を持たないからか、あるいはどの下界も他の全てより大きくないからである。元のすべての対が交わりを持つとき、交わりは A 上の二項演算であり、この演算が以下の3つの条件を満たすことを見るのは容易である。A の任意の元 x, y, z に対して、
普遍代数学からのアプローチ
定義により、集合 A 上の二項演算 ∧ が交わりとは、3条件 a, b, c を満たすことをいう。このとき対 (A, ∧) は交わり半束である。さらに、次のようにして A 上の二項関係 ≤ を定義できる：x ≤ y ⇔ x ∧ y = x。実は、この関係は A 上の半順序である。実際、A の任意の元 x, y, z に対して、
- x ≤ x、なぜならば c により x ∧ x = x;
- x ≤ y かつ y ≤ x ならば、a により x = x ∧ y = y ∧ x = y;
- x ≤ y かつ y ≤ z ならば x ≤ z、なぜならば b により x ∧ z = (x ∧ y) ∧ z = x ∧ (y ∧ z) = x ∧ y = x。
結びと交わりはともにこの定義を満たすことに注意。同伴な交わりと結びの対は互いに逆順序となる半順序を定める。それらの順序のうちの一方を主（正順）として選んで、その順序を与える演算を交わり、他方を結びと定義しなおすこともできる。
2つのアプローチの同値性
(A, ≤) が半順序集合であって、A の元の各対が交わりを持つとき、確かに x ∧ y = x であるのは x ≤ y のとき、かつそのときに限る。なぜならば後者のとき x はたしかに x と y の下界であり、明らかに x が最大下界であるのはそれが下界であるとき、かつそのときに限る。したがって、普遍代数学からのアプローチにおける交わりによって定義された半順序はもともとの半順序と一致する。
逆に、(A, ∧) が meet-semilattice で、半順序 ≤ が普遍代数学からのアプローチのように定義され、A のある元 x と y に対して z = x ∧ y であるとき、z は ≤ に関する x と y の最大下界である。なぜならば
- z ∧ x = x ∧ z = x ∧ (x ∧ y) = (x ∧ x) ∧ y = x ∧ y = z
でありしたがって z ≤ x だからである。同様に、z ≤ y であり、w が x と y の別の下界であるとき、w ∧ x = w ∧ y = w であり、したがって
- w ∧ z = w ∧ (x ∧ y) = (w ∧ x) ∧ y = w ∧ y = w
である。したがって、もともとの交わりによって定義される半順序によって定義される交わりがあり、その2つの交わりは一致する。
言い換えると、この2つのアプローチは本質的に同値な概念を定めている。それは1つの二項関係および1つの二項演算（それぞれ半順序および交わりの条件を満足する）を備えた集合であって、この2つの構造の各々一方が他方を決定するようなものである。
一般の部分集合の交わり
(A, ∧) が meet-semilattice であるとき、交わりは iterated binary operation に書かれている手法で任意の空でない有限集合の well-defined な交わりに拡張できる。あるいは、交わりが半順序を定義するあるいは半順序によって定義されているとき、A のある部分集合はこれについての下限をもち、そのような下限をその部分集合の交わりを考えることは合理的である。空でない有限部分集合に対して、2つのアプローチは同じ結果を生み出し、したがっていずれをも交わりの定義として取ることができる。A のすべての部分集合が交わりを持つ場合、(A, ≤) は実は完備束である。詳細は完備性 (順序集合論)を参照。