続報・役に立ちそうだが奇妙な圏： コレ、使えそう

昨日、「役に立ちそうだが奇妙な圏」という記事を書きました。基点付き集合（pinted set）を対象として、基点を基点に移すような関係を射とする圏PtRelを考え、さらに全域な関係だけを選んだ広い部分圏TotPtRelを作ります。この圏TotPtRelが役に立ちそうなんだけど、なんだか奇妙だ、という話でした。

今日になって思ったことは； この圏、そんなに変じゃないかも。

内容：

1. 変なところ
2. 足し算を考えなおす
3. 基点＝ボトム の直感的な意味
4. 積を和に写す標準的射 W
5. その他の標準的な射達
6. Wと足し算の性質

変なところ

変な感じを端的に表しているのは、この圏の End({1, ⊥}) です。これは三元集合で、掛け算（射の結合）と足し算（合併）を持ち、足し算も掛け算もベキ等な半環（足し算の単位律を除外）です。掛け算の吸収元があり、それは圏の零射なのに、足し算の単位元じゃありません。つまり、掛け算の吸収元は、圏論の意味で零だけど、足し算の零じゃない、と。

End({1, ⊥}) を三値論理の真偽値だと思うこともできそうですが、相当に変なモノですね。真偽じゃなくて、「真、沈黙、ハチャメチャ」の三値って感じ。ウーン、奇妙だ。

全域性の制限を取っ払って、PtRelならば、R:A→B が R(x) = {} （空集合）を認めるので、⊥以外の値は空である射が存在します。この射（射は関係です）を空な射（(⊥, ⊥)だけは含まれる）と呼ぶと、空な射は合併演算∪の単位元（中立元）になります。

しかし、PtRelには始対象も終対象も存在しません。当然に零対象、零射もありません。圏論の意味の零対象／零射をとるのか、足し算の単位元としての零をとるのか、どっちの「零」が欲しいのか？ という選択になります。「両方」と答えるわけにはいきません。

足し算を考えなおす

結局、「足し算＝集合の合併」と考えると、足し算の単位元がないみたいです、ムーー … … いや、待てよ。「足し算＝集合の合併」と決めてかかる必要はありませんよね。合併以外の足し算があってもいいわけです。圏TotPtRefでは、「積」も2つあって、A×B と A*B としていました。どちらか一方だけに制限する必要はないし、片一方だけでは不便です。であるなら、足し算だって複数あるかも。

圏TotPtRelの射は、実体としては直積の部分集合ですが、解釈は計算処理なので f, g などの小文字で表すことにします。計算処理をプロセスとも呼ぶことにすると（用語「プロセス」にさして深い意味はありません）、足し算 f + g のインフォーマルな意味は、2つのプロセスfとgを同時にスタートさせ、早く終わったほうの結果を採用することだとします。

このインフォーマルな解釈を素直に関係の言葉で表現すると次のようになります。

• f + g := Δ;(f×g);W;∇

もう少し正確に（それゆえにウザッタク）書くと、2つの射 f, g:A→B in TotPtRel に対して

• f + g := Δ^×_A;(f×g);W_B,B;∇^#_B

ここで：

