クロロの数学ブログ

自然現象の背後にある数学を勉強します。

束の定義:代数学的定義と順序理論的定義の等価性

束の定義

以下の等式をみたす二つの二項演算 {\displaystyle \lor}, {\displaystyle \land}を備えた集合 {\displaystyle L} のことを束(lattice)といいます1

  • 可換律
    • {\displaystyle x \lor y \approx y \lor x }
    • {\displaystyle x \land y \approx y \land x}
  • 結合律
    • {\displaystyle x \lor ( y \lor z ) \approx ( x \lor y ) \lor z}
    • {\displaystyle x \land ( y \land z ) \approx ( x \land y ) \land z}
  • 冪等律
    • {\displaystyle x \lor x \approx x}
    • {\displaystyle x \land x \approx x}
  • 吸収律
    • {\displaystyle x \approx x \lor ( x \land y)}
    • {\displaystyle x \approx x \land ( x \lor y)}

例えば、{\displaystyle x}{\displaystyle y} を論理式だと思えば、これは高校数学でも習った命題論理の性質です。また、{\displaystyle L = \mathbb{N}} として、{\displaystyle x \lor y} は最小公倍数、{\displaystyle x \land y} は最大公約数をとる演算だと思えば、自然数の集合 {\displaystyle \mathbb{N}} も自然に束とみなせます。

この記事内では、ここでの束の定義を代数学的な定義と呼ぶことにします。

半順序の定義

集合 {\displaystyle A} 上の二項関係 {\displaystyle \leq} が以下の性質をみたすとき、半順序(partial order)と呼ばれます。:

  • 反射律
    • {\displaystyle a \leq a}
  • 反対称律
    • {\displaystyle a \leq b} かつ {\displaystyle b \leq a} ならば {\displaystyle a = b}
  • 推移律
    • {\displaystyle a \leq b} かつ {\displaystyle b \leq c} ならば {\displaystyle a \leq c}

半順序の定められた集合のことを半順序集合(partially ordered set、略してposet)と呼びます。さらに、半順序集合 {\displaystyle A}において、任意の元 {\displaystyle a}{\displaystyle b} に対して {\displaystyle a \leq b}{\displaystyle b \leq a} の少なくとも一方が成り立つとき、{\displaystyle \leq} は特に全順序(total order)と呼ばれます。このとき、{\displaystyle A} は全順序集合(totally ordered set、linearly ordered set、chain)と呼ばれます。

例えば、集合 {\displaystyle A} の冪集合 {\displaystyle \mathrm{Su}(A)} に対して、包含関係 {\displaystyle \subseteq}{\displaystyle \leq} とみなせば、半順序の性質をみたします。また、自然数の集合 {\displaystyle \mathbb{N}} に対して、「 {\displaystyle a}{\displaystyle b} を割る」という関係を {\displaystyle \leq} とみなせば、これも半順序になります。

以下、ある性質をみたす半順序集合は実は束とみなせることを示していきます。この「ある性質」について述べるため、 さらに言葉の定義をしていきます。

上界、上限、下界、下限の定義

半順序集合 {\displaystyle P} の部分集合 {\displaystyle A} を考えます。

{\displaystyle P} の元 {\displaystyle p \in P}{\displaystyle A}上界(upper bound)であるとは、{\displaystyle A} の任意の元 {\displaystyle a \in A} に対して、{\displaystyle a \leq p} が成り立つことです。また、上界の中で「最小」のものを最小上界といいます。論理的に正確に述べると、{\displaystyle b \in P}, {\displaystyle p \in P} としたとき、「任意の {\displaystyle a \in A} に対して、 {\displaystyle a \leq b} ならば {\displaystyle p \leq b} 」が成り立つ2とき、{\displaystyle p \in P}{\displaystyle A}最小上界(least upper bound または l.u.b. of A)または上限(supremum of A)であるといい、{\displaystyle \sup (A)} と書きます。

