圏論を勉強しよう

(Let's Study Category Theory)

English Ver. (What are the foundamental mathematics for computer sciences?)

このページの内容

1. 動機

2. 色々な圏論の教科書
   圏論のいろいろなテキストを紹介しているサイト

3. 主な教科書の概要
   Steve Awodey : Category Theory,
   Tom Leinster : Basic Category Theory, 2014,
   M. Barr and C. Wells : Category Theory for Computing Science, 1998, 558ページ,
   Peter Smith : Category Theory : Gentle Introduction, 2016 (当面保留),
   David I. Spivak: Category Theory for the Sciences, 2014, 263 pages,
   Benjamin Pierce : A Taste of Category Theory for Computer Scientists, 1988, 75 pages,
   Emily Riehl : Category Theory in ontext, 2014, xvii + 240 pages
   

4. 関連トピックス
   
   • モナド (Monads)
   • Algebras and coalgebras

●動機

やはり圏論が必要だな

圏論の教科書を書く人たちは，圏論はもちろんのこと，ほかの 数学のバックグラウンドがあるので，数学の素人がなかなか理解できない ことを理解できないんだと思います．その点，今，勉強している私は 苦しんでいる最中ですから，初学者が苦しむところを理解することが できるのじゃないかなと思います．

で，何から始めようかと考えたのですが，これから学ぶもの，つまり圏論ですね， その全貌を知っている ということは学習に役に立つのではないかと思いますので，インターネットで アクセスできる圏論の教科書，何冊かを選んでどんなことが書いてあるか 調べてみましょう．方法としては，各章の頭にその章の説明が書いてあることが あるので，それを調べていきましょう(教育学の中で「先行オーガナイザ(advance organizer)」と呼ばれているものを考えています)．まずは Awodey からかな．先にも書いたように 私自身，今，圏論を勉強している最中ですから，以下の説明に誤解がある可能性が あります．したがって，皆さんは，「およそこの本にはこんなことが書いてあるのだな」 くらいの情報を受け取って，興味があるものはご自身で読んでみてください．

●色々な圏論の教科書(主にインターネットで入手可能なもの)

まずは，圏論の free で available な教材として何があるかは， Peter Smith 先生の

Logic Matters : Category Theory

The Galois Connection between Syntax and Semantics

さらに，実は Peter Smith 自身も圏論の簡単な導入用テキスト

Peter Smith: : Category Theory: A Gentle Introduction, 2016

●主な教科書の概要

1. Steve Awodey : Category Theory
   定評のある本ですね．計算機科学に関係のある話題も扱っています．例としてラムダ計算が 出てきたり，ある種の圏（Cartesian Closed Category）が論理やラムダ計算の モデルになるといった話題などです．

   これについては短い解説を書きました． 絵かここをピックしてみてください．
   

2. Tom Leinster : Basic Category Theory, 2014
   日本では「ベーシック圏論 普遍性からの速習コース」というタイトルで翻訳本が出ていますね． これは，ほぼ最初から随伴関手（Adjoints）が出てきて，幕間を挟んで，米田のレンマ，極限・余極限と続き，最後にそれらの関係が述べられます．速習をうたっていますが，しょっぱなからガツンとやって，難しさに慣れさせる学習方法でしょうか．話題としては数学だけで，計算機科学は カバーしていません．薄いので，これでまず基礎を学び，周辺分野を扱っている 他のテキストやレクチャーノートに移るという使い方をすると良いのだと思います．

   これについては短い解説を書きました． 絵かここをピックしてみてください．
   

3. M. Barr and C. Wells : Category Theory for Computing Science, 1998, 558ページ
   分厚さで敬遠していたのですが，パラパラと見てみると， 計算機科学（Computing Science）のネタが沢山つまったた本みたいです．
   
   ということで，とりあえず，各章の扉の説明だけでも読んで整理してみる 気になりました．まだ書きかけですが，上のリンクか絵をピックしてみてください． 整理しているページにとびます． 個人的には，その後，内容も細かく読んでいくという気がします． 2019.07.15 (月)

4. Peter Smith : Category Theory : Gentle Introduction, 2016 (当面保留)
   

   上に書いた Peter Smith 先生の本です．著者本人が

   今までの圏論の本は，ある程度決まった進み方があった．でも，最近，そうでない進み方があることが分かった．最初に 圏論の最終目的に近いところをやってしまう．でも，それだと，やはりある程度できる学生しか読めない（Leinster のことかなあ？）．私はその逆にうんと丁寧に進めてみる

   といったたぐいのことを書かれています．

   Adjunction あたりの章（第２５章以降)はまだだいぶ変わる可能性があるということで，当面，まとめを作るのは 保留しますが，最初の方はもうだいぶ固まっているということです． 私は，自然変換の章などは，Awodey の圏論の本を読むときなどに結構参考にさせて いただきました（２０１７年９月２０日記）．

