計算モデルに関しては、集合圏よりむしろ便利な圏Relを紹介し、Relと似た性質を持つ圏の構成法を探ってみます。
内容：
- 関係圏の紹介
- 関係圏みたいな圏
- スパンの圏
- 集合圏のスパン圏と関係圏
関係圏の紹介
AとBが集合だとして、AとBのあいだの（二項）関係とは、A×Bの部分集合Rのことです。(a, b)∈R のことを、「aとbは関係Rにある」といい、aRb のように書くこともあります。aRb という書き方は、a≦b のように、関係を二項中置演算子の形式で表現したものです。
AとBのあいだの関係の全体を Rel(A, B) としましょう。関係の定義から、Rel(A, B) = Pow(A×B) （Powはベキ集合）です。AとAとのあいだの関係ΔAを次のように定義します。
- ΔA = {(a, a)|a∈A}
あるいは：
- (a, b)∈ΔA ⇔ a = b
つまり、ΔAは集合A上のイコール関係に他なりません。記号としてデルタを使ったのは、外延としては対角集合となるからです（習慣的に対角はΔと書きます）。当然ながら、ΔA∈Rel(A, A) です。
RがAとBのあいだの関係、SがBとCのあいだの関係のとき、これら2つの関係の結合（合成） T = R;S を次のように定義します。
- T = {(a, c)∈A×C | (a, b)∈R かつ (b, c)∈S となる b∈B が存在する}
この結合は、0, 1 だけを成分とする行列の掛け算を使うとうまいこと説明できますが、今日は割愛します。
Rel(A, B) の A, B をすべての集合に渡って動かして、ΔA達（恒等関係）と関係の結合「;」を一緒に考えると圏になります。Rel(A, B) という書き方は圏Relのホムセットのつもりだったのです；Rel(A, B) = HomRel(A, B) 。
関係圏みたいな圏
集合圏Setの射は、全域的で一意的な値を持つ関数（写像）です。コンピュータで計算する関数は全域的とは限らないし、非決定性を考慮したいときもあります。関係圏Relの射（関係）は、部分関数や非決定性関数と解釈できるので、計算のモデルには集合圏Setより関係圏Relのほうが使いやすいことが多いですね。
さて、一般に圏Cがあったとき、「Set ： Rel ＝ C ： ？」という“比例式”を満たすような圏（「？」に当てはまる圏）が欲しいときがあります（実は今欲しい状況）。圏Cをベースにして、Cを含んでいて（Cを埋め込めて）Cより柔軟で使いやすい圏を構成する問題となります。
部分集合と述語（真偽値への関数）との対応関係により、Pow(A) = Set(A, {true, false}) となります。よって、Rel(A, B) = Set(A×B, {true, false}) です。これを真似て、D(A, B) = C(A×B, Ω) のような定義が考えられます。
しかし、C(A×B, Ω) と定義できるためには、もとの圏Cに直積（または直積に類似したモノイド積）と真偽値のように振舞う対象Ωが必要です。Cにトポスに近い構造を要求することになって、ちょっとキビシイ； 適用範囲が狭すぎるのです。
スパンの圏
別な方向で考え直すことにします。圏C内で、A←X→B という形を（Cの）スパン（span）と呼びます。アスキーアート風にスパンを次に図で表すことにします。
X
／ ＼
A B
矢印は付いてませんが、斜線は f:A←X, g:X→B という2本の射を表しています。fとAをスパンの左足、gとBを右足、Xをボディと呼んでいる例を見たことがありますが、一般的な用語ではないでしょう。でも、比喩的で分かりやすいのでこの言葉を使います。
A, B∈|C| として、A, Bを左右の足とするスパンの全体を Span(A, B) と書くことにします。ちゃんとCも添えるなら、SpanC(A, B) とか Span(C)(A, B) とかですが、Cは省略することにします。
圏Cが小さくないとき、Span(A, B)も小さくない（集合とはならない）可能性があり、ちょっとヤバイです。サイズの問題は気にしない（あるいは、圏Cが小さいときだけ考える）にしても、後の都合から、Span(A, B) 内に同値関係を入れて割り算しておきます。
x, x'∈Span(A, B)、つまり x = (A←X→B), x' = (B←X'→C) のとき、XとX'のあいだに同型があって、左右の足との可換性が成立するとき、x〜x' とします。Span(A, B)/〜 を再び Span(A, B) と書くことにします。
特殊なスパンδA を A←A→A で、左右の足が idA のモノとして定義します。これが恒等スパンとなります。
x∈Span(A, B), y∈Span(B, C)、つまり x = (A←X→B), y = (B←Y→C) のとき、xとyの結合 x;y を定義することにします。まずは次の図をみてください。
Z
／ ＼
X Y
／ ＼ ／ ＼
A B C
与えられた (A←X→B) と (B←Y→C) に対して、四角形ZXBYがプルバック（ファイバー積）になるようにします。もちろん、そう出来るためには、もとの圏Cがプルバックを持つ圏でないといけません。今、泥縄にCはプルバックを持つと仮定します。
もとの圏Cがプルバックを持つなら、x = (A←X→B), y = (B←Y→C) に対してこれらの結合 z = x;y を、Zから左右に落ちる斜線を左右の足とするスパンとして定義できます； z = x;y = (A←Z→C) 。
Zは一意的には決まりませんが、同型を除いて（up to isoで）一意なので、同値関係〜で割り算すれば一意的だと言えます。これで、スパンの結合が確定しました。
プルバックに関する性質を使うと、恒等スパンと今定義したスパンの結合により、Span = Span(C) が圏であることがわかります。
集合圏のスパン圏と関係圏
Set ： Rel ＝ C ： Span(C) とは言えないにしても、Set ： Rel ≒ C ： Span(C) くらいは成立している感じがします。その状況証拠を挙げましょう。
集合圏Setにはプルバックがあるので、Span(Set) を作れます。Rel = Span(Set) には（イコールを圏同値の意味に解釈しても）なりませんが、Rel を Span(Set) のなかに埋め込むことができます。
R⊆A×B だったので、2つの射影 π1:A×B→A, π2:A×B→B と組み合わせると、(A←R→B) が作れます。これはスパンですね。恒等関係 ΔA は恒等スパン δA にマップされます。集合圏におけるプルバックの定義を使って計算すると、関係の結合がスパンの結合と一致することを確認できます（練習問題）。
以上の手順で、Rel→Span(Set) の埋め込み関手を構成できます。これで、Span(Set)は、Relよりは大きい圏であることが分かりました。Span(Set) の射（スパンです）に何か条件を付けて、Span(Set) の広い部分圏（{broad, wide} subcategory）としてRelを特徴付けることはできないでしょうか？ そのような条件があれば、一般のSpan(C)のなかで扱いやすい部分圏を定義することができるかも知れません。できないかも知れません。
