このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

可愛い圏

対象の集まり、射の集まりが集合となるような圏は小さい圏(small category)と呼びます。ここでは、小さな圏のなかでも特に、対象集合や射集合が身近なモノであるような圏を可愛い圏として紹介します。

内容:

やせた圏

Cが圏だとして、次の条件を満たすときやせた圏(thin category)といいます。

  • 任意の対象A, Bに対して、ホムセットC(A, B) が空集合か単元集合。

Cがやせた圏のとき、関係 A ≦ B を次のように定義します。

  • A ≦ B ⇔ C(A, B) が空ではない

Cはやせているので、「空ではない」は「単元集合である」でも同じです。次のことはすぐにわかります。

  1. 任意の対象Aについて、A ≦ A
  2. 任意の対象A, B, Cについて、A ≦ B かつ B ≦ C ならば A ≦ C

つまり、(|C|, ≦) はプレ順序集合です。逆に、プレ順序集合 (X, ≦) が与えられれば、それからやせた圏を作れます。

実数R、整数Zは順序集合(当然にプレ順序集合)なので、これらからやせた圏を作れます。RZの部分集合もやせた圏になります。+∞, -∞ とか入れても大丈夫です。

集合のベキ集合、例えば Pow({a, b}) = {{}, {a}, {b}, {a, b}} は順序集合なので、やせた圏になります。任意の単純有向グラフ(サイクルがあってもかまいません)からやせた圏が作れます -- この構成は関係の反射的推移的閉包を作るのと同じことです。

演繹系とその論理式の集合があるとき、Aを仮定してBを証明できるとき A ≦ B と定義すると、やせた圏になります。このへんのことは、「論理とはなにか?」に書いています。

直積、直和、始対象、終対象

引き続き、「やせた圏=プレ順序集合」で考えましょう。プレ順序≦に関して、AとBのミートを定義します。XがAとBのミートである条件は次のとおり:

  1. X ≦ A かつ X ≦ B である。
  2. Y ≦ A かつ Y ≦ B であるなら、Y ≦ X となる。

Xに関する条件は、要するに「AよりもBよりも小さいモノのなかで一番大きい」という条件です。プレ順序集合では、AとBのミートが存在しても一意性は保証できませんが、XとX'がAとBのミートなら、「X ≦ X' かつ X' ≦ X」は言えます。AとBのミート(のひとつ)を A∧B と書くことにします。

A∧B の特徴を圏論の言葉で言えば:

  1. A∧B→A、A∧B→B という射が存在する。
  2. Y→A、Y→B という射が存在するなら、Y→X という射が存在する。

Cがやせていることから、「射が存在する」を「射が一意的に存在する」に言い換えることができます。すると、ミートA∧Bは、AとBの圏論的な直積であることがわかります。先に出した例、RZ、Pow({a, b})、単純有向グラフ、論理式などの例で、ミート=直積が何であるかを考えてみてください。

ミートと双対的に「AとBのジョインA∨B」を定義すると、これは直和(余直積)となっています。プレ順序≦に関する最小元(一意とは限らない)があれば、それは圏の始対象となります。同様に、最大元は終対象です。

例えば、実数の区間 {x∈R | 0≦x≦1} は、直積、直和、始対象、終対象を備えた可愛い圏です。2元集合{0, 1}でも同じ特徴を持っています。メチャ可愛いですね。

モノイド積とモノイド閉構造

(C, ×, 1)がデカルト圏のとき、対象Aによるデカルト積の意味での掛け算関手(-×A)に随伴の右(右でいいんだよな?*1)相方がいるとき、その相方を(-A)と指数の形で書きます。任意の対象に指数(掛け算関手の右随伴)があるなら、その圏Cデカルト閉です。

以上のように定義されるデカルト閉圏(CCC; Cartesian closed category)はとても有名ですが、より一般にモノイド閉圏、あるいは閉モノイド圏の概念があります。これは、デカルト積(直積)とは限らないモノイド積に関して、閉構造が存在することです。閉構造があるとは、任意の掛け算関手に随伴の右相方がいることです*2

