関係圏 -- toward 量子と古典の物理と幾何＠名古屋 - 檜山正幸のキマイラ飼育記 (はてなBlog)

関係圏Relはよく知られ、よく使われる圏です。「量子と古典の物理と幾何＠名古屋」でも関係圏は出てきます。つうか、明白な形で登場する唯一の圏が関係圏Relです。

ここでは、関係圏の性質をザッと眺めます。この記事も一般論で、“話すこと”より“話さないこと”が書いてあります。話す（説明する）必要があると考える内容は、最後の「関係圏ミニマム」にまとめてあります。

内容：

関係圏の定義
その他の定義
関係圏の構造
関係圏におけるテンソル積と指数
半線形代数
関係圏ミニマム

関係圏の定義

AとBを集合として、AからBへの関係とは、A×Bの部分集合のことです。RがAからBへの関係のとき、R:A→B と書きます。この記法はもちろん、圏論的な矢印記法です。すべての集合と関係からなる圏が関係圏Relです。具体的には：

対象： Obj(Rel) = |Rel| = |Rel|₀ = (すべての集合の集まり)
射： Mor(Rel) = |Rel|₁ = (すべての関係の集まり)
dom, cod： R:A→B のとき、dom(R) = A, cod(R) = B
id： id_A := {(x, y)∈A×A | x = y}
comp： R:A→B, S:B→C のとき、comp(R, S) = R;S := {(x, z)∈A×C | ∃y∈B. (x, y)∈R ∧ (y, z)∈S }

結合（合成、comp）に関する結合律と、恒等と結合に関する左単位律、右単位律は確認する必要があります。

関係 R:A→B に関して (x, y)∈R を xRy と書くことがあります。併置（くっつけて並べる）が混乱するときは、x(R)y とか x[R]y とかも使われます。この記法を使うと、x(R;S)z ⇔ ∃y∈B. xRy ∧ ySz となります。「友達の友達は友達だ」の発想です。

RはA×Bの部分集合なので、Rの特性関数（indicating function, characteristic function）をχ_Rとします。

χ_R:A×B→{true, false} （写像）
xRy なら、χ_R(x, y) = true
そうでないなら、χ_R(x, y) = false

記号の乱用で、χ_RをRと書いてしまうと、xRy ⇔ R(x, y) = true となります。この解釈では、RはA×B上のブール値関数です。つまり、AとBをインデックス集合とするブール値行列となります。実際、任意の集合をインデックス集合とするブール値行列の圏は関係圏と同じものです。

その他の定義

関係 R:A→B に対して、写像 R_〜:A→Pow(B) を次のように定義します。Pow(B)はBのベキ集合です。

R_〜(x) := {y∈B | xRy }

R_〜(x) を単にR(x)と書いてしまうと、

y∈R(x) ⇔ xRy

上記の同一視により、関係Rは非決定性写像（集合値写像、多値写像）とみなせます。関係圏と非決定性写像の圏は同じ（圏同型）です。

集合Xにそのベキ集合Pow(X)を対応させる対応は、共変関手にできます。これを共変ベキ集合関手と呼びます。さらに、平坦化 flatten_X:Pow(Pow(X))→Pow(X) と単元集合埋め込み single_X:X→Pow(X) が定義できるので、全体として集合圏上のモナドになります。このベキ集合モナド (Pow, flatten, single) のクライスリ圏は非決定性写像の圏 -- つまり、関係圏でもあります。

「スパンの圏と行列の圏」で述べたように、行列の圏とスパンの圏は近しい関係にあります。関係圏がブール値行列の圏であるなら、スパンの圏としても表現できそうです。

一般にCが終対象とファイバー積（プルバック）を持つ圏のとき、スパンの圏Span(C)を定義できます。C = Set と置いたSpan(Set)は、関係圏より大きな圏です。関係圏だけを取り出すには、スパン A←f-X-g→B に次の制限を付けます。

左脚fと右脚gのデカルトペア <f, g>:X→A×B が単射である。

このようなスパンは結局、A×B内の部分集合と同じモノなので、関係とみなせます。関係の結合や恒等関係もスパンの圏におけるそれと一致します。つまり、関係圏はスパンの圏に埋め込めます。なお、スパンを使った関係の定義は双対化できて、関係の双対的な概念も定義できます。

余関係＝関係の双対概念

ここまでの話で、関係圏の定義は、オリジナルの定義以外に、次の定義が可能であることが分かりました。

ブール値係数の行列の圏
ベキ集合モナドのクライスリ圏＝非決定性写像の圏
左右の脚のデカルトペアが単射であるスパンの圏

関係圏の構造

