束論を勉強しよう (Let's Study Lattice Theory)

(一般のPosetsも含む)

by Akihiko Koga
2nd Feb. 2020 (Update)
7th Oct. 2017 (First)

ホームページトップへ戻る

ここでは,計算機科学に関連する順序集合(Posets : Partially Ordered Sets)の理論について,勉強したことや,思っていることを 書くつもりです. タイトルの束論(Lattice Theory)というのは,象徴的に書いているだけで, 特に順序集合のうち,束論だけに特化するという意図はありません.本当は,順序を 弱めた Preorder にも多くの応用がありますので,このページの対象としては Preorder からです.



内容
  1. 動機 (Motivation)
  2. 理論と応用の関係 (Theories and Applications)
  3. 順序集合や束論の諸概念に関する説明
  4. お勉強のために役立つ文献 (References)
    1. 教科書的なもの
    2. 計算機分野での論文など

(「動機」からまともに読んでいくと能書きが多い可能性があります.目次から 興味のあるところに飛んでみたり,また,
順序集合や束などに関する基本的な概念の説明

最近になって,束論の基礎をかなり拡充しました.

2021.03.10
に,順序集合と束論の基礎や,学習の TIPS 集のようなものを用意していますので,そちらを参照して, あとで暇が出来たときに「動機」から読んでいくという使い方もあります.)

  1. 動機 (Motivation)

    ここでは,束(Lattice)半束(Semilattice)CPO (Complete Partial Ordered Set) , ガロア接続(Galois Connection)など,順序集合に関する 理論について,勉強したことや考えたことを書く予定です.

    1. なぜ,束論? なぜPoset?
      Why lattices? Why posets?

      束論を勉強し始めると, 何のためにこの理論があるのか (PDF), 考え込んでしまいます.応用が見えにくいのです.漠然と論理のモデルを作ったり, 物の関係を分析するのに使ったり(例えば,並列に動くプロセス間の依存関係の解析)には 使えるような気がするのですが,束論に現れる諸概念や定理がどのように使えるのか ピンとこないのです.束論だけじゃなく,数学的な理論はみなその傾向がありますが,束論の場合は 特にそんな気がします.

      例えば,モジュラー束(modular lattice)という束が出てきて,色々な性質が証明され,それが分配束にも使えてと理論展開されるのですが,それがまた分かりにくいのです.

      定義   束 (L, ≤) がモジュラー束であるとは次の条件が成立することである.
          c ≤ a ならば a ∧ (b ∨ c) = (a ∧ b) ∨ c         ∀a, b, c ∈L
      (初心者には)定義もヘンテコに見えるし,第一,この不等式と等式に出てくる4つの 要素の大小関係が頭にイメージできない.紙に書いても分からない.実は紙に書くのも大変. 私は紙粘土と針金で立体モデルを作りました(これについては 障壁を引き下げるで,作成した 3D モデルのことなど,もう少し詳しく書いた New (23rd Dec. 2017)).おまけに これが何の役に立つのか分からない.どの教科書にも,この辺は,さも皆さんが ご存知の当たり前の概念をきちんと書き下しましたというような感じでさらっと 書いてあって,学習する動機を説明してくれない.例だってそうです.群Gの正規部分群の集合を 包含関係で大小関係をつけたもの NSub(G) がモジュラー束の例と言われても, なにが嬉しいのか分からない.さらに,この事実と,モジュラー束のダイヤモンド定理から 群論の第二同型定理
      定理(第二同型定理)  G を群,Nをその正規部分群,SをGの部分群とすると
          (SN)/N ≅ S/(S∩N)
      がすぐ導出できると言われても,「いやいや,ちょっと待て.NSub(G)がモジュラー束であることの 証明と第二同型定理の直接の証明とどっちが簡単よ?」って言いたくなります(あまり変わらないかな).

    2. 束論を学ぶには?

      2020年2月2日 追記

      束論に限らず,一般に抽象数学の学習はかなり困難です.学習の効率を上げたり,学習をあきらめずに成し遂げさせるための基本的な方策は,(1)学習者を引き付けて,学習したいという気持ちを起こさせてやること(2)学習のための障壁を引き下げてやること(極度の抽象性に対する対応など),そして,(3)足腰を鍛えることでしょう.

      ここではこの三つの方策を少し詳しく見ていきましょう.ちなみに,「学習させる」と 他人に対してのような言い方をしていますが,ここでは学習者は自分自身も含みます.

      1. 学習者を引き付ける

        私のような計算機科学に興味があるものにとっては,計算機科学への応用を見せるのが一番なんでしょうね.まあ,一応,すぐ見える応用としては,

        各種形式論理のモデル, 形式的概念分析, 抽象解釈, 領域理論,...
        などがあり,これだけでもずいぶんあるように見えます.でも,自分自身でさえ,そこまで 学習に乗り気がないし,世の中(特に日本)でも流行ってない.流行ってたら, 束論の本がもう少し出版されていて,学習環境が整っているはずです.

        (The rest is to be filled )

      2. 障壁を引き下げる

        認知的な負荷を下げるというのは有効だと思います.例えば,私はモジュラー束が 中々想像できなかったので,紙粘土と針金を使って立体モデルを作ったことがあります. ホームページ上で見ることができるように New (23rd Dec. 2017)

        半順序集合に関する可視化の実験
        にステレオグラムを使った 3Dモデルを載せておきます.この3Dモデルを 何度も見てると,だんだん要素間の関係が分かってきて,条件式をイメージしやすくなる のではないかと思います(人によるかもしれませんが). モジュラー束の条件式を出すための一連の認知的段差の少ないステップ列なども 概念になじむのに有効でしょう.これは束ではありませんが,半群のページで, グリーンの関係 のペーパークラフトを作成していたこともあります.これは,紙をハサミで切ったり, 折ったり,ノリでつけたりで,筋肉の動き,触感,ノリのにおいなど,五感に働きかけて 面白かったです.圏論の米田のレンマや随伴関手のペーパークラフトもこれらを イメージする気苦労を減少させてくれていると思います.

      3. 足腰を鍛える (2020年2月2日追記)

        やはり,学習の動機を持たせてもらったり,障壁を引き下げてもらったりしても, 人任せでは学問は成就しません.複雑な概念を理解できるように, 自分自身が変わっていかねばなりません.私はあるところでC言語の応用編のような ものを教えていますが,分からないという学生をよく見てみると,その応用編が 分からないのではなく,その前から分かってないことが多いのです. 基礎的な概念を理解していなかったり,ごく簡単なプログラムの部分を解読するにも 随分悩んでしまい,肝心の応用編の新しい内容を読むのに振り向ける力が残って 無いのです.

        そういう人たちは,遠回りに見えても,基礎編をもう一度やったり, ごくごく簡単なプログラムを何度も何度も書いてみると,今まで,超えられないと 思っていた障壁が,実は大したものではないということに気付くはずです. つまり,応用編を読むための,基礎編に関する十分な体力をつけるのです. でも,なかなか,後戻りしようという勇気は起きません.

        振り返ってみて,自分たちはどうだろうと考えてみます.基礎が十分理解できているか? 束論の教科書の最初の方の理解は十分か? 練習問題はきちんとやったか? 前の章は まったく苦痛なく読み返せるか? 先ほど例に挙げたC言語応用編で挫折しかかっている 学生さんたちと同じことをやっていないかを考えてみて,もしそうなら,勇気を出して 基礎の理解,それも,あまり困難を感じなくなるまで何度もやり返してみるべきです.

        これに有効な従来の方法は,証明を何度もやり直してみることみたいです.本に書いてある 証明を構造化したり,改良したり,本当に理解できるまでやってみると自然に力が ついてきます.

        ただ,これは結構辛いです.これをある種,気軽にできるルーチンワーク的なものにする方法が あるのではないかと思い,目下,検討中です.これは日記の 計算機科学の発展を支える教育とは? 2019 年 7月 11 日 (木)どこが分からないのか分からない 2019 年 8月 22 日 (木) に書きました.ご興味があれば.

      以上,図の中の3つについて述べました.この3つは相互に関係しています.例えば,「障壁を引き下げる」ことが出来たら, 「学習者を引き付ける」程度は少なてもよいかもしれません.束論の応用としては 上に挙げたように,各種形式論理のモデル, 形式的概念分析, 抽象解釈, 領域理論,...など, 十分見えているのですが,そこで発見され得る未知の知見の価値と,束論を手段として 習得する大変さのトレードオフで多くの人が踏みとどまっているんだと思います.

      と言うことで,応用を挙げていき,それを整理していき,種々の把握しにくい概念の 視覚化や習得容易化を続けて行けば,学習者は増えるのではないでしょうか? 実はこの類のことはイラストの練習

      ソフトウェア科学とボサツ様 (2017.7.19)
      This side and that side in Software science


      ソフトウェア科学とボサツ様のPDF版

      一応,圏論を勉強しよう( English Page "Let's Study Category Theory") も作成して,コンテンツを作成中です.

      にも書きました.

  2. 理論と応用の関係 (Theory and Applications)

    きっと,理論と応用が入り乱れていて,一度に整理しようとすると破綻するんだと思います. ここは,まず,最初のアプローチとして,Posets, Lattices (or Semilattices), CPO (Complete Partial Ordered Sets) と それらの応用の関係あたりを整理して,次第に理論と応用の地図を精密に描いていくのが 良いのではないかと思います.

    例えば,次のような単純な絵を描いてみます.

    この絵に,思いつく応用や応用を目指した論文などを次々に付けていきます. きっと沢山の応用が付くような気がします. この単純な木では,それらの実は支えきれなくなるでしょう.そうしたら, 次第に形を整えて行けば良いのではないでしょうか?

    ほんの少しだけ応用と思えるものを上げてみます.あまり粒度は考えていません.

  3. 順序集合や束論の諸概念に関する説明

    順序集合や束論などの教科書や参考文献は次の項目で説明しているので,そこを 参考にして勉強するテキストを選んで欲しい.ここでは,それらを勉強するにあたって 知っておいた方がよいことや,勉強しながら参考になることなどを説明するつもりである. 具体的な内容は

    順序集合や束などに関する基本的な概念の説明 New (2018.01.14)
    に書いた.束 (lattice) の定義についてや J.B. Nation のテキストでの Dilworth の定理の証明の 参考になる図,これまた J.B. Nation のテキストの 第3章 代数的束の概要などを書いている.今後も気が付いたものを書いていく 積りである (2018.01.14).

  4. お勉強のために役立つ文献 (References)

      ●教科書的なもの(一般的な順序や束の基礎理論)

    1. J.B. Nation, Notes on Lattice Theory

      J.B. Nation of Lattice Theory, Hawaii University Wikipedia の Lattice (order) のページにも出てるくらい有名なので,皆さんご存知だと思います. PDF は,いくつかのURLがあるようですが,著者自身のホームページ

      J.B. Nation のホームページ
      に最新のものがおいてあるようです.そこに置いてある Entirebook は,各章をまとめたものなのですが,必ずしも最新のものではなく,あるタイミングで各章のPDF を統合しているようなので 最新のものを確認したい場合は,各章の PDF を見てください.

      私は,自家製の簡易製本で右の写真みたいな本にして読んでいます.ずいぶん前の バージョンで前半後半別々のPDFだったときに製本していたものを1冊にまとめたため このようなページ(もとは後半の表紙)が途中に挟まっています.キャラクターが結構かわいいでしょう.製本方法は こちらに説明しましたので,ご興味の あるかたは是非.この本の内容のことも書かないといけないので,製本についてはこれくらいにします.

      現在,束論のテキストである程度まとまっていて,PDF でダウンロード可能な本は この本くらいしかないのではないでしょうか? 私も色々探しているのですが, この本以外には見つかっていません(完全に,これ以外見つかってないわけでは ないですが,見つけたものはちょっと誤植が多すぎて読むのが大変だったのです).

      内容としては標準的なことが書かれていると思います.

      順序集合や束論がどのように応用に使われるかは,付録3にある形式的概念分析のこと以外は 書かれていません.

      想定している読者のレベルはあまり定まっているようには思えません.大部分は大学の群論の基礎を 終えていれば(たぶん終えていなくても)読むことは可能とは思いますが,普遍代数の基礎は分かっている方が 良いと思います.普遍代数については,この本の付録にも申し訳程度のことが書かれていますが できれば,私のホームページの別ページで紹介している

      A. J. Cain's "Nine Chapters on the Semigroup Art"
      の第8章 「Varieties & pseudovarieties」くらいの知識はあったほうが良いです. あるいは普遍代数についてはもう少し短いチュートリアルを こちらに紹介しました. たぶん,束論をやるときは普遍代数も併せて勉強した方が良いと思います. 理由は,通常の束論の本に,それらの理論構築の動機が書かれていないからです. 普遍代数は束論構築の一つの動機になっていると思います.

      この本については,私は2点だけ要望がありますが,長くなりますので,

      J.B.Nation への要望
      に書きます. 2つ目は,第2章の closure rules についてです.もし,この定義で悩んでいたら参考になるかもしれません*.すんなり読めたならそこの要望を参照する必要はないです.
      * これについては,著者の J.B. Nation さん自身に連絡をとってみました. closure rules については,上の要望の2番目に書いた解釈で良いそうです. これを尋ねたとき,closure rules の誤解のされやすさと,その解消の方法を 英語で書いたページをつくりましたので,それも書いておきます(要は上に書いた 要望の2番目の英語訳).
      Comment on a set of closure rules in "notes on Lattice Theory by J.B. Nation" (English)
      一応,これも公開してよいと彼に許可を得ました.

      2017年 10 月 26 日(木)

    2. B. A. Davey &H. A. Priestley, Introduction to Lattices and Order (2nd Edition), 2002

      この本は良い本だと思います.Cambridge University Press から出版されており, 有料で(少し値が張りま)すが,束論の基礎を学びたいなら,買っておいて損は ない本だと思います. 計算機科学などの応用のことについても触れてあります.また,ガロア接続を 使った形式的概念分析(FCA : Formal Concept Analysis)についても詳しく述べられています.

      また, JON COHENという人が書いた秀逸なレビュー(PDF)によると,この本の著者は

      「計算機科学者は〇ップレスモデルがお好き」
      という view を持っているそうです. 2ページ目の上から1/3くらいの Accordingly, computer scientists often choose ... のところです.これ意味分かりますでしょうか? 実は,計算機科学でモデルとして使う順序集合はトップ(最大の要素)が無い順序集合が多いのです. これに対して,数学で,例えば,ある代数系のすべての部分代数のなす順序集合ではトップが あります.

    3. H. A. Priestley, Chpter 2. Ordered Sets and Complete Lattices, A Primer for Computer Science, in Algebraic and Coalgebraic Methods, LNCS 2297, 2002, pp21-78
      上の本"Introduction to Lattices and Order"の著者の一人が書いた Posets の計算機応用のチュートリアルです.Abstract には
      These notes deal with an interconnecting web of mathematical techniques all of which deserve a place in the armoury of the well-educated computer scientist.

      (だいぶ意訳になるかもしれませんが)

      これらのノートは,教養のある計算機科学者(well-educated computer scientists)が (研究上の)武器として持っているべき数学的技術がWebのように相互に結合されたものに 関するものである.

      と書いてあります.これは well-educated computer scientist を目指すものにとっては読むしかないですね.

      内容は以下のようなものです.

      1. Introduction
      2. From Binary Relations to Diagrams
      3. Order, Order, Order, ...
      4. Lattices in General and Complete Lattices in Particular
      5. Complete Lattices, Concretely : Closure Systems and Closure Operators
      6. Galois Connections : Basics
      7. Making Connections, Conceptually
      8. The Existence of Fixed Points
      9. Speaking Categorically
      10. References
      予備知識としては,集合,関数,関係の知識があればよいことになっていて,順序集合の 定義から説き起こしてあるのですが,少ないページ数(58ページ)に,初歩的な束の定義などの 簡単なこと, 圏論などの難しいことなど,色々な事を詰め込んであるので, この分野の知識がまだあまり無い人は, 読めるところだけ拾い読みするのがよいかと思います.あと, 第2章の From Binary Relations to Diagrams が少し独特の書き方がしてあって, 私は読みにくかったです.ここは後で,ガロア接続の応用として出てくる形式的概念分析の 導入のような役割をはたします.読みにくければ,ざっとだけ読んで,後(6章 Galois Connections : Basics,7章 Making Connections, Conceptually)で読み返しても良いです.

      B. A. Davey &H. A. Priestley の教科書のJON COHENによるレビューで トップレスモデルのことを書きましたが,こちらのチュートリアルの p69 "8.6 From Complete Lattices to CPOs" の最初の段落に

      ..., and topless models are often to be preferred.
      と書いてありますね.Hilary さん,女性の方なんですけどね.

    4. Roland Backhouse : Galois Connections and Fixed Point Calculus, 2001, pp1-105

      これはまだ読んでいませんが,私の積読(つんどく)リストに入っているので,ここにものせておきます.

      このチュートリアルはガロア接続と不動点計算のチュートリアルです(それじゃあ,タイトルのまんまでんな).

      概要(abstract)によるとガロア接続の基本的な理論と,応用として計算機プログラムの構成を 扱うらしいです(右の図のような感じ).
      目次を章レベルで載せておきます.

      1. Introduction
      2. Galois Connections . Introductory Examples
      3. Abstract Properties of Galois Connections
      4. Existence of Galois Connections
      5. Unity of Opposites
      6. Fixed Points
      7. Fixed Point Calculus
      8. Further Reading
      9. Solutions to Exercises

      ●計算機分野での論文など

      上にあげたものは,順序集合や束論を学ぶための基礎的な文献でした. そのような理論を計算機科学で活用できるようになるためには,それらが実際に どのように使われているかを知ることが重要だと思います. ここでは,私が興味を持っている使われ方の論文を集めておきます. これらは,今,主に積読状態になっています(一部読んだものもありますが).

      まずは本棚から次々にリストしていくだけなのであまり分類していないかも しれませんが,主に,ガロア接続の応用(論理学,形式的概念分析,抽象解釈など), 形式言語理論への応用などになると思います.こちら側と境界が曖昧ですが, チュートリアルなども載せているかもしれません.

      Poset, Lattice 関係で読もうと思っている文献リスト

    
    
    (ちょっと個人の覚書のような内容で申し訳ありません.次第に整理していきます. 圏論の方はここより整理ができていますので,ご興味のある方は
    圏論 (Category Theory) のお勉強
    もご参照ください. )
    
    
    ホームページトップ(Top of My Homepage)