読者です 読者をやめる 読者になる 読者になる

北海道苫小牧市出身の初老PGが書くブログ

永遠のプログラマを夢見る、苫小牧市出身のおじさんのちらしの裏

今日は 圏論勉強会 第4回 の日です

圏論勉強会ではない方の圏論勉強会 第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(X, -) : C → Sets という関手。対象Aを集合Hom(X, A)へ移す
    • - には何か入るという意味
    • 射f : A → B は Hom(X, A) → Hom(X, B) なる関数にならなければならない
    • Hom(X, -)が関手であれば、普通の関手の議論ができて嬉しい
  • 例: 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と下付きで書いてるけど、書きにくいので