情報数学 I − A No.12 補足資料
束（Lattice）
(X,≼)を順序集合とする.
∀x, y∈Xに対して,{x, y}の上限(x∨y)と下限(x∧y)が存在するとき,X を束という.
定理1 集合Xの各要素x, yに２つの演算∨,∧が定義されていて,x∨y, x∧y がX に属すとする.このとき，∀x, y, z∈Xに対して演算∨,∧が
• 結合律： (x∨y)∨z=x∨(y∨z)， (x∧y)∧z=x∧(y∧z)
• 交換律： x∨y=y∨x， x∧y=y∧x
• ベキ等律： x∨x=x， x∧x=x
• 吸収律： x∨(y∧x) = (x∨y)∧x=x を満たすならば，Xは束である.
証明. 各要素x, y∈Xに対して，２項関係≼を x≼y def⇔ x∨y=y と定めるとき,≼が順序関係であり.
x∨y= sup{x, y}, x∧y= inf{x, y}
であることを示そう.ベキ等律より
x≼sup{x, x}=x∨x=x より 反射律 x≼x を得る.
次に，
x≼y かつ y≼x とすると，
x∨y=y かつ y∨x=x となるので，交換律より
x=y∨x=x∨y=y より
反対称律 x≼y かつ y≼x ⇒ x=y を得る.
1
最後に，
x≼y かつ y≼z とすると，
x∨y=y かつ y∨z=z となるので，結合律より
x∨z=x∨(y∨z) = (x∨y)∨z=y∨z=z
すなわち
x∨z=z となるので，推移律
x≼y かつ y≼z ⇒ x≼z
を得る.よって，２項関係≼は順序関係であり，(X,≼)は，順序集合となる. 次に，x∨y= sup{x, y}を示す.まず，結合律より
x∨(x∨y) = (x∨x)∨y となり，ベキ等律より
x∨(x∨y) = (x∨x)∨y=x∨y
となるので，
x≼x∨y を得る.同様に，結合律とベキ等律より
(x∨y)∨y=x∨(y∨y) =x∨y
となるので，
y≼x∨y
を得る. ゆえに，x∨yは{x, y}の上界の元である.ここで，{x, y}の任意の 上界の元をzとすると，
x≼z, y≼z であり，
x∨z=z, y∨z=z である.ゆえに，
(x∨y)∨z=x∨(y∨z) =x∨z=z
となるので
x∨y≼z 2
を得る. zは{x, y}の任意の上界の元であったから，x∨yは{x, y}の最小上 界，すなわち，{x, y}の上限である.よって，
x∨y= sup{x, y}
が成り立つ.次に，x∧y= inf{x, y}を示す.まず，結合律より x∧(x∧y) = (x∧x)∧y
となり，ベキ等律より
x∧(x∧y) = (x∧x)∧y=x∧y
となるので，
x∧y≼x を得る. 同様に，結合律とベキ等律より
(x∧y)∧y=x∧(y∧y) =x∧y
となるので，
x∧y≼y
を得る.ゆえに，x∧yは{x, y}の下界の元である.ここで，{x, y}の任意の 上界の元をuとすると，
u≼x, u≼y であり，
x∧u=u, y∧u=u である. ゆえに，
(x∧y)∧u=x∧(y∧u) =x∧u=u
となるので
u≼x∧y
を得る.uは{x, y}の任意の下界の元であったから，x∧yは{x, y}の最大下 界，すなわち，{x, y}の下限である.よって，
x∧y= inf{x, y}
が成り立つ.
3
