bitterharvest’s diary

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

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

随伴関手の応用 - Haskellでの実現例

8.8 Haskellでの実現例 HaskellはHaskと呼ばれる一つの圏で構成されるため、二つの圏を必要とする随伴の例を見ることは少ない(往々にして、関手でHask圏の外に出てしまう)。しかし、積と関数はともに相手方への関手であるため、例外的にHaskellでの随伴の…

随伴関手の応用 - モナドとしての随伴関手

8.7 モナドとしての随伴関手 今回は、随伴がモナドであることを示そう。二つの局所的に小さな圏\(\mathcal{C},\mathcal{D}\)において、関手の対\(R: \mathcal{C} \rightarrow \mathcal{D}, L: \mathcal{D} \rightarrow \mathcal{C}\)が次の条件を満たす時…

随伴関手の応用 - モノイドとしての随伴関手

8.6 モノイドとしての随伴関手 随伴関手の応用についていくつか説明してきたが、アダルトとベビーの例を始めとしてこれまでの例ではすべて、左側の圏の方が厳密であることに気がついただろう。今回の例も同じである。左側がモノイドを対象にした圏、右側…

随伴関手の応用 - 写像対象としての随伴関手

8.4 写像対象としての随伴関手 写像対象は次のように定義される。対象射 \begin{eqnarray} eval : B^A \times A \rightarrow B \end{eqnarray} を有する対象\(B^A\)が写像対象であるとは、任意の対象\(X\)と射\(g: X \times Y \rightarrow B\)に対し、射 …

随伴関手の応用 - 積としての随伴関手

8.3 積としての随伴関手 \(\mathcal{C}\)は対象\(A,B\)を有する圏とする。\(A\)と\(B\)の積は、\(A \times B\)と書かれる\(\mathcal{C}\)の対象と二つの射\(fst : A \times B \rightarrow A \)および\(snd : A \times B \rightarrow B \)との組で、以下の…

随伴関手の応用 - 随伴関手を理解するための比喩

8.2 随伴関手を理解するための比喩 比喩(Metaphor)は難しい概念を理解する助けをしてくれる。随伴関手は高度に抽象的な概念なので、理解しやすくするためには、やはり優れた比喩を必要とするだろう。David Spivakがその著書『Category Theory for the Sci…

随伴関手の応用 - 自然変換の合成

8.随伴関手の応用 圏論の創始者はソーンダース・マックレーン(Saunders Mac Lane)とサミュエル・アイレンベルグ(Samuel Eilenberg)だ。1942年から45年にかけて、代数的位相幾何学(Algebraic Topology)を研究する中で、関手や自然変換などの圏論の概念を生…

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

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

随伴関手 - 随伴関手を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{…

随伴関手 - 随伴の解釈

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