束
半順序集合 (poset) の完備性 (completeness)
$ (X, \leq)を半順序集合とする。性質Pを満たす$ Xの任意の部分集合$ Aについて下限 (infimum) $ \wedge Aが存在するとき、$ XはP-completeであるという。同様に、性質Pを満たす$ Xの任意の部分集合$ Aについて上限 (supremum) $ \vee Aが存在するとき、$ XはP-cocompleteであるという。
すなわち$ \wedge A、$ \vee Aはそれぞれ$ x \leq \wedge A \iff x \leq A ($ x \in X) 、$ \vee A \leq x \iff A \leq x ($ x \in X) を満たす。
記法$ \vee: \vee 、$ \wedge: \wedge
反対称性から、$ \wedge A、$ \vee Aは存在すれば一意に定まる。
例
任意の有限部分集合について下限(上限)が存在するとき、$ Xはfinitely complete (cocomplete)。
両方満たすとき$ Xは束 (lattice)。
任意の有向部分集合について下限(上限)が存在するとき、$ Xはdirected complete (cocomplete)。
後者 (cocompleteness) を満たすとき$ Xは有向完備半順序 (dcpo)。
任意のω鎖について下限(上限)が存在するとき、$ Xはω-complete (cocomplete)。
後者 (cocompleteness) を満たすとき$ Xはω-完備半順序 (ωcpo)。
任意の部分集合について下限(上限)が存在するとき、$ Xはcomplete (cocomplete)。
両方満たすとき$ Xは完備束 (complete lattice)。
これらは同値。
束 (lattice)
$ (X, \leq)を半順序集合(poset)とする。$ Xが束 (lattice) であるとは、$ Xの任意の有限部分集合$ A \subseteq X について、上限 (supremum)$ \vee Aと下限 (infimum)$ \wedge Aが存在することを言う。
束論では $ \vee Aと$ \wedge Aはそれぞれ結び (join)、交わり (meet) と呼ばれる。
すなわち$ X はfinitely completeかつfinitely cocomplete。
前者を満たすときjoin-semilattice、後者を満たすときmeet-semilatticeという。
束には最小元$ \bot ・最大元$ \top が存在し、$ \bot = \vee \emptyおよび$ \top = \wedge \emptyで与えられる。
別の言い方として、$ \topと$ \botが存在する束を区別して有界束と呼ぶこともあるらしい。束の定義は”〜、$ Xの任意の空ではない (inhabited) 有限部分集合”、になる
Traditionally, a lattice need have only finite inhabited meets and joins; that is, it need not have a top or bottom element.() 別の定義として、$ a, b \in X について、二元の結び ($ a \vee b ) と交わり ($ a \wedge b)を $ a \vee b \leq x \iff a \leq xand$ b \leq x ($ x \in X) および$ x \leq a \wedge b \iff x \leq aand$ x \leq b ($ x \in X) とし、$ \topと$ \botをそれぞれ$ \wedgeと$ \veeの単位元とするものもある
完備束 (complete lattice)
$ (X, \leq)を半順序集合とする。$ Xが完備束 (complete lattice) であるとは、$ Xの任意の部分集合$ A \subseteq X について、上限 (supremum)$ \vee Aと下限 (infimum)$ \wedge Aが存在することを言う。
すなわち$ Xはcompleteかつcocomplete。
参考
Categories for Types (Crole) 1.2, 1.3