束（lattice）

定義（上界、下界）

半順序集合 ＜P,⊑＞ の部分集合 S と P の元aについて、
∀x∈S(x ⊑ a)
であるとき、a は S の上界（upper bound）という。同様に、
∀x∈S(a ⊑ x)
であるとき、a は S の下界（lower bound）という。

定義（最小上界、最大下界、結び、交わり）

半順序集合 ＜P,⊑＞ の任意の２元からなる部分集合 {a, b} ⊆ P に対して、最小上界、最大下界をそれぞれ a∧b、a∨b で表し、a と b の結び（join）、交わり（meet）と呼ぶ。

定義（束）

半順序集合 ＜P,⊑＞ の任意の２元に対して {a, b} の最小上界（least upper bound; l.u.b.）、最大下界（greatest lower bound; g.l.b.）が存在するとき、P を束（lattice）と呼ぶ。代数構造を明示する場合は特に ＜P,∧,∨＞ と表すこととする。

束 ＜P,∧, ∨＞ においては、明らかに次の３法則が成り立つ。

• （可換律; commutative law）a∨b = b∨a, a∧b = b∧a,
• （結合律; associative law）a∨(b∨c) = (a∨b)∨c, a∧(b∧c) = (a∧b)∧c,
• （吸収律; absorption law）a∨(a∧b) = a, a∧(a∨b) = a.

定理（結び、交わりと半順序関係の同値性）

集合 L について、上の３法則を満たす演算 ∨, ∧ が与えられているとき、a∨b = b と a∧b = a とは同値であり、このとき2項関係 R を
R = {(x,y) ∈ L×L | x∨y = y}
と定義するとき、＜L, R＞ は半順序集合となる。

（証明）
a∨b = a が反射律、反対称律、推移律を満たすことを示せばよい。

• 反射律 a∨a = a∨(a∧(a∨b)) = a 従って aRa,
• 反対称律 a∨b = b かつ b∨a = a ならば、b = a∨b = b∨a = a したがって、b = a,
• 推移律 a∨b = b かつ b∨c = c ならば、a∨c = a∨(b∨c) = (a∨b)∨c = b∨c = c したがって、aRc.

以上より、＜L,R＞は半順序集合である。