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

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

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

参照用 記事

二項関係と非決定性関数

二項関係と非決定性関数は、事実上同じものなので同一視してしまうこともあります。が、導入時の定義は異なるし、印象〈メンタルモデル〉も違うように思えます。なぜ「事実上同じもの」なのかを確認しておいたほうが良さそうです。

二項関係と非決定性関数を利用する実例も紹介します。$`\newcommand{mrm}[1]{\mathrm{#1}}
\newcommand{\Iff}{\Leftrightarrow}
\newcommand{\In}{\text{ in }}
\newcommand{\id}{\mathrm{id}}
\newcommand{\Imp}{\Rightarrow}
%`$

内容:

関係の圏

二項関係を単に関係と呼びます。関係の圏 $`{\bf Rel}`$ は、集合を対象として、集合のあいだの関係を射とする圏です。対象の類とホムセットを書くと:

  • $`|{\bf Rel}| := |{\bf Set}|`$
  • $`\text{For }A, B\in |{\bf Rel}|,\; {\bf Rel}(A, B) := \mrm{Pow}(A\times B)`$

ここで、

  • $`{\bf Set}`$ は集合圏、
  • $`\mrm{Pow}(-)`$ はベキ集合です。

$`R\in {\bf Rel}(A, B),\, S\in {\bf Rel}(B, C)`$ に対して、その結合〈composition〉 $`R;S`$ (図式順)は次のように定義します。

  • $`\text{For }x\in A, z\in C,\; (x, z)\in (R;S) :\Iff \exists y\in B.(x, y)\in R \land (y, z) \in S`$

$`x`$ と $`z`$ のあいだを中継する要素 $`y`$ があれば、$`x`$ と $`z`$ は結合された関係により“関係する”とみなすわけです。

恒等射は次のようです。

  • $`\text{For }x\in A,\; (x, y)\in \id_A :\Iff x = y`$

習慣により、$`\id_A`$ を $`\Delta_A`$ とも書きます。$`\id_A`$ は $`A`$ の対角集合〈diagonal set〉だからです。大文字デルタを使っていても、マルコフ圏などのコピー射とは違うので注意してください。

以上に定義した、対象の類、ホムセット、結合、恒等射が、全体として圏を構成することは確認できます(やってみてください)。

非決定性関数の圏

非決定性関数の圏を $`{\bf ND}`$ と書きます。その対象の類とホムセットを書くと:

  • $`|{\bf ND}| := |{\bf Set}|`$
  • $`\text{For }A, B\in |{\bf ND}|,\; {\bf ND}(A, B) := {\bf Set}(A, \mrm{Pow}(B))`$

$`f\in {\bf ND}(A, B),\, g\in {\bf ND}(B, C)`$ に対して、その結合〈composition〉 $`f;g`$ (図式順)は次のように定義します。

  • $`\text{For }x\in A,\; (f;g)(x) := \bigcup_{y\in f(x)}g(y)`$

恒等射は次のようです。

  • $`\text{For }x\in A,\; \id_A(x) := \{x\}`$

以上に定義した、対象の類、ホムセット、結合、恒等射は、全体としてやはり圏を構成します。

圏同型を与える関手

圏 $`{\bf Rel}`$ と圏 $`{\bf ND}`$ が圏同型なことは、直感的に明らかそうですが、念の為に圏同型を与える関手を定義しましょう。

まず、関手 $`\mrm{nd}:{\bf Rel}\to{\bf ND} \In {\bf CAT}`$ を次のように定義します。

  • $`\text{For }A\in |{\bf Rel}|,\; \mrm{nd}(A) := A`$
  • $`\text{For }A, B\in |{\bf Rel}|, R\in {\bf Rel}(A, B),\; \mrm{nd}(R) := \lambda\, x\in A.\{y\in B\mid (x, y)\in R\}`$

これが実際に関手になることも確認できます。

逆向きの関手 $`\mrm{rel}:{\bf ND}\to{\bf Rel} \In {\bf CAT}`$ は次のようです。

  • $`\text{For }A\in |{\bf ND}|,\; \mrm{rel}(A) := A`$
  • $`\text{For }A, B\in |{\bf ND}|, f\in {\bf ND}(A, B),\; \mrm{rel}(f) := \{(x, y)\in A\times B\mid y \in f(x)\}`$