• Δ^×_A:A→A×A … 積に関する対角
• W_B,B:B×B→(B # B) … 積を和に写す標準的射
• ∇^#_B:(B # B)→B … 和に関する余対角

Wという射が存在することがポイントです。

基点＝ボトム の直感的な意味

Wの定義をする前に、「基点＝ボトム」について説明しておきます。圏TotPtRelの対象は基点付き集合で、対象Aに基点⊥_Aが含まれます。「役に立ちそうだが奇妙な圏」と同じ記号法で、

• A_○ := A - {⊥_A} （Aから基点を除いた集合）

とします。Aは空集合ではあり得ませんが、A = {⊥_A} のときA_○は空となります。A_○は説明や計算の途中で出てくるだけで、圏TotPtRelの対象ではありません。

Aに含まれる⊥_Aは、「A_○の値を期待して待ったが、なんの値も得られなかった」ことを表す特殊な値です。例えば、Boolean = {true, false, ⊥_Boolean} とすると、⊥_Booleanは、「trueまたはfalsを期待して待ったが、なんの値も得られなかった」ときの“値”です。どのくらい「待つ」かというと「無限」です。つまり、プロセスがウンともスンとも言わずに無限走行しているのを「無限に待った」結果が⊥です。

任意の f:A→B in TotPtRel には、f(⊥_A) = {⊥_B} という制限が付いています。これは、プロセスfが入力を無限に待つなら、後続するプロセスも無限に待つ（動けない）ことを意味します。この条件がいつでも適切かどうかは分かりませんが、プロセスが直列パイプラインに繋がれているときは、現実を表すモデル化だと思えます。

積を和に写す標準的射 W

僕が圏TotPtRelを考えた動機でもあり、この圏の一番便利だと思えるところは、任意の対象A, Bに対して、W_A,B:A×B→(A # B) という射が標準的（canonical）に存在することです。Wの直感的な意味は、「2つの値の早く来たほうを採用する」という操作です。

A×B は普通の直積で、A×B = A_○×B_○ + A_○×{⊥_B} + {⊥_A}×B_○ + {(⊥_A, ⊥_B)} と直和（普通の集合の直和）に分解できます。A # B は、A + B に含まれる2つのボトム、⊥_Aと⊥_Bを同一した集合で、A # B = A_○ + B_○ + {⊥} と書けます。W:A×B→(A # B) は場合分けで定義できて：

1. W(a, b) = {a} + {b} (a∈A_○、b∈B_○)
2. W(a, ⊥_B) = {a} (a∈A_○)
3. W(⊥_A, b) = {b} (b∈B_○)
4. W(⊥_A, ⊥_B) = {⊥}

W = W_A,B のパートナー（逆や転置ではない）と言える V_A,B:(A # B)→A×B も自然に定義できますが、今回は使いません。Wは、来ない相手を無限に待つことを避ける効果があり、タプルに対するある種の非正格評価方式となります。

その他の標準的な射達

Δ^×_A、∇^#_A、それと2つの対称 σ^×_A,B、σ^#_A,B についても簡単に説明します。

Δ^×_A:A→A×A は、直積の対角射で、Δ(a) = {(a, a)} として定義されます。∇^#_A:(A # A)→A は、直和の余対角射で、A_○の2枚のコピーを重ねあわせて、⊥は⊥に対応させます。TotPtRelでは、直和の対角 Δ^#_A:A→(A # A) も存在しますが、今回は使いません。

σ^×_A,B:A×B→B×A、σ^#_A,B:(A # B)→(B # A) はそれぞれ、直積×（圏の直積ではない）と直和#（これは圏の直和）に関する対称です。どちらも成分を入れ替える射です。

対角、余対角は次の基本的な性質を持ちます。

• f;Δ^× = Δ^×;(f×f)
• ∇^#;f = (f # f);∇^#

対角、余対角は次の意味で余可換／可換です。

• Δ^×;σ^× = Δ^×
• σ^#;∇^# = ∇^#

Wと足し算の性質

足し算の定義をもう一度出すと（簡略に記します）：

• f + g := Δ;(f×g);W;∇

Δの性質から、左からの分配性は明らかです。足し算が可換なこともすぐ分かります。結合律、零射θ_A,Bに対する単位律、ベキ等律も実際に計算をして示すことができます。

上記の計算の法則性は足し算の法則ですが、w_A = W_A,A;∇^#_A と定義すると、w_A:A×A→A はA上の二項演算となり、この演算wの性質ともみなせます。

1 := {⊥} と書くことにして； w_A:A×A→A は、零射 θ_1,A:1→A を単位として、圏TotPtRelのなかで可換ベキ等なモノイドとなります。足し算は、wを使って f + g := Δ;(f×g);w と定義されるので、wの性質を引き継ぐことになるのです。注目すべきは、Wやwなのです。

w⁽ⁿ⁾を、二項演算wから作った公平な（unbiased）n項演算とします。w⁽ⁿ⁾:Aⁿ→A in TotPtRel を、具体的に書き下してみると、Aⁿ→Pow(A_○) という演算とみなせることが分かります。この演算は、渡されたタプル (a₁, ..., a_n) をもとにして、ボトムを除いた成分からなる集合を作る操作です。これは、n個のプロセスを同時に走らせ、その結果を（順序を無視して）寄せ集めたときに得られる可能性の集合です。一部のプロセスがハング（無限走行）すれば、値の欠損が生じます。

Wやw、それとWから定義された足し算の性質を調べてみると、圏TotPtRelはそんなに奇妙じゃない気がしてきました。使えんるんじゃないのかな、コレ。