圏論勉強会ではない方の圏論勉強会 第4回にまたやって来ました。資料とustreamは公開されています。
- ワークスアプリケーションズ社に入ると、リハーサルも見れてお得だよ！
第4回: 射で考える / 講師 @9_ties さん
- 様々な概念を圏論の言葉のみで述べる
- 今日もHaskellのセクション記法使う : (1 +)みたいの
- Hom集合
- テキストの順番を無視してるけど、非常に重要な概念
- 「今回は大変厳しい会になります」
- 単集合(unit set, singleton) : 要素がひとつの集合
- 単集合1から集合Aへの関数は、Aの要素の数だけ
- Aから1への関数は、1つ
- 要素が2個の集合からAへの関数は、|A|^2
- 集合Aから要素が2個への集合への関数は、Aの部分集合の数(2^|A|)だけある
- 関数空間: 集合AからBへのすべての関数の集合
- 関数空間の構造(例えば要素がいくつあるか)は、AとBの構造から決まる
- Hom(A, B)、hom-set : AからBへ向かうすべての射の集合
- 「集合」であることに注意
- Aの要素と、Hom(1, A)の要素は同一視ができる A ≃ Hom(1, A)
- 対象、射、合成だけでは、Aの要素(Aの内部)について述べられない
- Hom(1, A)の要素は射なので、圏論の言葉で述べられる
- Hom(2, A) ≃ A×A、Hom(A,2) ≃ P(A)
- Hom(A, 1)の要素は1つだけ → 普遍性(来週やる内容)
- Q. Hom(1, A)が要素の個数を表すためには、1の構造(要素)について言及が必要では？
- A. 1を圏論の言葉で定式化できる(そこに向かう射が1つのみ存在)
- Hom集合は、対象自体よりも豊かな構造をしている → Hom集合を調べるとよい
- 集合 → Setsの対象。圏Cの議論をSetsへ移せる
- Sets(N, R) → すべての実数列 *1
- 半順序集合と単調関数からなる圏Posについて、Pos(N, R) → 単調増加実数列
- ベクトル空間と線形写像からなる圏VctのVct(V, R) → 双対ベクトル空間
- Vが有限次元だと、双対ベクトル空間からVが復元できる
- Mon(N+, Z×) ≃ Z
- f(1) = 2とすると、f(2) = f(1 + 1) = f(1) × f(1) = 4
- 1の行き先だけでモノイド準同型fは決まってしまう
- モノイドの圏から、コドメインの台集合が出てきた
- Hask(a, b) := a -> b に属する値
- 前提: エラーが起こる関数は無視する(⊥は考えない)
- f :: Integer -> () に属するのは f x = () しかない
- Hom(A, 1)に要素が1つであることに対応
- f :: () -> Integer に属するのは f () = n (nはInteger)
- 型(Hom集合)を見ることで、実装の複雑さがわかる
- 普遍射: 〜〜を満たす射は一個 → 実装も1つに定まる
- ⊥を考えてみると、 g x = g x なる g :: Integer -> () が考えられる
- ()は2点集合なので、Integerの部分集合の数だけ実装が作れてしまう
- ⊥は再来週くらいに話す予定
- Hom(X, A)に構造を入れる
- Aに構造があれば、Hom集合にも構造を入れられる
- Sets(X, M)でMがモノイドであれば、Sets(X, M)もモノイド
- 各点ごと(pointwizeな)定義ができる → (f・g)(x) := f(x)・g(x)
- Aが半順序集合であればSets(X, A)も半順序集合
- f <= g を f(x) <= g(x) で定義
- 関手圏 D^Cの構成は、Hom(C, D)にDの構造を入れることの一般化
- 射をpointwiseに集めたものが自然変換
- Mがモノイドの時、Hom(X, M) ≃ M^X
- Xは離散圏、Mはモノイド(対象が1つの圏)と見なす
- M^X内の関手は1つ。自然変換はMの射の数だけ。
- 関手圏の話は今後も繰り返すので、徐々に理解して欲しい
- Haskellでの例: instance Monoid b => Monoid (a -> b)
- Int -> Intの関数がf, gがあれば、Sum . f <> Sum . gができるようになる
- 「誰か役に立つ用途を考えてください」
- generalized element
- Hom(X, A)はAの構造そのものと見なせる
- 射a :: X → Aをgeneralized elementと呼ぶことができる
- 言い換えると、Hom(X, A)を「Aのものの集合」と見なす立場、のこと
- point-free
病style- 射と合成のみでプログラムを書くこと
- 言い換えると、圏論の言葉だけでプログラムを表現する
- one = \() -> 1 とすると、要素1と射oneが一対一対応に
- 帰納法でこの概念を定義すると議論しやすくなる
- zero = \() -> 0
- succ = \n -> n + 1
- succ . succ . succ . zero は 3を意味する
- 少ない語彙でプログラムを表現できる
- Hom関手
- 例: Hom(1, -) : Sets -> Sets を考えてみる
- Hom(1, A) → Hom(1, B)を考えるのだけど・・・
- f は Hom(1, f) (a) = f . a なる関数Hom(1, f)に移って欲しい
- つまり、fを(f .)に移す
- 1を任意の集合Xにしても、状況は同じと考えられる
- fを(f .)に移す話は第二回でやった
- aをendomorphism (a ・)に移すのは、M(*, -) : M → Setsを考えたことになる
- 共変Hom関手 C(X, -)の定義
- 対象Aを集合C(X, A)へ
- 射fを関数C(X, f) = (f .) :: C(X, A) → C(X, B)へ
- 関手であることの証明
- Hom(X, f.g)(h) = (f.g .)(h) = f.g.h
- (Hom(X, f).Hom(X, g))(h) = Hom(X, f) (g . h) = f.g.h
- 結合則は満たす。恒等射も同様
- 反変(contravariant)Hom関手 C(-, X)の定義
- 対象AはC(A, X)に映る
- 射f::A→BはC(f, X) = (. f) :: C(B, X) → C(A, X)
- 射が逆になってるので関手ではない → 双対圏C^op→Setsの関手にはなっている
- ここを乗り越えれば圏論は簡単と思えるようになるはず
- 次回は同型、モノ、エピ、普遍射など
*1:本当はHom_Setsと下付きで書いてるけど、書きにくいので