$`\mrm{rel}`$ も関手で、さらに次が成立することもそれほど手間なく示せます。

$`\text{For }R:A \to B \In {\bf Rel}\\
\quad \mrm{rel}(\mrm{nd}(R)) = R\\
\text{For }f:A \to B \In {\bf ND}\\
\quad \mrm{nd}(\mrm{rel}(f)) = f`$

結局、2つの圏 $`{\bf Rel},\,{\bf ND}`$ は、対象上で恒等〈identity-on-objects〉な互いに逆な関手 $`\mrm{nd},\,\mrm{rel}`$ で結ばれています。これにより、2つの圏は同一視可能です。

付加的な構造

関係の圏 $`{\bf Rel}`$ は、単なる圏以上の構造を持ちます。

  1. 各ホムセットには順序がある。
  2. 集合の直和から誘導されるモノイド積を持つ。
  3. 集合の直積から誘導されるモノイド積を持つ。
  4. 射〈関係〉を転置することができる。

これらの付加的な構造達は土台の圏の構造と協調し、また付加的構造どおしも互いに協調しています。

圏 $`{\bf ND}`$ は 圏 $`{\bf Rel}`$ と圏同型なので、非決定性関数の圏 $`{\bf ND}`$ にも関係の圏 $`{\bf Rel}`$ と同じ付加的構造を持たせることができます。

射のあいだの順序と射の転置を別な記号で独立に定義しておきましょう。

圏 $`{\bf Rel}`$ において:

  • $`R\subseteq S`$ は集合としての包含関係。
  • $`\text{For }R:A \to B \In {\bf Rel},\; R^\top := \{(y, x)\in B\times A\mid (x, y)\in R\}`$

圏 $`{\bf ND}`$ において:

  • $`\text{For }f, g:A \to B \In {\bf ND},\; f\sqsubseteq g :\Iff \forall x\in A.\, f(x) \subseteq g(x)`$
  • $`\text{For }f:A \to B \In {\bf ND},\; f^\dashv := \lambda\, y\in B. \{x \mid y \in f(x) \}`$

独立に定義しましたが、$`\mrm{nd},\, \mrm{rel}`$ で互いに移り合います。

  1. $`R\subseteq S \Imp (\mrm{nd}(R) \sqsubseteq \mrm{nd}(S) \In {\bf ND})`$
  2. $`f\sqsubseteq g \Imp (\mrm{rel}(f) \subseteq \mrm{rel}(g) \In {\bf Rel})`$
  3. $`\mrm{nd}(R^\top ) = \mrm{nd}(R)^\dashv \In {\bf ND}`$
  4. $`\mrm{rel}(f^\dashv ) = \mrm{rel}(f)^\top \In {\bf Rel}`$

集合の直積/直和から誘導されるモノイド積に関しても、自然な定義を独立に導入しても、それらは $`\mrm{nd},\, \mrm{rel}`$ で互いに移り合います。

実例:アクセス制御

関係と非決定性関数は本質的には同じで、違いは心理的〈認知的〉なものだと言ってもいいでしょう。同一のモノゴトを、関係で記述しても非決定性関数で記述しても同値です。実例として、アクセス制御を関係で記述してみましょう。非決定性関数としての解釈にも触れます。

人の集合と、名前が付いているデータ〈情報資源〉の集合を考えます。人の集合を $`\mrm{P}`$ 、データを識別する名前〈識別子 | ラベル〉の集合を $`\mrm{N}`$ とします。名前付きデータに対する操作はCRUD(Create, Read, Update, Delete)とします。操作(を表す記号)の集合は $`\mrm{O} = \{\mrm{C}, \mrm{R}, \mrm{U}, \mrm{D}\}`$ です。

人 $`p\in \mrm{P}`$ が、$`n\in \mrm{N}`$ で識別されるデータに、操作 $`o\in \mrm{O}`$ をしていいかどうかは、述語(ブール値の関数)$`\mrm{allow}`$ で決まるとしましょう。