5. David I. Spivak: Category Theory for the Sciences, 2014, 263 pages
   
   "for Sciences" というのが惹かれますね．

   今，印刷して右のような感じで 簡易製本して読んでいます（簡易製本は事あるごとに紹介することにしているのです）．

   この本は，だいたい次のような構成です．

   1. Introduction
      導入

   2. The category of sets
      集合の圏で，圏論で導入された色々な概念を味合います．特に，彼が Olog と 呼んでいる，日常の事象を集合の圏の枠組みで表現するための（図式）言語を 導入し，そこで，圏論の「極限」などの概念を卑近な例として味合います．

   3. Categories and functors, without admitting it
      後で圏論の例になり得る，モノイド，群，グラフ，順序，データベーススキームとインスタンスを大急ぎで学習する．without admitting it ですから，ここでは，まだそれらが 圏になり得るということを忘れて学習します．データベースが入っているのが他のテキストと大きく違いますね．

   4. Basic category theory
      圏論の基礎的な概念の説明．
      Categories, Functors, Categories and Functors in math., Natural transformations, Categories and Schemata are equivalent, Limits and Colimits, Other notions in Cat

   5. Categories at work
      科学者が仕事場で使う圏論という意味合いだと思います．Adjoint functors, Categories of functors, Monads, Operads について説明されます．

   
   

   この本の評価はかなり分かれるのではないかと思います．私の評価は言いません．まだ読んでいる 途中でもありますし，英語もあまり堪能ではありませんし（日常語で記述されたテキストから 生き生きしたイメージを 受け取るためには，読者側は英語の堪能さが要りますよね．この本ではありませんが，私は上にあげた Peter Smith 先生が イメージを伝えようとして力説すればするほど，イギリスの古い民に根付いた固有の単語がでてきて 読むのがつらいのです．長さ 5 から 7 くらいの短い単語で，こんなに知らない単語があったのかと 驚かされます．むしろラテン語系のテクニカルタームの方が有難いのです．曖昧性も 少なくなりますし）．

   と言う訳で，例えば，Awodey や Leinster あるいは，上にあげている Peter Smith の圏論の本を 読める人はそちらを読んで，必要だったり，興味があれば，こちらでどのようにそれらを数学以外の人たちに 説明しているかを読み解くのが良いのではないだろうかと思います．

   自分の数学の熟練度がまだ低いと考えている人，数学にはほとんど興味がなく，自然科学の 中でどのように圏論が使われ得るのか知りたい人はこれを読んでみるのも手だと思います． Olog とか彼独特の言い回しが 数学の熟練度が小さい人に対して，十分イメージを伝えることに成功しているか， あるいは，そこまでイメージの強化に寄与せず，単にページを増やしているかという ところが評価の別れどころでしょうね．でも，まあ，Olog で日常的な事象の中から， 圏論の概念を構成してみるのは面白いと思いますよ．

