トリビアルが役に立つ話 -- トレースがそのままスターになる
[追記]このエントリー、かなり間違いが含まれる。が面白いところもある。明かな間違いは消し線付ける。[/追記]
Cは単一対象の圏だとする。つまり、|C| = {*}で、Cは結合;に関してモノイド。Cの対象には *×* = * というトリビアルな積を入れて、Cはモノイド圏になっているとする。つまり、Cは;と×という2つのモノイド演算を持つ代数系。積×は対称だとするとこれは可換演算。さらにCにトレースが入っているなら、f:*→*は、f:*×*→*×* とみなして、Tr(f):*→* となるから、TrはC上にwell-definedな単項演算とみなせる。
[追記]モノイダルモノイドにエクマン/ヒルトンの手法を適用して、モノイド積は結合と一致する。よって、cup-plus代数のcupはモノイド積ではない。そうじゃなくて、AbMon豊饒化されたhom-setだと考えて、そのAbMon演算がcupってことだな。[/追記]
別なトレース付き圏Eがあって、関手L:E→Cがモノイド関手であり、かつトレースも保つとする。対象のレベルでは|E|→{*}はトリビアルになるので、g∈Eがどんな射であっても、L(Tr(g)) = Tr(L(g)) のようになる。
さて、こんな定式化が何の役にたつのか? 形式言語理論のポンプの補題やパリクの定理を自然に証明できる。以下に、ホッピングボール・マシンの文脈で語ってみる。
Gは境界付き有限グラフとすると、Gは適当な境界付きアサイクリックグラフH(または、被覆有限ヘッジH)に対してTr(H)の形に書ける。これは、(辺に0, 1でラベルした)境界付き有限グラフの圏を、直和とルーピングでトレース付き圏と考えれば、Gの構造に関して帰納法により証明できる。この帰納法が使えるのは、この圏が自由トレース付き圏だから。証明を簡略化したいなら、初歩的圏の範囲で定式化するとよい。
G境界を繋ぐすべての道(軌道)に対して、その長さとなる自然数の集合をL(G)とする。L(G)はPow(N)を台とするエキゾチック代数だが、∪をモノイド積、+を結合としたモノイド圏ともみなせる。クリーネスターがこの圏のトレースを与えて、結局Pow(N)をトレース付き圏だとみなせる。
関手Lはトレース付きモノイド関手だから、G = Tr(H) をL(G) = Tr(L(H)) に移す。アサイクリックグラフとNの有限集合が対応するから、Tr(L(H))は有限集合のクリーネスターになる。あとは、有限集合のクリーネスターがどんな集合かを見ればよい。
以上、細かい点でイイカゲンなのだが、L(G)=Length(Path(G)) をトレース付きモノイド関手とみなすところがミソ。すごく具体的に見るところは、Nの部分集合で、等差数列の有限合併(準アフィン集合)で書けるものは、有限部分を除いて周期的な集合であること; それと、有限集合のクリーネスターが等差数列の有限合併の形をしていること。
ここらへんの具体的観測の背後には、NやNkという空間の準アフィン集合が実は正規集合であり、可換クリーネ代数の元でもある事実がある。
僕は今まで、単一対象のクリーネ圏にはモノイド積が入らない(つうか、入れてもしょうもない)と思っていたが、トリビアル積なら入るし、これがすごく役に立つようだ。トリビアル積はデカルト積や余デカルト積ではないが、それでもかまわない。トレース付きデカルト圏の範囲で考えるのではなくて、単に“トレース付きモノイド圏の圏”で考えればよい。
トレースからスターに至る道として、 f* = Tr(∇;f;Δ) 以外にも、f* = Tr(f) というトリビアルな手もあったわけだ。
一般のラベル付き遷移系に関して、ポンプの補題/パリクの定理の完全に圏論的な証明もできそうだ。[追記]ポンプの補題とパリクの定理では事情がかなり異なる。[/追記]