圏のloopingと不動点 - (保存用) 檜山正幸のキマイラ飼育記メモ編

なんか、思惑とは違った展開だな -- 別にいいけど。状況をまとめておく。

まず、ElgotオペレータとConwayオペレータは、本質的に同じことがわかった。Elgotオペレータが余デカルト（な対称モノイド）圏、Conwayオペレータがデカルト圏に作用するもので、お互いに双対になっている。

デカルト圏で、Conwayオペレータ ⇔ トレース
余デカルト圏で、Elgotオペレータ ⇔ トレース

結局は、カザネスク／ステファネスク／ハイランド／長谷川の定理に集約される。この定理の副産物として、X⁺ = (1 + X⁺)X に対応する補題があり、これがトランスデューサの構造をうまく表現して、f = <f_out, f_tran> という分解を与える。

Tr(f) = Δ;(A × (f_tran)^†);f_out = <A, (f_tran)^†>; f_out

双デカルト圏で、Tr(∇;f;Δ)がKleeneスターになると踏んでいたのだけど、これはどうも無理があるような気がする。というのも、Kleene代数／Kleene圏の条件には、Horn条件付き等式があって、完全に等式的ではない。双デカルト圏を（GSモノイダル圏のように）等式的に定義するなら、Horn式が示せる見込みはない。

しかし、双デカルト圏でも、不動点に関する条件と、sum-star equationは示せるような気がする。となると、End(X)はConway代数（ベキ等とは限らない半環）と思ったほうがよさそうだ。

そこで、Conway代数とKleene代数の差が問題になる。Zoltan Esik, Werner Kuichi "Rationally Additive Semirings"（http://www.brics.dk/RS/01/42/BRICS-RS-01-42.pdf）から要点を引き写しておく。

まずはConway代数（Conway半環）の等式：

(x + y)* = (x*y)*(x*)
(xy)* = 1 + x(yx)*y

行列に関するスターの定義は：

M = [a, b; c, d], M* = [α, β; γ, δ] として：

α = (a + bd*c)*
β = αbd*
γ = δca*
δ = (d + ca*b)*

このへんはKleene代数と特に変わりがない。([(a + bd*c)*, (a+bd*c)*bd*; (d+ca*b)*ca*, (d+ca*b)*])

さて、a∈End(A), b∈End(B), f:A→B に対して、次が条件を考える：

a;f = f;b ならば、a*;f = f;b*

この条件もEsik, Kuichiにあるのだが、これでKleene代数に近づけないか？

もうひとつのヒントは、Idempotency本P.114に載っていた partially additive category概念かな（その定義は、なんかイマイチな気がするが）。partially additive categoryでは、可算個の対象や、可算個の射に対して足し算ができるので、だいたいω極限がとれると思ってよい。これは、圏のなかで無限級数の計算ができるようなものだと思っていいだろう。すると、ω極限としてKleeneスターを作れるかもしれない。