「導出系： 反省と課題 // ソート付き集合の圏は変わる」において、ソート付き集合達の圏 $`\mathbf{SortedSet}`$ を導入したのですが、その定義は関係をベースにしています。
関係をベースにした定義は、どうも分かりにくいし扱いにくいので、ファミリー〈集合族〉をベースにした定義に切り替えようと思いました。このような切り替えをしてもよい理由と、切り替えをするときに使うメカニズムの解明と説明をこの記事でします。これは、関係とファミリーが“どんな関係”になっているかをハッキリさせることです。$`\newcommand{\cat}[1]{\mathcal{#1}}
\newcommand{\mrm}[1]{\mathrm{#1}}
\newcommand{\mbf}[1]{\mathbf{#1}}
%\newcommand{\msf}[1]{\mathsf{#1}}
\newcommand{\twoto}{\Rightarrow }
\newcommand{\ot}{\leftarrow }
%\newcommand{\parto}{ \supset\!\to }
\newcommand{\In}{\text{ in }}
\newcommand{\op}{\mathrm{op}}
\newcommand{\id}{\mathrm{id}}
%\newcommand{\u}[1]{\underline{#1}}
%\newcommand{\o}[1]{\overline{#1}}
\newcommand{\hyp}{ \text{－} }
\newcommand{\H}{ \text{-} }
\newcommand{\Iff}{ \Leftrightarrow }
\newcommand{\Imp}{ \Rightarrow }
\newcommand{\base}[1]{ {{#1}\!\lrcorner} }
%\newcommand{\SEArrow}{\style{display: inline-block; transform: rotate(45deg)} {\Rightarrow} }
%\newcommand{\NEArrow}{\style{display: inline-block; transform: rotate(-45deg)} {\Rightarrow} }
%\newcommand{\Models}{ \mathrel{|\!\!\models} }
`$
内容：
関係圏と関係2-圏
関係圏 $`\mbf{Rel}`$ の対象集合〈set of objects〉とホムセットは次のようです。
- 対象集合： $`|\mbf{Rel}| := |\mbf{Set}|`$
- ホムセット： $`\mbf{Rel}(A, B) := \mrm{Pow}(A\times B)`$
圏のネーミングに関して注意しておくと（混乱する人もいるので）、集合圏は「集合を対象とする圏」ですが、関係圏は「関係を射とする圏」です。関係圏の対象は集合です。
圏 $`\cat{C}`$ の恒等射、結合を（他の圏の恒等射、結合と区別するために）$`\id^\cat{C}, \mrm{comp}^\cat{C}`$ のように書くことにして、関係圏の恒等射と結合は以下のようです。
$`\quad \id^{\mbf{Rel}}_A := \Delta_A := \{(x, y)\in A\times A\mid x = y\}`$
$`\quad \mrm{comp}^{\mbf{Rel}}_{A, B, C}(R, S) := \{(x, z)\in A\times C
\mid \exists y\in B.\, (x, y)\in R \land (y, z)\in S\}`$
ホムセット $`\mbf{Rel}(A, B)`$ はベキ集合なので、部分集合の包含順序関係から順序集合になります。関係のあいだの包含関係を2-射とみなします。
$`\text{For }R, R' \in \mbf{Rel}(A, B)\\
\quad (\alpha :: R \twoto R') :\Iff (R \subseteq R')
`$
2-射 $`\alpha`$ とは、包含関係 $`R\subseteq R'`$ に名前を付けたものです。2つの部分集合のあいだの包含関係は（在っても）1つしかないので（以下、二重矢印 $`\twoto`$ がオーバーロードされているので注意）：
$`\quad (\alpha, \beta :: R \twoto R') \Imp (\alpha = \beta')`$
つまり、圏としての $`\mbf{Rel}(A, B)`$ はやせた圏〈thin category〉です。
各ホムセットに包含順序関係から圏の構造を入れると、結果的に2-圏が出来上がります。この2-圏は関係2-圏〈2-category of relations〉です。
1-圏としての関係圏と2-圏としての関係圏を区別したいなら：
- 1-圏としての関係圏は、$`\mbf{Rel}1`$ または $`{_1 \mbf{Rel}}`$ と書く。
- 2-圏としての関係圏は、$`\mbf{Rel}2`$ または $`{_2 \mbf{Rel}}`$ と書く。
関係の転置、全域性、一意性
ここでの $`\mbf{Rel}`$ は2-圏だとします。通常の圏論の記法により $`\mbf{Rel}^\op`$ は反対圏だとします。2-圏の反対圏は1-射の向きは逆転しますが、2-射の向きはそのままです。
関係圏の転置〈transpose〉は次のような自己反変関手です。
$`\quad \mrm{T} : \mbf{Rel}^\op \to \mbf{Rel} \In \mbf{CAT}`$
転置関手 $`\mrm{T}`$ は対象集合上で恒等〈identity-on-objects | i.o.o.〉な関手なので：
$`\quad \mrm{T}_\mrm{obj} = \id_{|\mbf{Rel}|} \; : |\mbf{Rel}| \to |\mbf{Rel}|\In \mbf{SET}`$
転置関手 $`\mrm{T}`$ のホムパートは次のように書けます。
$`\quad \mrm{T}_{A, B} = \mrm{T}_{\mrm{hom}(A, B)} \;: \mbf{Rel}(A, B) \to \mbf{Rel}(B, A) \In \mbf{Set}`$
具体的には：
$`\text{For} A, B \in |\mbf{Rel}|\\
\text{For} R \in \mbf{Rel}(A, B)\\
\quad \mrm{T}(R) := \{(y, x) \in B\times A\mid (x, y)\in R\}
`$
$`\mrm{T}(R)`$ を通常は $`R^\mrm{T}`$ と書きます。対象集合上で恒等な反変関手なので、次が成立します。
$`\text{For }A, B, C\in |\mbf{Rel}|\\
\text{For }R:A \to B, S: B\to C \In \mbf{Rel}\\
\quad A^\mrm{T} = A\\
\quad {\id_A}^\mrm{T} = \id_{A^\mrm{T}} = \id_A\\
\quad (R; S)^\mrm{T} = S^\mrm{T} ; R^\mrm{T}
`$
関係 $`R:A\to B\In \mbf{Rel}`$ が全域〈total〉であるとは、次が成立することです。
$`\quad \forall x\in A.\exists y\in B.\, (x, y)\in R`$
全域であることは、恒等射（$`\Delta_A`$ などと書く）と関係のあいだの包含関係を使って次のようにも書けます。
$`\quad \Delta_A \subseteq R ; R^\mrm{T}\;: A\to A\In \mbf{Rel}`$ （全域性）
若干トリッキーかも知れませんが、全域性の条件を次のように書き換えてみると分かります。
$`\quad \forall x, x'\in A.(\, x = x' \Imp
\exists y\in B.((x, y)\in R \land (y, x')\in R^\mrm{T}) \,)
`$
関係 $`R:A\to B\In \mbf{Rel}`$ が一意{的}?〈unique〉であるとは、次が成立することです。
$`\quad \forall x, x'\in A.(\, \exists y\in B.( (x, y)\in R \land (x', y)\in R )
\Imp
x = x' \,)
`$
全域であることは、恒等射（$`\Delta_A`$ などと書く）と関係のあいだの包含関係を使って次のようにも書けます。
$`\quad R; R^\mrm{T} \subseteq \Delta_A\;: A\to A\In \mbf{Rel}`$ （一意性）
これは、一意性の条件から（わずかな書き換えで）すぐに出ます。
一意的なことは univalent〈単葉 | 一価〉ともいいますが、最近 univalence が別な意味で使われることが多いので、「一意」を使うことにします。
一意な関係は部分関数とみなせます。一意かつ全域な関係は関数〈写像〉とみなせます。
関係 $`R: A\to B`$ の転置が全域なとき、$`R`$ は余全域〈cototal〉または全射{的}?〈surjective〉といいます。全射の条件は次のように書けます。
$`\quad \Delta_B \subseteq R^\mrm{T}; R \;: B\to B\In \mbf{Rl}`$ （全射性）
関係 $`R: A\to B`$ の転置が一意なとき、$`R`$ は余一意{的}?〈counique〉または単射{的}?〈injective〉といいます。単射の条件は次のように書けます。
$`\quad R^\mrm{T}; R \subseteq \Delta_B\;: B\to B\In \mbf{Rel}`$ （単射性）
$`\mbf{Rel}`$ は2-圏なので、$`\mbf{Rel}`$ のなかの随伴系やモナドを考えることが出来ます。興味ある方は、$`\mbf{Rel}`$ 内の随伴系やモナドを調べてみてください。
ここまでに紹介した関係の性質達 全域性、一意性、全射性、単射性は、部分圏を定義できる性質です。次のような広い部分圏〈{wide | broad} subcategory〉を定義します。
- $`\mbf{Rel}^\mrm{tot}`$ ： 全域な関係を射とする部分圏
- $`\mbf{Rel}^\mrm{uniq}`$ ： 一意な関係を射とする部分圏
- $`\mbf{Rel}^\mrm{surj}`$ ： 全射的な関係を射とする部分圏
- $`\mbf{Rel}^\mrm{inj}`$ ： 単射的な関係を射とする部分圏
転置関手 $`\mrm{T}`$ を部分圏に制限すると、次のような“部分圏のあいだの圏同型”が得られます。
$`\quad \mbf{Rel}^\mrm{tot} \overset{\mrm{T}}{\longleftrightarrow} \mbf{Rel}^\mrm{surj}\\
\quad \mbf{Rel}^\mrm{uniq} \overset{\mrm{T}}{\longleftrightarrow} \mbf{Rel}^\mrm{inj}
`$
ファミリー達の圏
ファミリー達の圏〈category of families〉を $`\mbf{Fam}`$ と書きます。ファミリー達の圏は「ファミリーを対象とする圏」です。
ファミリー達の圏 $`\mbf{Fam}`$ の対象集合〈set of objects〉とホムセットは次のようです。以下の $`\mrm{MAP}(\hyp, \hyp)`$ は大きい〈小さいとは限らない〉集合のあいだの関数空間です。
- 対象集合： $`|\mbf{Fam}| := \sum_{X\in |\mbf{Set}|}\mrm{MAP}(X, |\mbf{Set}|)`$
- ホムセット： $`\mbf{Fam}(F, G) := \sum_{f\in \mrm{Map}(\base{F}, \base{G})} \mrm{Nat}(F, f^*(G) : \base{F}\to \mbf{Set})`$ （以下に説明あり）
ホムセットが複雑ですね。順に説明します。
ファミリー $`F: X\to |\mbf{Set}|`$ に対して、次の記法の約束をします。
$`\quad \base{F} := \mrm{dom}(F) = X`$
$`\base{F}`$ は、ファミリー $`F`$ のベース集合〈base set〉またはインデキシング集合〈indexing set〉と呼びます。大きな関数の域〈ドメイン〉を、ファミリーの文脈ではそう書く／呼ぶ、というだけです。単に域〈ドメイン〉 $`\mrm{dom}(F)`$ の別名／別記法です。
ファミリー $`F:\base{F} \to |\mbf{Set}|\In \mbf{Set}`$ は、集合 $`\base{F}`$ を離散圏とみなすと、次のような関手です。
$`\quad F: \base{F} \to \mbf{Set} \In \mbf{CAT}`$
以下、「ファミリーは離散圏から集合圏への関手だ」という態度をとります。これは、大事な視点の変更です。
$`F, F'`$ がベース集合〈インデキシング集合 | 域〉 $`X`$ を共有する2つのファミリー（関手です！）だとすると、そのあいだの自然変換 $`\alpha`$ を考えることができます。
$`\quad \alpha :: F \twoto F' : X \to \mbf{Set} \In \mbf{CAT}`$
自然変換達の集合を $`\mrm{Nat}(\hyp, \hyp)`$ 記法を使って書くと：
$`\quad \alpha \in \mrm{Nat}(F, F')`$
あるいは、もう少し丁寧に書いて：
$`\quad \alpha \in \mrm{Nat}(F, F' : X \to \mbf{Set})`$
$`F, G`$ が異なるベース集合〈インデキシング集合 | 域〉 $`X, Y`$ を持つときは、インデキシング集合のあいだの関数〈写像〉 $`f`$ による引き戻しを使って、ベース集合を揃えます。そのときは次のように書けます。
$`\quad \beta :: F \twoto f^*(G) : X \to \mbf{Set} \In \mbf{CAT}`$
ここで、$`f^*(G)`$ は、関数 $`f`$ も関手とみなしての関手結合 $`f*G`$ のことです（アスタリスクは関手結合の図式順演算子記号）。$`f^*`$ はプレ結合引き戻しです。
さて、2つのファミリー $`F, G`$ のあいだの射 $`\varphi: F \to G`$ は、2つのパートのペア $`(\base{\varphi}, \varphi^\#)`$ です。ベースパート〈base part〉と呼ばれる $`\base{\varphi}`$ は、ベース集合のあいだの関数〈写像〉です。
$`\quad \base{\varphi} : \base{F} \to \base{G} \In \mbf{Set}`$
ファイバーパート〈fiber part〉である $`\varphi^\#`$ は次のような自然変換です。
$`\quad \varphi^\# :: F \twoto \base{\varphi}^*(G) : \base{F} \to \mbf{Set} \In \mbf{CAT}`$
別な書き方をすると：
$`\quad \varphi^\# \in \mrm{Nat}(F, \base{\varphi}^*(G) : \base{F} \to \mbf{Set})`$
まとめると、2つのファミリー $`F, G`$ のあいだの射 $`\varphi`$ を決めるには次の手順を実行します。
- ベース集合 $`\base{F}`$ から $`\base{G}`$ への関数 $`f`$ を決める。つまり、関数空間の要素 $`f\in \mrm{Map}(\base{F}, \base{G})`$ をひとつ選ぶ。
- 選んだ $`f`$ をベースパートと考えて、ファイバーパートを決める。つまり、自然変換の空間の要素 $`\beta \in \mrm{Nat}(F, f^*(G) : \base{F} \to \mbf{Set})`$ をひとつ選ぶ。
- 選んだ $`f`$ と $`\beta`$ を $`f =: \base{\varphi}`$ 、$`\beta =: \varphi^\#`$ とした射 $`\varphi = (\base{\varphi}, \varphi^\#)`$ が決まる。
この手順を、シグマ型構成により書き下したのが以下の形（再掲）です。
$`\quad \sum_{f\in \mrm{Map}(\base{F}, \base{G})} \mrm{Nat}(F, f^*(G) : \base{F}\to \mbf{Set})`$
$`\varphi = (\base{\varphi}, \varphi^\#)`$ という書き方は依存ペアです。ペアの第一成分がベースパート、第一成分に依存して選ばれる第二成分がファイバーパートです。
圏としての恒等射と結合も、ルーチンワークをこなせば構成できます。実は、ルーチンワークの部分はテンプレート化されています。ファミリー達の圏は、Diag構成の一例です。興味があれば以下の記事を参照してください。
ファミリーと関係の相互変換
ファミリーと関係の相互変換とは、文字通り「ファミリー ←→ 全射関係」の一対一対応です。ファミリー達の圏と関係圏が圏同型だとか圏同値だとか言ってるわけではありません。集合のあいだの同型に過ぎません。
「ファミリー ←→ 全射関係」という同型があるとは、次の図式が可換だと言っても同じです。
$`\quad \xymatrix@C+1pc{
{|\mbf{Fam}|} \ar@/^1pc/[r]^-{\mrm{FamToRel}}
&{ \mrm{Mor}(\mbf{Rel}^\mrm{surj}) } \ar@/^1pc/[l]^-{\mrm{RelToFam}}
}\\
\quad \text{commutative }\In \mbf{SET}
`$
具体的に $`\mrm{FamToRel}`$ と $`\mrm{RelToFam}`$ を構成しましょう。だけど、名前がちょっと長いので次の略記の約束をします。
$`\text{For }F \in |\mbf{Fam}|\\
\quad {^\mrm{rel}F} := \mrm{FamToRel}(F)\\
\text{For }R \in |\mrm{Mor}(\mbf{Rel}^\mrm{surj})|\\
\quad {^\mrm{fam}R} := \mrm{RelToFam}(F)
`$
$`{^\mrm{rel}F}`$ の定義は以下のとおり。
$`\text{For }F : X \to |\mbf{Set}| \In \mbf{SET}\\
\quad \mrm{dom}({^\mrm{rel}F}) := X\\
\quad \mrm{cod}({^\mrm{rel}F}) := \bigcup_{t\in X}F(t)\\
\quad {^\mrm{rel}F} := \{
(x, y)\in X\times \bigcup_{t\in X}F(t) \mid y\in F(x)
\}
`$
これが全射的であるとは、次のことです。
$`\quad \forall y\in \bigcup_{t\in X}F(t).\exists x.\, (x, y)\in {^\mrm{rel}F}`$
$`y\in \bigcup_{t\in X}F(t)`$ ということは、適当な $`x\in X`$ が在って、$`y\in F(x)`$ が成立していることなので、その $`x`$ に対して $`(x, y)\in {^\mrm{rel}F}`$ は成立しています。よって、$`{^\mrm{rel}F}`$ は全射的です。
次に、$`{^\mrm{fam}R}`$ の定義は以下のとおり。
$`\text{For }R \in \mrm{Pow}(A \times B)\\
\quad \base{({^\mrm{fam}R})} = \mrm{dom}({^\mrm{fam}R}) := A\\
\quad {^\mrm{fam}R} := \lambda\, x\in A.\{y\in B\mid (x, y)\in R \}
`$
これらが互いに逆であることは、次が成立することです。
$`\text{For }F : X \to |\mbf{Set}| \In \mbf{SET}\\
\quad {^\mrm{fam}({^\mrm{rel}F})} = F\\
\text{For }R \in \mrm{Pow}(A \times B)\\
\quad {^\mrm{rel}({^\mrm{fam}R})} = R
`$
これは、定義に従って確認できます。
関係圏には転置が備わっているので、「ファミリー ←→ 全域関係」という同型も作れます。次の図式を可換にする $`\mrm{T}\H\mrm{FamToRel}`$ を考えます。
$`\quad \xymatrix{
{|\mbf{Fam}|} \ar[rr]^-{\mrm{FamToRel}} \ar[dr]_-{\mrm{T}\H\mrm{FamToRel} }
&{}
&{ \mrm{Mor}(\mbf{Rel}^\mrm{surj}) } \ar[dl]^-{\mrm{T} }
\\
{}
&{\mrm{Mor}(\mbf{Rel}^\mrm{tot})}
&{}
}\\
\quad \text{commutative }\In \mbf{SET}
`$
この $`\mrm{T}\H\mrm{FamToRel}`$ とその逆写像 $`\mrm{T}\H\mrm{RelToFam}`$ は、「ファミリー ←→ 全域関係」の同型を与えます。
$`\quad \xymatrix@C+1pc{
{|\mbf{Fam}|} \ar@/^1pc/[r]^-{\mrm{T}\H\mrm{FamToRel}}
&{ \mrm{Mor}(\mbf{Rel}^\mrm{tot}) } \ar@/^1pc/[l]^-{\mrm{T}\H\mrm{RelToFam}}
}\\
\quad \text{commutative }\In \mbf{SET}
`$
感触としては、「ファミリー ←→ 全域関係」の同型のほうが使いやすそうです。
関係の包含関係をファミリー射として表現する
この節はオマケみたいなものなんで、手短に説明します。
次のような問題を考えます。
- $`\mbf{Rel}^\mrm{surj}`$ または $`\mbf{Rel}^\mrm{tot}`$ を、2-射（関係の包含関係）を含めて $`\mrm{Fam}`$ に埋め込めるか？
- 埋め込めたとして、埋め込み像を $`\mrm{Fam}`$ のなかでどのように特徴付けられるか？
- 埋め込み像を特徴付けられた〈識別できた〉として、埋め込み像からもとの圏を再現できるか？
- 部分圏 $`\mbf{Rel}^\mrm{surj}`$ または $`\mbf{Rel}^\mrm{tot}`$ ではなくて、全体圏 $`\mbf{Rel}`$ に対して同様なことはできるか？
この問題が解ければ、“関係圏とファミリー達の圏のあいだの関係”はよりハッキリすることになります。とっかかりとして、$`\mbf{Rel}^\mrm{surj}`$ の2-射の集合を、$`\mbf{Fam}`$ の1-射の集合のなかに埋め込んでみます。
$`\mbf{Rel}^\mrm{surj}`$ 側に次の状況を考えます。
$`\quad \alpha :: R \twoto S : A \to B \In \mbf{Rel}^\mrm{surj}`$
図式で描くなら：
$`\quad \xymatrix@+1pc{
A \ar@/^1pc/[r]^R \ar@/_1pc/[r]_S
\ar@{}[r]|{\alpha \Downarrow}
&B
}\\
\quad \In \mbf{Rel}^\mrm{surj}
`$
$`R`$ と $`S`$ は、前節の $`\mrm{RelToFam}`$ で $`\mbf{Fam}`$ の中に送ります。$`\alpha`$ もうまく $`\mbf{Fam}`$ 内に送り込めたとすれば、$`\mbf{Fam}`$ 側に次の状況ができます。
$`\quad {^\mrm{fam}\alpha} : {^\mrm{fam}R} \to {^\mrm{fam}S} \In \mbf{Fam}`$
$`\varphi := {^\mrm{fam}\alpha}`$ と置くと、ファミリーのあいだの射 $`\varphi`$ のベースパートは次の形をしていることが分かります。
$`\quad \base{\varphi} = \id_A`$
ファミリー側に移っても、$`R`$ と $`S`$ が同じ域を共有していた事実は保存されます。
$`\alpha`$ の実体は集合の包含関係 $`R\subseteq S`$ でした。包含関係をファイバーごとに切り刻むと、包含写像の族が得られます。それが $`\varphi`$ のファイバーパートを与えます。
$`\text{For }x\in A\\
\quad {\varphi^\#}_x : ({^\mrm{fam}R})(x) \hookrightarrow ({^\mrm{fam}S})(x) \In \mbf{Set}
`$
先に挙げた問題は解けてませんが、今日はここらへんにしておきます。
おわりに
次のような圏はよく使います。
- $`\mbf{Set}`$ ： 集合圏〈集合達の圏〉
- $`\mbf{Rel}`$ ： 関係圏〈関係達の圏〉
- $`\mbf{Partial}`$ ： 部分関数達の圏
- $`\mbf{ND}`$ ： 非決定性関数達の圏
- $`\mbf{SPAN}`$ ： 集合圏内のスパン達の圏（ホムセットが大きい集合になり、結合は一意的ではない）
上記の圏はすべて、対象集合が“集合達の大きい集合”です。他に、対象が集合ではありませんが、次の圏も重要です。（いずれも集合圏から“構成された圏”です。）
- $`\mrm{Arr}(\mbf{Set})`$ ： 集合圏のアロー圏（可換四角形を射とする圏）
- $`\mrm{TW}(\mbf{Set})`$ ： 集合圏の捻じれアロー圏〈twisted arrow category〉
- $`\mbf{Fam} = \mrm{Fam}(\mbf{Set})`$ ： ファミリー達の圏
これらの圏達はてんでんばらばらに存在するわけではなくて、相互に関連しています。今回は特に、$`\mbf{Rel}`$ と $`\mbf{Fam}`$ の関連を探ったわけです。他の関連性も調べると、“圏達が形成する社会”の構造が見えてくるでしょう。
