bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

プログラマーのための圏論 (上級編)

プログラマのための圏論:上級編(上)

『プログラマのための圏論:上級編(上)』はこれまで、プログラマのための圏論(上級編)で説明してきたことをまとめました。圏論での重要な概念である、極限、米田の補題、随伴関手についてまとめてあります。

随伴関手 - 随伴関手をHaskellで表現する

7.8 随伴関手をHaskellで表現する 随分と時間がかかったが、随伴関手をHaskellで表現するための準備がほぼ出そろった。ほぼといったのは、もう一つだけ、頭の体操をしておかなければならないことがある。それは、右随伴関手が表現可能関手でもあるという…

随伴関手 - 随伴の別定義

7.7 随伴の別定義 1)別定義 随伴の定義にはこれまでと異なる方法がある。それは次のように定義される。\(\fbox {随伴の定義2:}\) 二つの局所的に小さな圏\(\mathcal{C},\mathcal{D}\)において、関手の対\(R: \mathcal{C} \rightarrow \mathcal{D}, L:…

随伴関手 - 随伴から導き出される可換図

7.6 随伴から導き出される可換図 随伴の定義からどのような可換図が導きだされるかを考えてみよう。随伴の定義は次のようになっている。二つの局所的に小さな圏\(\mathcal{C},\mathcal{D}\)において、関手の対\(R: \mathcal{C} \rightarrow \mathcal{D}, …

随伴関手 - 随伴の解釈

7.5 随伴の解釈 随伴の定義は次のようになっていた。二つの局所的に小さな圏\(\mathcal{C},\mathcal{D}\)において、関手の対\(R: \mathcal{C} \rightarrow \mathcal{D}, L: \mathcal{D} \rightarrow \mathcal{C}\)が次の条件を満たす時、随伴であるという…

随伴関手 - 随伴の定義

7.4 随伴の定義 数学で最も重要な概念はと問われた時、皆さんは何と答えるだろうか。私は、「等しい」だと思う。算数から数学へと教科の名前が変わり、少し大人になったと感じさせてくれた中学で、すぐに習ったのが三角形の合同であった。ある三角形を移…

随伴関手 - 米田の埋め込み

7.2 余米田の補題 米田の補題では、共変\(\rm{Hom}\)関手\(\mathcal{C}(A,-)\)を用いていたが、これを反変\(\rm{Hom}\)関手\(\mathcal{C}(-,A)\)に変えたのが、余米田の補題となる。次のようになる。局所的に小さな圏\(\mathcal{C}\)と集合の圏\(\mathcal…

随伴関手 - 米田の補題:復習

7 随伴関手 7.1 米田の補題:復習 米田の補題は次のようになっていた。局所的に小さな圏\(\mathcal{C}\)と集合の圏\(\mathcal{Set}\)、これらによって作られる関手圏\([\mathcal{C},\mathcal{Set}]\)を考えよう。今、任意の対象\(A \in \mathcal{C}\)と…

米田の補題 ー 集合値関手を積として表す

6.6 集合値関手を積として表す 米田の補題は次のようになっていた。局所的に小さな圏\(\mathcal{C}\)と集合の圏\(\mathcal{Set}\)、これらによって作られる関手圏\([\mathcal{C},\mathcal{Set}]\)を考える。任意の対象\(A \in \mathcal{C}\)と任意の関手\…

米田の補題 ー 継続渡しのプログラム

6.5 継続渡しのプログラム 1980年代後半に情報科学を学んだ人々にとって、アベルソンとサスマン夫妻が書かれた『計算機プログラムの構造と解釈』は思い出に残る本だったと思う。私も、情報科学の中でどれが最も良い本であったかと問われればこの本をあげ…

米田の補題 ー Haskellで理解する

6.4 Haskellで理解する 米田の補題の補題を下図の可換図を用いて説明した。Haskellを用いてさらに理解を深めることとしよう。 Bartosz Milewskiさんが上手に説明しているので、それを借りることにしよう。\({\rm Hom}\)関手を作成しよう。\(Reader\)のデ…

米田の補題 ー 証明

6.3 米田の補題の証明 前回の記事で米田の補題を提示した。米田の補題は次のようになっていた。局所的に小さな圏\(\mathcal{C}\)において、\({\rm Hom}\)関手\(h^A: \mathcal{C} \rightarrow \mathcal{Set}\)から、集合値関手\(F: \mathcal{C} \rightarro…

米田の補題 - 米田の補題とは

6.2 米田の補題とは 米田の補題を説明する前に、圏論とは一見関係のなさそうなカニと大相撲の例について説明した。そこでの説明で重要な事項は、操作ボタンと機械の動作が一対一に対応していることだ。米田の補題は、このような状況を、数学的に説明した…

米田の補題 ー 具体例

6.米田の補題 今回の記事は、米田の補題(Yoneda lemma)である。圏論の定義の中で、個人名がついている定理や補題はそれほど多くない。これから紹介する補題は、数少ない例の一つである。そして、重要な定義であることには間違いない。それも、かなり難解な…

表現可能関手

5. 表現可能関手 日本の歴史を学んでいるといくつもの学説に出会う。それらの中で、圏論との関わりが面白いと思った学説が中世史にあったので、それを最初に紹介しよう。一つは、「権門体制論」である。黒田俊雄氏の学説で、中世の国家体制は、公家権門(執…

自由モノイド

4.自由モノイド 圏論では、普遍性という概念はとても大切である。普遍性は、その言葉が示すように、数学の多くの分野で共通する性質を示したものである。前の記事で説明した極限と余極限も広い分野での共通の性質であるため、圏論での重要な普遍性の一つと…

極限-Readerと極限

3.3 \(Reader\)と極限 ここまでの記事で、\(Reader\)の使い方と定義について詳しく説明した。この記事では、さらに理解を進めるために、圏論での極限とのかかわりについて説明しよう。圏論は、様々な数学の分野で共通に成り立っている性質について論じる…

極限-HaskellでのReaderを定義する

3.2 \(Reader\)を定義する Haskellでは\(Reader\)を用意している。Control.Monad.Readerというモジュールを読み込めば、使えるようになっている。しかし、このモジュールを理解しようとすると、忍耐力を必要とする。汎用性を高めるために、\(Reader\)が、…

極限-HaskellでのReaderについて

3.Haskellでの極限と余極限 これまでの記事で、極限と余極限の説明をしてきた。数学的な記述が主で、Haskellを学ぼうとしている人は、役に立たないなと感じたことだろう。圏論での積や余積は、乗算や加算、あるいは、論理積や論理和と関係があることは、直…

極限-余極限の例

2.2 余極限の抽象化 前回と同じように、余極限を抽象化してみよう。ここでは、下図のように、三つの圏を用意する。最初の圏\(\mathcal{C_0}\)は、余錐の頂点からなる圏だ。次の圏\(\mathcal{C}\)は余錐で構成される圏だ。最後の圏\([\mathcal{I,C}]\)はイ…

極限-余錐と余極限の定義

2.余極限 極限と双対の関係にあるのが、余極限である。 2.1 余錐と余極限の定義 前回までの記事で、極限について説明してきた。極限は錐(cone)を用いることで定義した。即ち、ある圏の中で錐が定義できたとする。そのような錐は、複数あっても一つでも…

極限-極限の例

1.8 錐の例 今年のブログの締めは、少しでも圏論が身近に感じられるようにするために、錐の例を取り上げよう。前回のブログで、抽象度の高い、下図のような極限の可換図を示した。 この可換図は、錐を作成すると、それがどのような極限なのかを、示してく…

極限-錐と極限のさらなる抽象化

1.7 錐と極限のさらなる抽象化 前回の記事で、錐は二つの異なる方法で作成できることが分かった。一つは、錐の頂点から錐の底面への写像を自然変換で与えるものである。もう一つは、求める錐の頂点から極限の錐の頂点への射を与えるものである。前回は、…

極限-錐と極限の抽象化

1.6 錐と極限の抽象化 前回の記事までで、インデックス圏を用いての粋と極限の求め方を説明してきた。その中では、インデックス圏から粋を作成しようとしている圏へ、三角形のまま移す関手と、一点にまとめる関手を用意した。前者は錐の底辺を形成し、後…

極限-極限の定義

1.5 極限の定義 前回の記事で、インデックス圏から錐を作成する方法を示した。 上図で、関手\(D\)によって、インデックス圏\(\mathcal{I}\)での三角形(頂点が対象、辺が射)が、圏\(\mathcal{C}\)に移され、これから作成される(三角)錐の底辺を形成する。…

極限-錐

1.4 錐 これまで、2回にわたって、圏論での極限の具体的な例を示してきた。そこでは、二つの対象\(A\),\(B\)とその極限\(A \times B\)ということで説明をした。また、極限は、ある条件を満たすものの中で最も良いものといういい方もした。また、ある条件…

極限-例:最大公約数

1.3 最大公約数 前回の記事では、集合を利用して、圏論での積を説明した。また、積の普遍性についても説明した。これらをさらに進めると、極限になる。しかし、もう少し例を挙げて、極限の説明をするための準備をすることにしよう。ここでは、集合から離…

極限-圏論の積

プログラマのための圏論(初級編)では、自然変換まで説明した。ここまで理解すると本当の意味で圏論を自由に扱えるようになる。上級編では、これまでの理解を踏まえて、さらに圏論の奥義を学ぶことにしよう。 1.極限 圏論の特徴は抽象階層だと思う。圏は、…