下界については、上界の「逆」に定義します。すなわち、任意の {\displaystyle a \in A} に対して、{\displaystyle p \leq a} が成り立つとき、{\displaystyle p \in P}{\displaystyle A}下界(lower bound)といい、下界の中で最大3のものを{\displaystyle A}最大下界(greatest lower bound)または下限(infimum)といい、{\displaystyle \inf (A)}と表します4

束の代数学的定義と順序理論的定義の等価性

半順序集合 {\displaystyle L} を考えます。{\displaystyle L} の任意の二つの元 {\displaystyle a}, {\displaystyle b} に対して、{\displaystyle \sup \{a, b\} }{\displaystyle \inf \{a, b\} } が存在するとき、 {\displaystyle L} は束とみなすことができます。このような半順序集合も一般に束と呼びますが、はじめのうちは少しややこしいです。ここでの束の定義(任意の二元が上限と下限をもつような半順序集合のこと)を、この記事内では順序理論的な定義と呼ぶことにします。

それぞれ独立して自然に定義されている代数学的な定義と順序理論的な定義が、実は等価であることを示していきます。

束が代数学的に定義されているとき

{\displaystyle L}代数学的に定義されているとき、{\displaystyle L} 上の二項関係 {\displaystyle a \leq b} を、{\displaystyle a = a \land b} によって定めれば、この二項関係は半順序の公理をみたし、さらに順序理論的な定義(任意の二元が上限と下限をもつ)もみたします。

このことを示すために、この二項関係 {\displaystyle \leq} が実際に半順序の公理をみたすかどうかを確認し、任意の二元に対して上限と下限が存在するかを調べます。

  1. 反射律 {\displaystyle a \leq a} の証明:
    代数学的定義では冪等律 {\displaystyle a = a \land a} が成り立ち、これは順序理論的定義 {\displaystyle a \leq a} であることと同値です。

  2. 反対称律 {\displaystyle a \leq b} かつ {\displaystyle b \leq a} ならば {\displaystyle a = b} の証明:
    {\displaystyle a \leq b} のとき代数学的には {\displaystyle a = a \land b} であり、 {\displaystyle b \leq a} のときは代数学的には {\displaystyle b = b \land a} であるため、代数学的定義での可換律と合わせると {\displaystyle a = a \land b = b \land a = b} であることがわかります。

  3. 推移律 {\displaystyle a \leq b} かつ {\displaystyle b \leq c} ならば {\displaystyle a \leq c} の証明:
    {\displaystyle a \leq b}{\displaystyle a = a \land b} で、{\displaystyle b \leq c}{\displaystyle b = b \land c} であるため、代数学的定義での結合律と合わせて、{\displaystyle a = a \land b = a \land ( b \land c ) = ( a \land b ) \land c = a \land c} をえることができます。この {\displaystyle a = a \land c} は順序理論的定義では {\displaystyle a \leq c} です。

  4. 任意の二元に対して上限と下限が存在することの証明:
    {\displaystyle L} の任意の二元 {\displaystyle a}, {\displaystyle b} に対して、{\displaystyle \sup \{a, b\} = a \lor b} で、{\displaystyle \inf \{a, b\} = a \land b} となります。上限に関して示します。下限の場合は、上限の場合において、{\displaystyle \leq} の向きを逆にして、 {\displaystyle \lor}{\displaystyle \land } を入れ替えるだけで示すことができます。

    まず、代数学的定義での冪等律より、{\displaystyle a = a \land (a \lor b)} ですが、これを順序理論的定義にすると {\displaystyle a \leq (a \lor b)} であるため、上界であることがわかります。次に、{\displaystyle c}{\displaystyle \{ a, b \}} の上界だとすると、{\displaystyle a \leq c}, {\displaystyle b \leq c} ですが、これらを代数学的定義に書き換えると {\displaystyle a = a \land c}, {\displaystyle b = b \land c} となります。このとき吸収律から、{\displaystyle a \lor c = ( a \land c) \lor c = c}, {\displaystyle b \lor c = ( b \land c) \lor c = c} をえます。これと可換律から、{\displaystyle c = (c \lor c) = (a\lor c) \lor (b\lor c) = (a \lor b) \lor (c \lor c) = (a \lor b) \lor c} です。さらに吸収律を用いて、{\displaystyle (a \lor b) \land c = (a \lor b) \land (( a\lor b) \lor c) = a \lor b} がえられます。これを順序理論的定義に書き換えると、 {\displaystyle a \lor b \leq c} となります。これは、上界の中で {\displaystyle a \lor b} が最小であることを意味します。