6. Benjamin Pierce : A Taste of Category Theory for Computer Scientists, 1988, 75 pages
   短いレクチャーノートですが，後半が計算機科学への応用の Case Study になっています． 圏論の説明はその前の 42p までです．米田のレンマは入っていませんが 随伴関手（Adjoints）の説明は入っています．

   Case Study としては次のものがあげてあります．

   1. Categorical Type Systems
      萩野達也先生の論文 "A Typed Lambda Calculus with Categorical Type Constructors, 1987, LNCS 283" の紹介でプログラミング言語の型構造の基礎に圏論を使うものです．

   2. Implicit Conversions and Generic Operators
      ここでは，John Reynolds の論文を紹介していて，例えば，整数と実数の 両方に対する generic な加算の取り扱いに関する圏論的なアプローチを紹介しています．

   3. Semantics
      ここはプログラミング言語の意味論に対する圏論的なアプローチとしてどのような 研究があるかを全体的に見ています．

   4. Recursive Domain Equations
      再帰的な領域（例えば，A を予め規定された領域として D ≅ A + (D → D) となるような領域 D）の扱いに対する圏論的なアプローチを述べています．

   とにかく短いので，ざっと全体を見てしまい，動機を持って他の分厚い教科書やそのほか各分野の論文やチュートリアルに行くというのが良いのではないでしょうか．

   前半部分の圏論の基礎では，正味 pp7-42 の36ページしかなく，どちらかというと定義，例，解説からできています．圏論らしい証明としては付録に Limit Theorem の証明があります．Products と Equalizers がある圏では Limits が構成できるという定理ですね．初心者はこれは見ておいた方が良いです．数学に慣れていない人は，中に出てくる E-indexed products が分からないと，読めないかもしれませんが，何となく証明のエッセンスを感じ取って，自分で products と equalizers を使って極限をいくつか構成してみると良いと思います．

7. Emily Riehl : Category Theory in Context, 2014, xvii + 240 pages
   この本は Dover Publications から出版されています．という ことはかなり良心的な価格の本ということですね．また，PDF は freely available みたいです． ここらあたりは彼女のweb-site に書かれています．彼女の web-site は 上のEmily から Context までの行を Copy & Paste して google で検索すると探すことができると思います．そこを見ると，圏論だけでなく，スポーツや音楽など，多方面で活発な方の ように見えますね．

   本の内容ですが，数学の範囲内の本です．基本的には計算機科学は入ってないみたいです ¹⁾． レベルですが， 前書きの Note to reader によると，原理的には基本的な集合論と論理を学んだ後に読めるのだが，それなりの数学的な成熟度を要求するとのこと．この本の中の例を眺めてみて大部分が大筋で 理解できるなら大丈夫でしょうが，そうでないならたぶん読むのは難しいのではないでしょうか．

   章立ては次の通りです．

   1. Categories, Functors, Natural Transformations
      Abstract and concrete categories, Duality, Functoriality, Naturality, Equivalence of categories, The art of the diagram chase, The 2-category of categories
   2. Universal Properties, Representability, and the Yoneda
      Lemma Representable functors, The Yoneda lemma, Universal properties and universal elements, The category of elements
   3. Limits and Colimits
      Limits and colimits as universal cones, Limits in the category of sets, Preservation, reflection, and creation of limits and colimits, The representable nature of limits and colimits, Complete and cocomplete categories, Functoriality of limits and colimits, Size matters, Interactions between limits and colimits
   4. Adjunctions
      Adjoint functors, The unit and counit as universal arrows, Contravariant and multivariable adjoint functors, The calculus of adjunctions, Adjunctions, limits, and colimits, Existence of adjoint functors
   5. Monads and their Algebras
      Monads from adjunctions, Adjunctions from monads, Monadic functors, Canonical presentations via free algebras, Recognizing categories of algebras, Limits and colimits in categories of algebras
   6. All Concepts are Kan Extensions
      Kan extensions, A formula for Kan extensions, Pointwise Kan extensions, Derived functors as Kan extensions, All concepts

   注意：

   1) 今，ざっと本の中を見てみたら，"computer science" という 単語が１０か所くらいでていました．カーリー化，つまり A × B → C が A → B → C と 同型であること, Maybe monad などです．

●関連トピックス

