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

by Akihiko Koga
16th Mar. 2021 (Updated)
2nd Jan. 2018 (First)

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

●このページの趣旨

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

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


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

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

少し再構成を始めました.このページは,もともと,J.B. Nation 教授の束論の教科書を読むのに, 気を付けることを散発的に書いていたのですが,今, 前半部分に順序集合や束論の基礎をかなりの分量補充していっています.
2021.02.20

内容


  1. 順序集合の定義など

    順序集合の基本概念についてある程度の数の解説を加え,再構成しました.

    2021.02.11

    全体の目次に戻る

  2. さらに,順序集合の例
    もう少し,色々な順序集合の例を見ていきましょう.

    全体の目次に戻る

  3. 整列集合(well-ordered set)

    順序集合 (W, ≤) が整列集合(well-ordered set)というのは その任意の部分集合に最小元が存在するような順序集合です.論理式で書けば,

    ∀D⊆W ∃ min(D)∈D⊆W

    ということです. 整列集合 W に対しては,x, y∈W のときは {x, y}⊆W ですから,最小元があります.x か y のどちらかが最小元になる訳 ですね.したがって,整列集合では 任意の2元が比較可能ということになり,必然的に全順序集合になります.

    整列集合は数学的帰納法(超限帰納法)の基礎となる集合で重要です.さらに詳しい説明は 集合論のページに ありますので,ご存じない人は勉強しておいて下さい.ただし,このページの 内容を読むためには必須ではありません.

    全体の目次に戻る

  4. Zorn の補題


    図. Zorn の補題

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

    ただし,このページを読むのに,Zorn の補題はそれほどは必要なく, ざっとどんな補題で何に使えるのかを知って入れば当面は問題ないと 思います.

    全体の目次に戻る

  5. 順序集合としての半束と束

    束やその条件を少し緩めた半束は,順序集合としても,代数系としても特徴づけることができます. ここではまず,順序集合として特徴づけて,この項目の最後で半束の代数系としての 特徴づけ,次の項目で束の代数系として特徴づけを紹介します.順序集合としての 特徴づけと代数系としての特徴づけは同値になります.

    束を定義するのにまず,その約半分の公理を満たす半束(semilattice)を定義します. 半束は上への半束と下への半束があります.それら両方を満たすのが束(lattice)です. ここでは,このようにして束を定義した後,そのような束で極限操作について特に 良い性質を持っている完備束(complete lattice)について定義しておきます.

    この項目の内容


    2021.02.16
    全体の目次に戻る

  6. 代数系としての束の定義について

    束(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)である.

    全体の目次に戻る

  7. Knaster-Tarski の不動点定理
    上で束や完備束が定義されたので,完備束についての不動点に関する重要な定理を書いておきます.

    Knaster-Tarski の不動点定理

    (L, ≤) を完備束,f : L → L を順序保存写像とするとき, L には f の不動点,つまり, f(x) = x となる元 x が存在する.

    さらに,それらの不動点のうち,最大不動点と最小不動点は次の式で与えられる.

    最大不動点

    ∨ {x∈L | x≤f(x)}

    最小不動点

    ∧ {x∈L | f(x)≤x}

    [証明]
    まず,u := ∧ {x∈L | f(x)≤x} として,u が不動点であることを証明する.

    任意の x∈{x∈L | f(x)≤x} に対して,u≤xであり,f は順序を保つので,

    f(u)≤f(x)≤x

    となり,f(u) は{x∈L | f(x)≤x}の下界の1つである.u はそのような下界の中の 最大元であるから

    f(u)≤u ........ (1)

    f は順序を保つので

    f(f(u))≤f(u)

    となり,

    f(u)∈{x∈L | f(x)≤x}

    u はこの右辺の下限であり,したがって下界でもあるから,

    u≤f(u) ........ (2)

    (1) と (2) から u=f(u) となり,u は f の不動点になる.

    次に u が最小不動点であることを示す.f の不動点の集合を Fix(f) とすると,

    Fix(f)⊆{x∈L | f(x)≤x}

    したがって,u は Fix(f) の下界でもあり,最小元となる.

    次に,∨ {x∈L | x≤f(x)} が f の最大不動点であることで あるが,これは 上の議論の上下を逆さまにすれば分かる.

    [証明終]

    この定理から,完備束 (L, ≤) では順序を保つ関数 f : L → L に対して, 必ず,不動点,つまり f(x) = x となる x があることが分かります.それは, {x∈L | x ≤ f(x)} の上限をとったりすることで見つかるはずですが, 無限個の要素を持つ領域ではなかなかこれはできません.もう少し簡単に

    ⊥ f(⊥), f(f(⊥)), f(f(f(⊥))), ..., fn(⊥), ...

    と言った具合に段々近似していくというアイデアもあると思います.残念ながら, これが常に可能とは限りません.しかし,順序集合に色々条件を付ければこの方法も 可能になります. 実際,計算機科学では,このような近似が可能な順序集合を使って,プログラムの 意味を段々近似していって定めるというような研究もあります.

  8. その他の重要な順序集合
    この項目の内容
    全体の目次に戻る

  9. 順序集合の完備化

    ここでは順序集合を完備束に埋め込む方法を見ていきます.例えば,有理数の集合 (Q, ≤) は,A = {x∈Q | x2≤2} は Q の中に上限を持ちませんが,Q を含む実数の集合 R は,そのなかに A の上限 √ 2 を持ちます.その結果,R の中では,Q の中だけでは展開できなかった,極限に関する 色々な理論の構築が可能になります注).ここでは,このような,順序集合からそれを含む完備な 束をシステマティックに構成する方法を見ていきます.

    注)正確には実数の集合Rは順序集合としては完備ではなく,Rに最小元と 最大元を加える必要があります.最大元を∞,最小元を-∞とすれば, R ∪ {-∞, ∞} が完備順序集合になります.
    以下の項目へのリンク

  10. ガロア接続 (Galois Connection)

    2021.03.06 -
    この項目の内容

    全体の目次に戻る

  11. ブール代数 (Boolean algebras)

    計算機科学を先行している方は, {0, 1} の二値のブール代数には馴染みが深いと 思いますが,ブール代数としては,多くの値を持つ,より一般の代数の一群があります. 簡単に言うと,ブール代数とは,最小元と最大元がある分配束で,各元に補元と呼ばれる 論理学の否定相当の元が存在するような束を指します.

    このページが大きくなり過ぎたなどの理由から,ブール代数については 別ページ

    ブール代数(Boolean algebras)
    にまとめました.ご興味のある方は,そちらを参照してください.

    全体の目次に戻る

  12. 超フィルター (Ultrafilter)

    フィルターのうち,極大なものを超フィルター(Ultrafilter)と言います. これは,例えば,実数の集合を無限小のようなものを入れて拡張する超準解析 などで使われたり,ちょっと意外な使われ方をします.この項目では超フィルターの そういった側面を説明していきたいと思います.

    このページが大きくなり過ぎたなどの理由から,超フィルターについては 別ページ

    超フィルター(Ultrafilter)
    にまとめました.ご興味のある方は,そちらを参照してください.

    全体の目次に戻る

  13. ハイティング代数 (Heyting algebras)

    ハイティング代数は,束の一種ですが,直観主義論理のモデルに使われるなどの 用途があります.上で述べたブール代数もハイティング代数の一種ですが,ハイティング 代数の中には,ブール代数よりも「弱い」代数があり,これらは,排中律 p ∨ ¬p が必ずしも成立しない論理のモデルとして使うことができます. ここでは,このような論理学との繋がりまでは解説できないと思いますが,ハイティング代数についての基本的な事柄を説明します.

    このページが大きくなり過ぎたなどの理由から,ハイティング代数については 別ページ

    ハイティング代数(Heyting algebras)
    にまとめました.ご興味のある方は,そちらを参照してください.

    全体の目次に戻る

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

    ここと次の項目は,Modular 束への親しみ方について書いています. 特に,Modular 束がどんな意味があるかや何に使えるかではなく,一見奇異に見える 定義に少しでも慣れれば良いというくらいの位置づけです.今のところ,他の項目とは あまり関係がないかと思います.Modular 束を束論の教科書などで勉強するとき, とっつきにくいなと感じた方がいらっしゃったら,読んでみるとよいかもしれません.

    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 束の章を読むのは多少楽になるのでは ないかと思います.何に使えるかはまた別のところで学ぶことにして.

    ところで,上の図は慣れたら次の図でも良いかもしれませんね.

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

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

    全体の目次に戻る

  15. 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 束が何に使えるのか分からなくとも, 「これはなにか有難い束だ」という気がしてきます.

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

    このペンタゴンについても立体視の図がありますからリンクを貼っておきます.

    全体の目次に戻る

  16. 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 を取り直さないといけない. この取り方は,定理の証明方法と同じ.

    全体の目次に戻る

  17. 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 の概念を身につけてください.これは束の表現をするときにとても重要な概念になります.

    全体の目次に戻る

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

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

    */

    全体の目次に戻る

  19. 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 について)
    を参照していただきたい.

    全体の目次に戻る

  20. 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)