したがって、束が代数学的に定義されているとき、自然に順序理論的な定義をみたすような二項関係 {\displaystyle \leq} がえられました。

束が順序理論的に定義されているとき

{\displaystyle L} が順序理論的に定義されているとき、{\displaystyle L} 上の二項演算を {\displaystyle a \lor b = \sup \{a, b\} }{\displaystyle a \land b = \inf \{a, b\} } と定めれば、これらは代数学的な束の公理をみたします。

このことを示すために、これらの二項演算が実際に代数学的に定義された束の公理をみたすかどうかを確認します。

  1. 可換律 {\displaystyle a \lor b = b \lor a} の証明:
    {\displaystyle a \lor b =  \sup \{ a, b \} = \sup \{ b, a \} = b \lor a } です。下限についても同様です。

  2. 結合律 {\displaystyle a \lor ( b \lor c) = ( a \lor b) \lor c}{\displaystyle a \land ( b \land c) = ( a \land b) \land c} の証明:
    {\displaystyle \sup \{ a, \sup \{ b, c \} \} = \sup \{ a, b, c \} } を示します。まず、上界性から{\displaystyle a \leq \sup \{ a, \sup \{ b, c \} \} } かつ {\displaystyle \sup \{ b, c \}  \leq \sup \{ a, \sup \{ b, c \} \} } であることと、{\displaystyle b \leq \sup \{ b, c \} } かつ {\displaystyle c \leq \sup \{ b, c \} } であることから、{\displaystyle \sup \{ a, \sup \{ b, c \} \} }{\displaystyle \{ a, b, c \} } の上界であることがわかります。{\displaystyle \sup \{ a, b, c \} } が最小上界であることから、{\displaystyle \sup \{ a, b, c \} \leq \sup \{ a, \sup \{ b, c \} \} } です。また、{\displaystyle b \leq \sup \{ a, b, c \} }{\displaystyle c \leq \sup \{ a, b, c \} }、最小上界性から {\displaystyle \sup \{ b, c \} \leq \sup \{ a, b, c \} } であり、さらに {\displaystyle a \leq \sup \{a, b, c \} } であることから、{\displaystyle \sup \{ a, \sup \{ b, c \} \} \leq \sup \{ a, b, c \} } です。これらと、反対称律から {\displaystyle \sup \{ a, \sup \{ b, c \} \} = \sup \{ a, b, c \} } です。同様にして、{\displaystyle \sup \{\sup \{ a, b \}, c \} = \sup \{ a, b, c \} } なので、 {\displaystyle \sup \{ a, \sup \{ b, c \} \} = \sup \{\sup \{ a, b \}, c \} } がえられます。

    このことに注意すると、 {\displaystyle a \lor ( b \lor c) = \sup \{ a, \sup \{ b, c \} \} = \sup \{\sup \{ a, b \}, c \} = ( a \lor b) \lor c} がわかります。 {\displaystyle a \land ( b \land c) = ( a \land b) \land c} の場合も、下限の性質を用いて同様に示すことができます。

  3. 冪等律 {\displaystyle a \lor a = a}{\displaystyle a \land a = a } の証明:
    反射律 {\displaystyle a \leq a } より {\displaystyle a }{\displaystyle \{ a, a\} } の上界であり、{\displaystyle a \leq b} はそのまま最小上界であることを意味するので、{\displaystyle \sup \{a, a \} = a }、すなわち {\displaystyle a \lor a = a } であることがわかります。{\displaystyle a \land a = a } の場合も同様にして示せます。

  4. 吸収律 {\displaystyle a = a \lor ( a \land b )}{\displaystyle a = a \land (a \lor b)} の証明:
    上限の性質から{\displaystyle a \leq \sup \{ a, \inf \{ a, b \} \} } です。また、下限の性質から、{\displaystyle \inf \{ a, b \} \leq a} なので、{\displaystyle a \leq a} と合わせると、{\displaystyle a}{\displaystyle \{a, \inf \{ a, b \} \} } の上界であることがわかります。したがって、最小上界性から {\displaystyle \sup \{ a, \inf \{ a, b \} \} \leq a } です。これらから、{\displaystyle a = \sup \{ a, \inf \{ a, b \} \} = a \lor (a \land b)} です。{\displaystyle a = a \land (a \lor b)} も同様にして示せます。

