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

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

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

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

レポート math

圏論勉強会ではない方の圏論勉強会 第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) → 羃等射がセクションとレトラクションに分解できる
  • プログラミングで言うと、連続して実行しても1度だけ実行しても同じ
    • 最適化や正規化に使える。冗長性(redundancy)を扱う文脈で使う
    • 並列アルゴリズムで、共有メモリに同じ命令列が並んだり。