では、可愛いモノイド閉圏を紹介しましょう。N = {0, 1, 2, ...} として、Nに普通の大小順序を考えるとやせた圏ができます。ミートは n∧n = min(n, m)、ジョインは n∨m = max(n, m) と定義できて、それぞれ圏の直積と直和を与えます。0が始対象であり直和の単位です。終対象(かつ直積の単位)はありませんが、必要なら∞を入れておけばいいでしょう。

今は、デカルト積じゃなくて、別なモノイド積を考えましょう。その前に、集合Nから作られる圏を、Nそのものと区別してNat(naturalから)と書くことにしておきます。念のために圏の構造を記しておくと:

  1. Obj(Nat) = |Nat| = N
  2. Mor(Nat) = Nat = {[n, m]∈N×N | n≦m}
  3. dom([n, m]) = n, cod([n, m]) = m
  4. id(n) = idn = [n, n]
  5. comp([n, m], [m, k]) = [n, m];[m, k] = [n, k]

ここで、Nat上のモノイド積として普通の足し算を考えます。足し算を Nat×Nat→Nat という関手にしないといけませんが、対象(自然数)に対してはホントに足し算、射に関しては次のように定義します。

  • [n, m] + [p, q] = [n + p, m + q]

大小順序と足し算の関係から、(Nat, +, 0) がモノイド圏になることがわかります。このモノイド圏にトレースを入れる話は「こんな簡単なトレース付きモノイド圏があったなんて」に書いています。さて、このモノイド圏がモノイド閉構造を持つには足し算の随伴となる指数が必要です。次の同値性が欲しいわけ。

  • (n + m ≦ k) ⇔ (n ≦ km)

ここで、km と指数の形に書いてますが、ほんとの指数(累乗)を意味しているわけじゃないですから気をつけてください。混乱を防ぐために、km の代わりに [k <- m] と書くことにすると:

  • (n + m ≦ k) ⇔ (n ≦ [k <- m])

この同値性を成立させる演算 [k <- m] はあるのでしょうか? あります。探してみてください。

もうひとつのモノイド閉圏

P = {x∈R | x>0} として、Pをベースに圏Pos(positiveから)を作ります。

  1. Obj(Pos) = |Pos| = P
  2. Mor(Pos) = Pos = {[x, y]∈P×P | x≦y}
  3. dom([x, y]) = x, cod([x, y]) = y
  4. id(x) = idx = [x, x]
  5. comp([x, y], [y, z]) = [x, y];[y, z]) = [x, z]

この圏に正実数の掛け算「*」を使ってモノイド積を入れます。

  • (x*y ≦ z) ⇔ (x ≦ [z <- y])

この同値性なら分かりやすいでしょう。[z <- y] が割り算ならOKですね。

  • (x*y ≦ z) ⇔ (x ≦ z/y)

つまり、モノイド圏としてのPosにおいて、モノイド積は掛け算で指数は割り算なのです。「指数は割り算」とだけ聞くと、奇妙な感じがしますが、圏の閉構造の観点からは確かにそうなっています。指数が割り算なんてオチャメで可愛い

可愛い豊饒圏

Vが、対称モノイド圏(閉でなくてもよい)であるとき、V-豊饒化(V-enrichment)を考えることができます。圏Vとして可愛い対称モノイド圏をとると、V-豊饒圏(V-enrichec category)も可愛い圏となります*3

ローヴェル(W. Lawvere)が示した例 -- 非負実数を対称モノイド圏と考えると、距離空間や超距離空間が豊饒圏となる -- は可愛いので有名です。{0, 1} に∧(min、または論理AND)でモノイド積を入れた対称モノイド圏で集合を豊饒化すると、順序集合が得られます。「モノイド圏、豊饒圏、閉圏と内部ホム」も参照してみてください。

プラット(V. Pratt)は、可愛い圏Vに関するV-豊饒化手続きが、フロイド/ウォーシャル(Floyd-Warshall)法による行列計算であることを指摘しています。可愛くない圏(例えばSet)に関する豊饒化も、超絶計算パワーを持つ神様が行列計算を遂行していると言えなくもないでしょう。

*1:右と左の区別は苦手だーー!

*2:モノイド積が対称でないときは、右指数と左指数を区別する必要があります。

*3:「可愛い」の定義はありません。