こうして、順序理論的に定義した束は、自然と代数学的な定義もみたすようにできることが示されました。

まとめ

以上のように、束の代数学的な定義と順序理論的な定義は同一視できることが示されました。状況に応じて、束の代数学的性質と半順序集合としての性質を使い分けることができます。

次回は、今回定義した束の同型性と部分束について解説します。今回の代数学的定義と順序理論的定義から推測できるように、代数学的に定義された二つの束が同型であるということは、これらの束を半順序集合として見ると、二つの束の間に順序を保つ全単射が存在することであることが示されます。

その後の記事では、完備束・同値類・代数束の説明をしたあと、閉包作用素の導入をします。束は普遍代数学の基礎となると同時に、普遍代数の一例でもあるので、丁寧に解説していきたいと思います。今回はここまで。

2017/07/02 追記

束の二つの定義の同値性は、例としてある集合の冪集合のなす束を考えると明らかです。

{\displaystyle A \leq B}{\displaystyle A \subseteq B}と定めると、ベン図を用いて

f:id:eternalletter:20170702135736p:plain:w200

と図示できます。これは、{\displaystyle A = A \cup B} であることと同値です。このように、包含関係を順序関係だとみなせば、冪集合は半順序集合です。

下図のようになっていると、{\displaystyle A \subseteq B} でも {\displaystyle A = A \cup B}でもありません:

f:id:eternalletter:20170702135753p:plain:w250

このとき、順序関係は定まりませんが、実は {\displaystyle \sup \{A, B\} = A \cup B}{\displaystyle \inf \{A, B\} = A \cap B} となるので、束となります:

f:id:eternalletter:20170702135801p:plain:w250

実際、{\displaystyle A  \subseteq C}{\displaystyle B \subseteq C} とすると、{\displaystyle A \cup B \subseteq C}(最小上界性)であり、{\displaystyle D \subseteq A}{\displaystyle D \subseteq B} とすると、{\displaystyle D \subseteq A \cap B}(最大下界性)です:

f:id:eternalletter:20170702135805p:plain:w250

参考文献

S. Burris and H.P. Sankappanavar, A Course in Universal Algebra. The Millenium Edition, 2012.


  1. ここで、{\displaystyle \approx}という記号は、等式を表します。等式ですので、成り立つこともあれば成り立たないこともあります。{\displaystyle =}という記号は、両辺が全く同じ対象であることを表します。等式が成り立つということと同じ対象であるということは似て非なる概念ですが、腑に落ちなければ当面はあまり違いを気にしないでよいです。この記事でも、あまり違いを気にせず書いています。

  2. 任意の{\displaystyle a \in A} に対して {\displaystyle a \leq b} ということは、{\displaystyle b}{\displaystyle A} の上界ということであり、{\displaystyle A} の上界 {\displaystyle b} に対していつでも {\displaystyle p \leq b} であるということは、上界の中で{\displaystyle p}が最小ということを意味します。

  3. 任意の{\displaystyle a \in A} に対して、{\displaystyle b \leq a} ならば {\displaystyle b \leq p} が成り立つとき、{\displaystyle p} は 下界の中で最大のものとみなせます。

  4. 実数の連続性と同値な命題「上限性質」は、実数を全順序集合とみなしたときに、ここで定義した言葉で述べられます。上限性質とは、「実数の空でない部分集合は、上に有界であれば上限が存在する」でした。実は、上限性質をみたす束は、条件付き完備束(conditionally complete lattice)と呼ばれます。