$`\quad \mrm{allow} : \mrm{P}\times \mrm{N}\times \mrm{O} \to \{\mrm{True}, \mrm{False}\} \In {\bf Set}`$

集合 $`\mrm{Allow}`$ を次のように定義します。

$`\quad \mrm{Allow} := \{(p, n, o) \in\mrm{P}\times \mrm{N}\times \mrm{O} \mid \mrm{allow}(p, n, o) = \mrm{True} \}`$

集合 $`\mrm{Allow}`$ は三項関係と言えますが、圏 $`{\bf Rel}`$ は二項関係の圏なので、集合 $`\mrm{Allow}`$ を二項関係とみなしましょう。その“みなし”の方法はいくつかあります。以下で、$`{\bf 1}`$ は単元集合 $`{\bf 1} = \{*\}`$ です。

  1. $`\mrm{Allow}_0 \in {\bf Rel}({\bf 1}, \mrm{P}\times \mrm{N}\times \mrm{O})`$
  2. $`\mrm{Allow}_1 \in {\bf Rel}(\mrm{P}, \mrm{N}\times \mrm{O})`$
  3. $`\mrm{Allow}_2 \in {\bf Rel}(\mrm{P}\times \mrm{O}, \mrm{N})`$
  4. $`\mrm{Allow}_3 \in {\bf Rel}(\mrm{N}\times \mrm{O}, \mrm{P})`$
  5. その他

色々な可能性がある背景は、対称(直積順序の入れ替え)、カリー化/反カリー化、転置による“ホムセットの同型”があるからです。

  • $`{\bf Rel}(A\times B, C) \cong {\bf Rel}(B\times A, C)`$ (対称)
  • $`{\bf Rel}(A\times B, C) \cong {\bf Rel}(A, C\times B)\cong {\bf Rel}(B, A \times C)`$ (カリー化/反カリー化)
  • $`{\bf Rel}(A, B) \cong {\bf Rel}(B, A)`$ (転置)

ここで、関係を非決定性関数と解釈してみると、上記の $`\mrm{Allow}_i\,(i = 0, 1, 2, 3)`$ は次のように解釈されます。

  1. 入力 $`*`$ に対して、アクセスを許可されている三つ組 $`(p, n, o)`$ をすべて列挙する。
  2. 入力 $`p`$ に対して、人 $`p`$ がアクセス許可されているデータ名と操作のペア $`(n, o)`$ をすべて列挙する。
  3. 入力 $`(p, o)`$ に対して、人 $`p`$ が操作 $`o`$ を許可されているデータ名 $`n`$ をすべて列挙する。
  4. 入力 $`(n, o)`$ に対して、名前 $`n`$ のデータに操作 $`o`$ を許可されている人 $`p`$ をすべて列挙する。

各人に対してそれぞれアクセス許可を設定するのは面倒なので、人に対してロール(例えば、管理者、一般ユーザー、ゲスト)を割り当てて、ロールに対してアクセス許可を設定するとしましょう。一人の人に複数のロールを与えても、まったくロールを与えないでもいいとします。すると、ロール割り当ては次の関係になります。

$`\quad \mrm{Roll}:\mrm{P} \to \{\mrm{Admin}, \mrm{User}, \mrm{Guest}\} \In {\bf Rel}`$

新たに、$`\mrm{Allow'}`$ は次のようにします。

$`\quad \mrm{Allow'}:\{\mrm{Admin}, \mrm{User}, \mrm{Guest}\} \to \mrm{N}\times \mrm{O} \In {\bf Rel}`$

関係の圏の結合を使えば、各人ごとのアクセス権限を計算できます。

$`\quad \mrm{Roll};\mrm{Allow'} : \mrm{P} \to \mrm{N}\times \mrm{O} \In {\bf Rel}`$

名前付きデータの側を、ファイルシステムのフォルダーやデータベースのテーブルのようにグループ化するとか、データにメタデータ属性を付けて属性によるアクセス制御をするとか、いろいろな方法が考えられますが、いずれにしても $`{\bf Rel}`$ または $`{\bf ND}`$ で定式化して計算できます。