conditionally complete lattice〜完備束か、完備束から最大元 1 を除いたものか、完備束から最小元 0 を除いたものか、あるいは完備束から最大元と最小元の両方を取り除いたもの

数学における束(そく、英語: lattice)は、任意の二元集合が一意的な上限(最小上界、二元の結びとも呼ばれる)および下限(最大下界、二元の交わりとも呼ばれる)を持つ半順序集合である。それと同時に、ある種の公理的恒等式を満足する代数的構造としても定義できる。二つの定義が同値であることにより、束論は順序集合論と普遍代数学の双方の領域に属することとなる。さらに、半束 (semilattice) の概念は束の概念を含み、さらにハイティング代数ブール代数の概念も含む。これら束に関連する構造は全て順序集合としても代数系としても記述することができるという特徴を持つ。

半順序集合 (L, ≤) が束であるとは、以下の二条件が満足されるときに言う。

二元の結びの存在
L の任意の二元 a, b に対して、二元集合 {a, b} が結び(上限、最小上界、和) a ∨ b を持つ。
二元の交わりの存在
L の任意の二元 a, b に対して、二元集合 {a, b} が交わり(下限、最大下界、積) a ∧ b を持つ。
これにより、∨ および ∧ は L 上の二項演算となる。最初の条件は L が結び半束 (join-semilattice) となることを主張するものであり、後の条件は L が交わり半束 (meet-semilattice) となることをいうものである。二つの演算はその順序に関して単調である。すなわち、a1 ≤ a2 かつ b1 ≤ b2 ならば

a
1

b
1

a
2

b
2
,
a
1

b
1

a
2

b
2
a_{1}\lor b_{1}\leq a_{2}\lor b_{2},\quad a_{1}\land b_{1}\leq a_{2}\land b_{2}
がともに成り立つ。

このとき、帰納的に、束の任意の空でない有限集合に対して、その結び(上限)および交わり(下限)の存在が示せる。さらに仮定を増やせば、もっといろいろなことが言える場合もある。完備性等を参照。そういった文脈では、上記の定義をもっと別の方法、例えば適当なガロワ接続の存在によって定義することもできる(これは束に対するある種のガロワ理論的な手法である)[要出典]。

有界束 (bounded lattice) は 1 で表される最大元 (greatest element, maximum, top (⊤)) および 0 で表される最小元 (least element, minimum, bottom (⊥)) を持つ束である。任意の束は最大元と最小元を付加することにより有界束とすることができる。また、空でない任意の有限束は有界である(全ての元の結びおよび交わりが最大元及び最小元を与える)。すなわち、A = {a1, …, an} ならば

1=⊤ :=⋁A (=
a
1
∨⋯∨
a
n
), 0=⊥ :=⋀A (=
a
1
∧⋯∧
a
n
){\begin{aligned}1=\top &:=\bigvee A&&(=a_{1}\lor \cdots \lor a_{n}),\\0=\bot &:=\bigwedge A&&(=a_{1}\land \cdots \land a_{n})\end{aligned}}
が成り立つ。

半順序集合が束となる必要十分条件は、任意の有限部分集合(零元集合としての空集合を含む意味で言う)が結びおよび交わりを持つことである。ここで、空集合に関する結びは最小元、空集合に関する交わりは最大元となるものと約束する。



=
0
,


=
1.
\bigvee \varnothing =0,\quad \bigwedge \varnothing =1.
この規約は、結びおよび交わりの結合性および可換性に整合性を持たせるためのものである。すなわち、有限集合の族の和集合の結びはそれらの集合の結びの結びに一致し、双対的に、有限集合の族の和集合の交わりがそれらの集合の交わりの交わりとなる。これは、具体的に束 L の有限部分集合を A, B とすると、


(
A

B
)
=
(

A
)

(

B
)
, ⋀
(
A

B
)
=
(

A
)

(

B
)
{\begin{aligned}\bigvee \left(A\cup B\right)&=\left(\bigvee A\right)\vee \left(\bigvee B\right),\\\bigwedge \left(A\cup B\right)&=\left(\bigwedge A\right)\wedge \left(\bigwedge B\right)\end{aligned}}
がともに成り立つという意味である。ここで B として空集合を取ると


(
A


)
=
(

A
)

(


)
=
(

A
)
∨0=⋁A, ⋀
(
A


)
=
(

A
)

(


)
=
(

A
)
∧1=⋀A{\begin{aligned}\bigvee \left(A\cup \emptyset \right)&=\left(\bigvee A\right)\vee \left(\bigvee \emptyset \right)=\left(\bigvee A\right)\vee 0=\bigvee A,\\\bigwedge \left(A\cup \emptyset \right)&=\left(\bigwedge A\right)\wedge \left(\bigwedge \emptyset \right)=\left(\bigwedge A\right)\wedge 1=\bigwedge A\end{aligned}}
となり、これは A ∪ ∅ = A であるという事実と整合する。

集合 L および L 上の二項演算 ∨, ∧ からなる代数的構造 (L, ∨, ∧) が束であるとは、L の任意の元 a, b, c に対して以下の公理的な恒等式を満足するときに言う。

可換律 結合律 吸収律
a

