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

圏論勉強会ではない方の圏論勉強会 第5回です。資料とustreamは公開されています。

• 今日は倚子が追加された
• ワークスアプリケーションズ社さんに感謝しましよう

第5回: 様々な射 / 講師 @9_ties さん

• Hom集合についての補足
  • A言語とB言語のトランスレーターtと問題のA言語での解法fがあるとする
  • B言語での解法はt.f (共変)
  • B言語でのインタプリタをinterpとすると、A言語のインタプリタはinterp.t (反変)
  • オブジェクト思考でも同様の考え方ができる
    • インスンタンスを作るのは共変
    • フィールドから値を取り出すのは反変
  • 計算機では射は実装する可能性があるもの → 自動で射を移せるのはありがたい
• 同型射
  • g.f = 1, f.g = 1, 同型射がある対象同士は同型
  • gは逆射 → 一意なのでf^-1と書く
  • 証明 → gとhがfの逆射であれば、g = g.id = g.f.h = id.h = h
• 函手は可換図を保つ → 同型性も保つ
  • fが同型射 → F(f)も同型射
  • fが同型射 → F(f^-1) = F(f)^-1
  • A ≃ B → F(A) ≃ F(B)
• C^opは同型性を保つ
  • 反変函手も同型性を保つ
• Hom(X,-)は共変、Hom(-,X)は反変
  • A ≃ B → Hom(X, A) ≃ Hom(X, B), Hom(A, X) ≃ Hom(B, X)
  • Aの回りの射とBの周りの射が対応
  • オブジェクトの性質は射に表われるので、重要
  • gとhをHom(X, f)とHom(f^-1, Y)でf.gとh.f^-1に移しても可換図は保たれる
• AとBが同型であれば区別できない
  • Aに関して成り立つことはBに関しても成り立つ
  • 具体的でないとわからないことは圏論で調べるのに向かない
• 例: (R, +)と(R, ×)は同型
  • 全然違うものだけど、区別できない
  • 例えば、メモリ効率などは不明
  • 一つの圏の中で全て表現しようと思うべきではない
  • 圏論で述べられる範囲については気をつけたほうが良い
• 同値関係 → 二項関係が、反射律、対称律、推移律、を満す
• 同型は同値関係
  • A≃A (恒等射)。A≃B ならば B≃A。A≃B,B≃CならばA≃C(合成)
• モノイドでの同型 → x・y = y・x = eのことなので、可逆元
  • (R, ×)の同型射は0以外の全ての実数
  • 同型"射"は関数とは限らない
• 半順序集合での同型 → x <= y, y <= x より x = y 、つまり自分自身のみ
• 証明の圏における同型 → 同値な命題
• fが単射 → f(x) = f(y) ならば x = y
• fが全射 → 任意のyについて、y = f(x)なるxがあること
• fが全単射 → 全射かつ単射
• Setsにおける全単射は同型射 → 証明はスライド参照
• 集合の要素の数が等しい → 全単射があること
  • カントールにより、無限集合にも一般化。濃度(cardinal number)。
  • Nと偶数の集合の濃度は等しい
  • カントール「任意の集合Aについて、A→P(A)への全射は存在しない」(P(A)の方が大きい)
  • 無限集合にもサイズ大小がある
  • オブジェクトの中の性質を射で表現したと言える
  • 計算機科学とも無関係ではない
• 証明(対角線論法): f:A→P(A)で全射のものがあったとする
  • X = {x: f(x)にxが含まれない}とする
  • 全射なので、f(x) = Xなるxがあるはずだが、xがXに含まれても含まれなくても矛盾
  • 計算機科学で言えば、停止性を判断するプログラムが作れないこと、の証明となる
• プログラムは文字の集まりなので、自然数と同じ濃度
  • できることとできないことがある、ということを意味する
  • 例えば、計算機では求めることができない実数が存在する
• レトラクト → 同型を少し弱めたもの
  • r.s = 1のみ成り立つとする
  • sがセクション(断面、切断(幾何学分野より))
  • rがレトラクション(撤回する、と言う)
  • 直感的には、sで埋めこんだものをrで復元できる
• 函手はレトラクトを保つ
• Setsにおけるレトラクト
  • セクションは単射
  • レトラクションは全射
  • レトラクションは集合を類別(classify)する
  • セクションは類別されたグループから元を選択している
  • 選択公理の圏論的な形式化となる
• s.rとはなんなのか
  • 全ての元を、セクションによって選択された元に移す → 射影と見なせる
  • 羃等な射になる
• rのセクションが存在 ⇔ 任意のfについてf = r.gとなるgが存在
  • ⇒ g = s.f とするとr . (s . f) = f
  • ← 自明
• プログラミングで言えば、射(プログラム)を分解できるか
  • 仕様→HTMLとDSL→HTMLがあったときに、DSL→HTMLにセクションがあれば仕様→DSLで常に表現できる
• 位相空間と連続写像の圏
  • S1(円)→D2(円盤)への埋め込みはレトラクションか
  • 連続写像では取り出せない
  • レトラクションは何かを含む、ことを言うには強すぎる条件
• fがレトラクションを持つ→rでfをキャンセルできる
  • monomorphism(モノ射、モニック射)
  • m.f=m.g ならば、f=gであること
• Setsのモノ射と単射は同値
  • fとgを1からの射として具体例をイメージするとわかりやすい
• epimorphism(エピ射)
  • f.e = g.e ならば f = gであること
• Setsでのエピ射は全射
• 同型射→モニックかつエピック
• fがレトラクションを持つ→fはモニック
• fがセクションを持つ→fはエピック
• モニックかつエピックでも、同型射とは限らない
  • Monの圏で、f:(N,+)→(Z,+)を考えると、同型射ではない
  • しかし、モニックかつエピック。g(-n)の移り先はg(n)で決まるため
  • fは0以上の部分の断面をとっているが、断面だけで等しいと言えてしまう(テキストのEx. 2.5)
• Cのモノ射はC^opのエピ射。
  • モノの性質を示せばエピの性質を示したことになる
  • 来週以降は双対性をどんどん使う
• 羃等射 → e.e=eなるe
  • (s. r).(s.r) = s.id.r = s.r (先程の証明)
  • 分裂羃等射(split idempotent) → 羃等射がセクションとレトラクションに分解できる
• プログラミングで言うと、連続して実行しても１度だけ実行しても同じ
  • 最適化や正規化に使える。冗長性(redundancy)を扱う文脈で使う
  • 並列アルゴリズムで、共有メモリに同じ命令列が並んだり。