関係圏はデカルト積（圏論的直積）を持ちます。つまり、デカルト圏です。しかし、集合の直積がデカルト積ではありません。集合の直和が関係圏のデカルト積なのです。R:A→B, S:A→C に対して、RとSのデカルトペアは、A×(B + C) $\stackrel{\sim}{=}$ A×B + A×C の部分集合で、集合としての R + S で与えられます。

関係圏は余デカルト積も持ちますが、余デカルト積も集合の直和で与えられます。結果的に、デカルト積と余デカルト積が一致する圏になります。このような圏は半加法圏と呼びます。「半加法」という名称が腑に落ちないですが、それについては次を参照：

関係圏では、射（関係）の転置（transpose, converse）ができます。R:A→B の転置をR^tと書くと、

R^t := {(y, x)∈B×A | (x, y)∈R }

対象（集合）Aに関してはA^t = A と定義しておきます。すると、(-)^tは対合的反変自己関手になります。

(R;S)^t = S^t;R^t
(id_A)^t = id_A
(R^t)^t = R

転置のようなオペレーターは一般にダガー（dagger）と呼ばれ、ダガーを持つ圏はダガー圏といいます。関係圏は典型的なダガー圏です。

関係圏におけるテンソル積と指数

関係圏はデカルト積を持ち、これをモノイド積としてモノイド圏になります。余デカルト積はデカルト積と一致します。デカルト積と余デカルト積が一致した積は特に双積（biproduct）と呼びます。双積をモノイド積とするモノイド圏が、先に紹介した半加法圏で、もちろん関係圏は半加法圏の構造を持ちます。

集合の直積は、関係圏のなかでデカルト積に（余デカルト積にも）なりません。しかし、モノイド積にはなります。モノイド積としての集合の直積（くどいが、圏論的直積ではない）は、ベクトル空間の圏のテンソル積とかなり類似しています。なので、集合の直積を関係圏のテンソル積と呼ぶことにします。

テンソル積は閉構造を持ちます。言い方を変えると、テンソル積に対する指数が存在してカリー同型が成立します。

Rel(A $\otimes$ B, C) $\stackrel{\sim}{=}$ Rel(A, [B, C])

ここで、 $\otimes$ がテンソル積、[-, -]が指数です。実は、指数がテンソル積と一致してしまうのですが、そのへんの事情は次の記事に書いてあります。

Alloyの矢印記法と、モノイド閉圏としての関係圏

半線形代数

関係圏は、双積、転置（ダガー）、テンソル積、指数などの構造を持つので、ベクトル空間の圏と類似しています。関係圏のなかで、かなりの程度線型代数を行うことができます。ただし、引き算はできないので半線形代数と言っておきます。

関係圏におけるスカラーは、テンソル単位I（単元集合）の自己射です。Rel(I, I) = {R | R⊆I×I} = {空集合, I×I} $\stackrel{\sim}{=}$ {0, 1} なので、スカラーは0と1です。圏とそのスカラーの関係は次の記事で書いています。

対象（集合）Aに対して、Aのベクトルは射 v:I→A のことです。単元集合IからAへの関係はI×Aの部分集合、つまりAの部分集合なので、Rel(I, A) $\stackrel{\sim}{=}$ Pow(A) です。つまり、AのベクトルとはAの部分集合のことになります。

双対的に、Aのコベクトルは射 f:A→I ですが、これもAの部分集合のことです。つまり、関係圏の半線型代数では、ベクトルもコベクトルも部分集合です。さらに、転置 (-)^t:Rel(I, A)→Rel(A, I) があるので、ベクトルとコベクトルのあいだの標準的な1:1対応があります。空間と双対空間が標準的に対応しているとは、そう、内積空間です。

関係圏は、単なるベクトル空間の圏より内積空間の圏に近いのです。関係圏における内積(u|v)は、

(u|v) := u;(v^t) : I→I

で与えられます。これは、2つの部分集合が交わるかどうかの判定になっています。

関係圏ミニマム

関係圏の定義はオリジナルの（標準的な）定義を採用します。R:A→B in Rel は R⊆A×B です。
その他の定義（行列圏、クライスリ圏としての関係圏）は必須ではありません。が、関係を非決定性写像とみなすことは、しばしば有用なので知っておいたほうがいいでしょう。xRy 以外に、R(x)⊆B という書き方に慣れておくといいですね。
関係圏のテンソル積、つまり集合の直積は知っておくべきです。R:A→B, S:C→D に対してR $\otimes$ S:A $\otimes$ C→B $\otimes$ D の定義も必要です。
関係の転置は便利だし、関係圏全体の対称性（自己双対性）を理解するためにも使い慣れるべきです。モノイドのような代数系に対して、転置によりすぐさま双対な代数系（モノイドなら余モノイド）が作れます。これは非常に役に立ちます。