1. モナド (Monads)

   モナドは，関数型言語で副作用を閉じ込めるのに使われているという触れ込みなどでプログラマの関心を集めています．

   ここでは，モナドに関する色々な文献とその内容を調べてみます． 対象としては，特に関数型言語のモナドの使い方には限りません（でも，そこから始めます）．

   一応，定義としては，圏 C から C への自己関手 T に対して，C のオブジェクトXをT(C) のオブジェクトT(X)へ「変換」する自然変換ηとT²(X) = T(T(X))のように T がネストしてしまったオブジェクトを T(C) のオブジェクトにほどく自然変換μが存在して，それらがモノイドの条件に似たある条件を満たすときに，(T, η, μ)をモナドと言います．

   例えば，C が集合の圏 Setsとするとき，関手 T : Sets → Sets を，集合 X に対して，

   T(X) = X の全ての部分集合の集合 = 2^X

   とし，自然変換 η:1 → T, μ:T² → T を

   η_X(x) = {x} for x ∈ X

   μ_X(y) = ∪y for y ∈ 2^2X

   とすれば (T, η, μ) はモナドになります．

   このとき，例えば，X={a, b, c} に対して， ηとμは，

   η_X : X → 2^X

   例えば η_X(a) = {a}

   μ_X : 2^2X → 2^X

   例えば μ_X({{a}, {a, b}}) = ∪{{a}, {a, b}} = {a}∪{a, b} = {a, b}

   のように，それぞれ {} を付ける関数，最上位の要素の {} を一つ解く関数になります． この例題の設定の場合，自然変換 ηとμは，各集合 X に対して，

   関数 η_X : X → 2^X,

   関数 μ_X : 2^2X → 2^X

   を決めたものであることに留意してください．

   
   

2. Bart Jacobs , Jan Rutten : A Tutorial on (Co)Algebras and (Co)Induction, 1997, 38 pages
   圏論のテキストでは，Monads や Algebras はトピックスとしては出てくるのですが， 大抵，それらの圏論的な構成の方法までで，実際に代数を使って応用を楽しむということは あまりありません．

   このチュートリアルは，Algebra と CoAlgebra を使ったソフトウェアシステムのモデリング に関するものです．図で，Algebra は 自然数やリストなどのように別の型から 生成する手段があって，帰納的(Inductive)にそれらのデータの領域が作られます． それに対して，無限リストや整楚でない集合（non-well-founded sets）など，どうやって 作られたかは問わず，ユーザから，destructor (あるいは observer)で，それを構成する データを次々に取得して観測することが出来るものもあります．中がどうなっているか 分からないけど（つまりブラックボックス），内部状態を持っていて，色々な信号に対して，返答を返すような システムもこちらの種類のものです．こちらのシステムの証明手段は (Co)Induction です．

   

   このチュートリアルは上に書いたようなことを，圏論での Algebras, CoAlgebras を使って扱う 手法を簡単に紹介しています．予備知識としては，Awodey の Category Theory の第１０章 Monads と Algebras を読み終えた後がちょうどよいと思います（下の段落で修正 2020.01.09）．もっとも，この チュートリアルはかなり分かりやすく書かれていますので，関手が出てきた後，どの段階でも， ざっと読んで，圏論の応用の仕方を頭に入れて，再度，圏論のテキストに戻るのも 良いかもしれません．

   2020.01.09 (木) 補足
   先日，久しぶりにこのチュートリアルを読み返してみました．結構良い読み物です．計算機科学の人間が圏論を 勉強するときは，それを計算機科学で使いたいからですが，通常のボトムアップの教科書では 使えるようになるまでかなりの下積み生活を強いられ，根性が無いと続けていけません． この論文は，圏論が計算機科学でどう使われ得るかを示唆してくれます．基本的には関手の 概念が分かれば分かるように構成されています．また関手自身もその他の圏論の概念も， 集合の圏という特別な場合においてですが，このチュートリアルで定義されています．したがって，実は，集合論の 基礎さえ知っていれば原理的には読むことができます．上の段落では，Awodey の第１０章と 書いていましたが，どこで読んでも良いと思います．もちろん，内容は深いので，どこまで くみ取れるかは読者のそのときの状態次第ですが，早くから読んでみて，分かるところは 分かって得をする，分からないところは動機付けに利用して得をするという 使い方が良いと思います．