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

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

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

参照用 記事

関係圏 -- toward 量子と古典の物理と幾何@名古屋

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

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

内容:

  1. 関係圏の定義
  2. その他の定義
  3. 関係圏の構造
  4. 関係圏におけるテンソル積と指数
  5. 線形代数
  6. 関係圏ミニマム

関係圏の定義

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

  • 対象: Obj(Rel) = |Rel| = |Rel|0 = (すべての集合の集まり)
  • 射: Mor(Rel) = |Rel|1 = (すべての関係の集まり)
  • dom, cod: R:A→B のとき、dom(R) = A, cod(R) = B
  • id: idA := {(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)を対応させる対応は、共変関手にできます。これを共変ベキ集合関手と呼びます。さらに、平坦化 flattenX:Pow(Pow(X))→Pow(X) と単元集合埋め込み singleX:X→Pow(X) が定義できるので、全体として集合圏上のモナドになります。このベキ集合モナド (Pow, flatten, single) のクライスリ圏は非決定性写像の圏 -- つまり、関係圏でもあります。

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

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

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

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

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

関係圏の構造

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

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

関係圏では、射(関係)の転置(transpose, converse)ができます。R:A→B の転置をRtと書くと、

  • Rt := {(y, x)∈B×A | (x, y)∈R }

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

  • (R;S)t = St;Rt
  • (idA)t = idA
  • (Rt)t = R

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

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

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

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

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

  • Rel(A\otimesB, C) \stackrel{\sim}{=} Rel(A, [B, C])

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

線形代数

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

関係圏におけるスカラーは、テンソル単位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;(vt) : I→I

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

関係圏ミニマム

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