順序集合や束などに関する基本的な概念の説明

by Akihiko Koga
14th Jan. 2018 (Updated)
2nd Jan. 2018 (First)

束論を勉強しようへ戻る
Welcome to AKI's Homepage へ戻る

●このページの趣旨

計算機科学では順序集合に関する理論がいろいろと使われています.半束,束,ガロア接続,完備半順序集合などです.ここでは,それらの基礎理論の学習や応用を学ぶ上で役に立ちそうなことを 書いていきます.まあ,私が勉強したときの覚書みたいなものです.とりあえず, あまり構成を考えずに書いていきますので,ざっと見て,役に立ちそうなことがあれば 読んでみてください.もしかしたら後で少しは構造化するかもしれません.

束論に関しては,ハワイ大学の J.B. Nation さんのレクチャーノートをかなり参照し ましたので,これについては,テキストの在処を書いておきます.


J.B. Nation のホームページ
(ここで "Notes on Lattice Theory" を見つけてください)

注意:このページに書いてあることは,もしかしたら私の勘違いを含んでいるかも しれませんので,あくまで参考にするという目的で,最終的には皆さん自身の 頭で判断してください.

内容


  1. 順序集合の minimum, minimal, maxmum, maxmal について

    これらの概念は非常に重要なので自分で絵に描いたりして,しっかり身につけて ください.二つほど,特殊な場合を絵にしておきます.

    「極大元 (maximal) が1個のとき最大」という記述を見たことがありますが,それは ウソです. 次の poset は唯一の極大元を持つが最大元は持ちません.ただ,有界な順序集合で で極大元が1個ならそれが最大元ですね.
    The following poset have a unique maximal, but no maximum.

  2. その他,順序集合の重要な用語
    次の用語は教科書を読んでよく頭に入れておくこと.思い浮かべたり,絵に描いたり, 何となく口ずさんでみたり,歌に歌ったりして, あなたの自宅から最寄りの駅に いくまでの道筋くらい に親しんでください.

    partial order, power set of a set X (P(X)),

    chain, anti-chain, covered by, Hasse diagram,

    order preserving map, isomorphic to,

    ideal (order ideal), the set of all order ideals O(P),

    dual concepts, dual poset Pd, filter (order filter),

    maximum, maximal, minimum, minimal,
    (上で書きましたが重要なのでもう一度書きました)

    DCC : descending chain condition,
    ACC : ascending chain condition,

    well-ordering,

  3. Zorn の補題


    図. Zorn の補題
    順序集合での極大元の存在に関する重要な命題である Zorn の補題について解説を Zorn の補題と選択公理のお話に書きました. これは少し長いです.参考文献として比較的短い証明が載っているものも あげました(ここで何度も紹介している J.B. Nation さんの束論の 教科書の付録なんですけどね).

  4. 束の定義について

    束(lattice)の定義は次のようないくつかの公理からなっていると思う.

    これを初めて見た学習者は,なんだかゴチャっとした公理があって,何を言っているのか 分かりにくいと思う.

    これは次の図のようなことを言っている.

    まず,(1) - (3) は ∧ と ∨ が それぞれ順序 ≤ と ≥ を定義し,それぞれが 半束 (semilattice) であることを言っている. (4) は,Absorption law と呼ばれ,上のようにして定義した二つの順序 ≤ と ≥ が同じ順序であることを言っている.つまり, (4) の条件の元には

    (4')     x ≤ y <=> x ≥ y

    であるし,その逆に(4') が成り立てば,(4) が成り立つことが証明できる. (1)-(3) と (4) をまとめると,一つの順序 ≤ (つまり, ≥ ) について,x と y の上限と下限があることを言っている訳である.

    ちなみに,<L, ∧> が半束である条件は次のような名前がついている.

    1. x ∧ x = x (Idempotency 冪等性)
    2. x ∧ y = y ∧ x (Commutativity 可換性)
    3. x ∧ (y ∧ z) = ( x ∧ y) ∧ z (Associativity 結合性)

    3 の結合性は群論などで良く知られているだろう.二項演算が定義されている 集合は,これが成立すれば半群 (semigroup) と呼ばれる.

    1 の冪等性はあまり面白くない性質のように思うかもしれないが重要な性質で, 半群や位相空間の理論で大活躍する性質である.例えば,群やモノイドの単位元 e は この性質

    e・e = e
    を持つ代表的な元である.半群論では,部分に限れば群構造を 持つ部分を見つけることができる場合があり,そのときの単位元の候補でもある.

    2 の可換性もよく使う性質で,群論の基礎を勉強した学習者はアーベル群の定義などで 馴染みのある性質だと思う.この性質があると代数系の構造がかなり簡単になる.例えば, 有限生成のアーベル群は巡回群の直積に分解できることは良く知られている.

    条件 1 の冪等性 (idempotency) と条件3の結合性 (associativity) を併せて持つ代数系を帯 (band) と言うので, 半束 (semilattice) は可換帯 (commutative band)である.

  5. Modular 束との親しみ方(1)

    Modular 束は,

    a ≥ c ならば a ∧ (b ∨ c) = (a ∧ b) ∨ c for ∀ a, b, c ∈ L
        または
    a ≤ c ならば a ∨ (b ∧ c) = (a ∨ b) ∧ c for ∀ a, b, c ∈ L
    が成立する束です.Modular 束は, 束論の初学者には分かりにくい概念ではないでしょうか. だいたい,何に使えるか分からないし,形も不等式の条件が付いていて変だし.

    これが何に使えるかは,私も良く知りません.なんでも Dedekind が束論の前身を考えているとき アーベル群の部分群がなす束の性質として認識していたというような由緒正しい 性質だそうですが.

    で,ここでは少しでもこの式の形に慣れる方法を考えます.

    上の2つの等式は双対(dual) で,一方から一方が言えますので,上の方だけにして, さらに,任意の束で成立する

    a ≥ c ならば a ∧ (b ∨ c) ≥ (a ∧ b) ∨ c for ∀ a, b, c ∈ L
    を考えます.この不等式はどんな束でも成立するもので,Modular 束は,この不等式に おいて常に等号が成立することを保証するものです.

    この式をいつでも書き下せるように練習することを考えます.

    Modular 不等式は Distributive 不等式の特別な形ですから,まず,

    a ∧ (b ∨ c) とそれを展開した式 (a ∧ b) ∨ (a ∧ c)
    を頭に思い浮かべます.そしてじっと見つめて,この二つのどちらが大きいかを 考えます.

    左辺の a は右辺の (a ∧ b) と (a ∧ c) 以上であり,また, 左辺の (b ∨ c) も 右辺の (a ∧ b) と (a ∧ c) 以上な訳ですから, ∧ をとっても それら以上となり,不等号は ≥ となります.これで次の Distributive 不等式が得られます.

    a ∧ (b ∨ c) (a ∧ b) ∨ (a ∧ c)
    あとは,この式の右端の (a ∧ c) を c にすることを考えます.a ∧ c = c は a ≥ c と同値ですから,その条件を前につけて,Modular 不等式
    a ≥ c ならば a ∧ (b ∨ c) ≥ (a ∧ b) ∨ c for ∀ a, b, c ∈ L
    を得ます.こうやってよく見ると,文字や演算子は変わらないのに,括弧の位置が変わるだけで大きさが変わる面白い不等式です.

    このようにして,まず Modular 不等式に慣れ親しんで,いつでもこの式を展開 できるようにしておくと,束論の本で Modular 束の章を読むのは多少楽になるのでは ないかと思います.何に使えるかはまた別のところで学ぶことにして.

    ここで述べたことを,ステレオグラムを使って立体に可視化したものを

    半順序集合に関する可視化の実験
    に載せておきます.

  6. Modular 束との親しみ方(2)ペンタゴンとダイヤモンド

    束 L が, Modular であるための必要十分条件は,次のようなペンタゴン(5角形) が L の部分束として存在しないことというのはどの教科書に説明されていると思います.

    定理(Modular 束となるための必要十分条件)

    束 L が, Modular であるための必要十分条件は,次のようなペンタゴン(5角形) が L の部分束として存在しないことである.

    (ここでの条件は,ペンタゴンが部分束として存在しないことであることに 注意しておいてください.そくの中の大小関係を結んでペンタゴンがあっても, 束の演算 ∨ と ∧ に関してペンタゴンが形成されなければ OK です.)

    また,Modular 束 L では任意の a, b ∈ L に対して,区間 [a, a ∨ b] と 区間 [a ∧ b, b] は,写像 x -> x ∧ b と y -> y ∨ a で同型になります.これはダイヤモンド定理と呼ばれます.

    ダイヤモンド定理

    束 L が Modular とするとき,
    区間[a, a ∨ b] と 区間 [a ∧ b, b] は,
    写像 x -> x ∧ b と y -> y ∨ a で
    同型となる.

    図で赤い線同士が同型となるということですね. 当然,青い線同士も同型となります. あと,この図では線で書いていますが,束では一般に区間 [u, v] は 全順序(チェイン)になるとは限らない ことに注意してください.当然 Modular 束ででも同様です.

    ペンタゴンが無いというのは Modular 束になる必要十分条件ですが,ダイヤモンド定理の 区間[a, a ∨ b] と 区間 [a ∧ b, b] が同型というのも Modular 束になるための 必要十分条件です.それを確信するには,

    ペンタゴンがない <=> 区間[a, a ∨ b] と 区間 [a ∧ b, b] が同型
    を言えば良い訳です.=> はダイヤモンド定理の内容自身ですから,<= を言えば完了です.それには対偶をとって,ペンタゴンがあれば,区間[a, a ∨ b] と 区間 [a ∧ b, b] が同型に ならないことを言えば良い訳です.a = β, b = γ ととれば,同型にならない場合が作れますから,結局,この2つの条件は同値だということがわかります.上の同型が成り立つのが Modular 束だと言われると,Modular 束が何に使えるのか分からなくとも, 「これはなにか有難い束だ」という気がしてきます.

    そういえば,最近,ペンタゴンの図として五角形らしい五角形でなく,下の図のような,ひし形に近い五角形を 使うのをよく見ているような気がします.δに対応する要素が区間 [β, α] の中に無いという図ですね.

  7. J.B. Nation Notes on the Lattice Theory 第1章 Dilworth の定理の証明 (有限の場合)
    J. B. Nation Notes on the Lattice Theory の 該当箇所を 勉強するときに必要なら参照してください.

    一応,Dilworth の定理も書いておきます.

    Dilworth の定理
    順序集合 P において,w(P)が有限なら,w(P) = c(P)
    ここで,w(P) は P の中の最大の anti-chain の要素の数,c(P) はP を chain で 覆うときの最小の chain 数とする.

    順序集合 P に対して w(P) と c(P) を図示しておきます.

    chain covering number and width of a poset

    以下は,J.B. Nation の第1章での Dilworth の定理の証明を理解するための 補助に書いた図です.

    (次の図で Case2 がどんな時かは,図の後の注意を参照)
    chain covering number and width of a poset

    注意)maximal chain を取り去っても width が減らない例

    width 個の chains で覆うには,改めて,chain を取り直さないといけない. この取り方は,定理の証明方法と同じ.

  8. Join irreducible

    Join irreducible という概念は,有限個の join に表すことができない要素と いうことで,定義に否定を含んでいて,また,ほかに無限個の join で表すことが できないという completely join irreducible という概念も出てくるので, 結構,混乱しやすい.しかし,これは束を表現するためにとても重要な概念である. ここでは,定義を絵にしたりしながら,しっかりとこの概念を身につけていきたいと 思う.

    まず,x ∈ P が join irreducible であるというのは,これが x とは異なる 要素 a, b ∈ L の join として表されないことである.つまり,

    x = a ∨ b => x = a or x = b
    が成立すること.ただし,最小元 0 は,join irreducible な元には含めません( 含める流儀もあるようですがここでは 0 は含めません).join irreducible の定義は, 「表されない」と表現が否定形になっているので分かりにくいですね. 表されるとき join reducible と考えて,そうでないときと思ったら良いかもしれません. ここでは二つの元の join としましたが,これは「有限個」と言い換えても同じです. join irreducible でないときは,x は,複数の要素の join で表されている訳ですが, この表し方は下の2つの図に示すように一意ではありません.

    つまり,この例では x は次の図のようにも表すことができます.

    だいたいにおいて join irreducible な要素は次の図のように直下の要素を一つだけ持つ要素です.

    次の例の ω も join irreducible です.もともと w は自分自身と異なる有限個の要素の join で表せません.しかし,無限個の要素の join にはなっているので,completely join irreducible ではありません (無限個の join になっているとき,必ず自分自身がその中に含まれていなければならないとき completely join irreducible といいます).

    次の ω' は join irreducible ではありません.無限個の要素を使わなくとも a ともう一つ何か 自然数 n を選べば ω' = a ∨ n になるからです.

    まあ,ここらあたりの絵を参考にしながら,しっかり join irreducible の概念を身につけてください.これは束の表現をするときにとても重要な概念になります.

  9. 順序集合 (Poset) や束 (Lattice) の表現

    /* ***** TO DO *****

    */

  10. Closure rules in J.B. Nation's Textbook

    J.B. Nation の Notes on the Lattice Theory に Closure operator と 同等の概念として導入されている.私は他のテキストでは見たことがないような気が する (J.B. Nation 氏は,「今では普通の手法になった」と言われているが).

    便利なのだが私は分かりにくかったので解説を書いた.私と同様に分かりにくい人は

    J.B. Nation の Notes on Lattice Theory への要望
    第二の要望 (Closure rules について)
    を参照していただきたい.

  11. J.B. Nation Notes on the Lattice Theory の第3章 Algebraic Latticesの概要
    J. B. Nation Notes on the Lattice Theory の 該当箇所を 勉強するときに必要なら参照してください.

    第3章で書いてあることをまとめると次の図のようになります.

    ここでは,ある特殊な種類の束の構造を学びます.それは代数の部分代数の族がなす束です. 特殊と言っても,結構よく現れます.なんせ,代数の部分代数の族ですから,代数が現れるところには現れる訳です.これが図の一番上の四角の中に書いてあることです.

    次の四角の中は,代数的束 (Algebraic lattice) という束を定義するところを書いています. 代数的な束とはコンパクトな要素の集合がその束 L の中で join dense になっているという条件で 定義されます.この部分の四角の右側では,代数的閉包演算 (algebraic closure operator) という閉包演算および,その閉包演算により閉集合の族を定義し,それが先に定義した代数的束と 同等の概念だということを証明します.

    次の四角は,代数的束の性質を記述するための概念をいくつか定義しています.

    最後の四角は,そのようにして定義された諸概念で代数的束の性質を述べています.

    compact in lattice and topological space

    一応,束の要素がコンパクトであることのイメージと位相空間の意味のコンパクトの対比も書いておきます.その要素がコンパクトとは,それが無限個の要素のジョインに押さえられていたら,その中から有限個の要素を選んで,そのジョインで元の要素を押さえることができるということです.位相空間では,コンパクトという概念は,ある集合が無限個の開集合のユニオンで覆われていたら,その中から有限個の開集合を選んでそれらのユニオンで覆うことができるということですから,うまく対応していますね.

    compact in lattice and topological space

Let's Study Lattice Theory (Japanese)

Top of My Homepage (Japanese)