b
=
b

a
a\lor b=b\lor a
a

(
b

c
)
=
(
a

b
)

c
a\lor (b\lor c)=(a\lor b)\lor c
a

(
a

b
)
=
a
a\lor (a\land b)=a
a

b
=
b

a
a\land b=b\land a
a

(
b

c
)
=
(
a

b
)

c
a\land (b\land c)=(a\land b)\land c
a

(
a

b
)
=
a
a\land (a\lor b)=a
さらに以下の二つの恒等式を公理として仮定することも多いが、実際には吸収律を二度使うことで導くことが可能である[* 1]

冪等律
a

a
=
a
,
a

a
=
a
.
a\lor a=a,\quad a\land a=a.
これらの公理は (L, ∨) および (L, ∧) がともに半束となることを要請するものである。また吸収律は(公理のうちこれだけが条件式に結びと交わりの両方が現れているので)、これによって束が、単にかってな半束の対ということではなく、対となる二つの半束のあいだに適切な相互関係があることを仮定するものとなっている。特に、互いの半束の間に双対性が見て取れる。

代数的な意味での有界束とは代数的構造 (L, ∨, ∧, 1, 0) であって、(L, ∨, ∧) は束であり、(束の最小元となるべき)0 が結び ∨ に関する単位元で、(束の最大元となるべき)1 が交わり ∧ に関する単位元となるものをいう。さらなる詳細は半束の項に譲る。

束はある種の群に似た代数的構造と関連がある。実際、交わりも結びも結合的かつ可換なので、束を台を共有するふたつの可換半群の対と看做すことができる。有界束ならば、この二つの半群は実際には可換モノイドになる。吸収律だけが、束論に特有の定義式である。

可換性と結合性により、結びや交わりを二項ではなく空でない任意の有限集合上の演算として考えることもできる。有界束の場合には、空集合に関する結び(空和)と空集合に関する交わり(空積)をそれぞれ 0 と 1 として定義することができる。このことは、有界束がある意味で一般の束よりも自然であるという見方を与えるものであって、しばしば、単に束といえば有界束のことを意味するという文献があるので注意が必要である。

このような束の代数的な解釈は普遍代数学において本質的な役割を果たす。

以下、いくつか意味のある束のクラスを定めるさまざまに重要な束の性質について述べる。なお、そのうちの一つ、有界性についてはすでに述べてあることを注記する。

半順序集合が完備束 (complete lattice) であるとは、その任意の部分集合が交わりと結びを持つときに言う。特に任意の完備束は有界束である。有限束の準同型は有限な交わりおよび結びしか保存しないが、完備束の準同型では任意濃度の交わりと結びを保つことを要請する。

任意の半順序集合はそれが完備半束であるならば完備束となる。この事実に関する面白い現象として、このクラスの半順序集合に対しては、いくつもの準同型を同時並行的に考えることができるということが挙げられる(つまり、それを完備束とみるか、完備結び半束とみるか、完備交わり半束とみるか、結び完備束とみるか交わり完備束とみるか、それぞれの意味での準同型を考えうる)。

条件付き完備束 (conditionally complete lattice) とは任意の空でない上に有界な部分集合が結び(最小上界)を持つことをいう。このような束は実数全体の集合に対する完備性公理を最も直接に一般化するものである。条件付き完備束は、完備束か、完備束から最大元 1 を除いたものか、完備束から最小元 0 を除いたものか、あるいは完備束から最大元と最小元の両方を取り除いたものかのいずれかである。

応用に際して、分配性条件は強すぎる制約となることがあり、次のようなより弱い性質を考えると便利なことがよくある。束 (L, ∨, ∧) がモジュラー (modular) であるとは L の各元 a, b, c に対して

モジュラー恒等式
(a ∧ c) ∨ (b ∧ c) = [(a ∧ c) ∨ b] ∧ c
が成立するときにいう。この条件は次の条件と同値である。

モジュラー律
a ≤ c ならば a ∨ (b ∧ c) = (a ∨ b) ∧ c.
束がモジュラーである必要十分条件は N5 (右図)と同型な部分束を含まないことである[7][8]。 分配束はモジュラーだが、分配束とは限らないモジュラー束の例として、加群の部分加群全体の成す束や、群の正規部分群全体の成す束が挙げられる。

モジュラー性でも強すぎるときに(上)半モジュラーと呼ばれる次のような性質を課すことがある。 束 L が (上)半モジュラー ((upper)semimodular) であるとは

半モジュラー律
a ∧ b <: a ならば b <: a ∨ b。
が成立するときにいう。ただしここで a <: b とは b が a を被覆する、すなわち a < b であり a < c < b となるような c が存在しないこと。

上半モジュラーの双対概念を下半モジュラーという。 モジュラー束は上及び下半モジュラーだが逆は一般には成立しない。しかし有限束などでは両者は一致する。

半モジュラーの更なる一般化として 弱半モジュラー (weakly semimodular) 又はバーコフ条件と言われる以下の条件がある

バーコフ条件
a ∧ b <: a かつ a ∧ b <: b ならば a <: a ∨ b かつ b <: a ∨ b。
任意の半モジュラー束は弱半モジュラー束である。