「引き算と無限個の足し算は両立しない」で述べた内容は、一種のダメ定理(no-go theorem、ダメな定理のことではなくて、「そりゃダメだ、無理だわさ」と主張する定理)です。引き算(あるいは負の元)が自由に使える状況では無限和が使えないということです。積分や測度の概念が意味をなさない状況では、その代替手段として無限和を使いたいわけですが、無限和を使うと決めたなら、群や環は使えません。代わりにモノイドや半環を使うことが強制されます。
そこで、モノイドや半環、そして圏における無限和(総和、summation)について考えてみます。
内容:
準備
この話題の基本的なことは、「可算な総和可能性」で扱っています。「圏係数の行列の圏」にも類似の話題があります。必要なら参照してください。今回の記事と上記の過去記事では、用語、記号法、定義の記述などを少し変えたところがありますが、ささいな違いです。
I, Jなどは添字(インデックス)の集合とします。Xがナニモノカだとして、写像 φ:I→X をIで添字付けられた族(I-indexed family)と呼び、(i∈I | φ(i)) のように書くことにします。φ(i) は φi と書くこともあります。
基数条件という概念は「形式言語理論のための代数」の「基数条件と総和可能性」で説明しています。基数κに対して、単にκ-総和可能と言ったら、それは (≦κ)-総和可能のことだとします。例えば、可算基数ωに対してω-総和可能は(≦ω)-総和可能の意味なので、高々可算の添字集合に関する総和可能のことです。ω-総和可能は最もよく使われる総和可能概念です。
可換モノイドの総和可能性
Mは可換モノイドとします。Mのモノイド演算は足し算で書き、単位元は0と書きます。χは基数条件として、添字集合Iは基数条件χを満たすとします。(i∈I | xi):I→M の総和を(それが存在するなら) Σ(i∈I | xi) と書きます。χ-総和を考える前提は次の状況です。
- 基数条件χを満たす任意の添字集合Iと族 x:I→M に対して、Mの要素 Σx = Σ(i∈I | xi) が対応している。
x:I→M に対して、{i∈I | xi ≠ 0}をxの台(support)と呼ぶことにします。無限和は有限和の拡張である必要があるので、対応 x|→Σx には次の条件を要求します。
この条件「有限帰着性」はもっと単純な形にもできますが、上記の記述が使いやすと思います。
次に、可換性の無限版です。
- [無限可換性=置換不変性] f:J→I が可逆写像(双射)のとき、Σ(j∈J | xf(j)) = Σ(i∈I | xi) 。
そして、結合性の無限版。
- [無限結合性=分割不変性] (j∈J | Ij) がJで添字付けられた集合の族だとして、∪(j∈J | Ij) = I で「j ≠ j' ならば、Ij∩Ij' = 空集合」であるとき、Σ(j∈J | Σ(i∈Ij | xi)) = Σ(i∈I | xi) 。
半環の総和可能性
半環 S = (S, +, ・, 0, 1) があるとき、(S, +, 0) は可換モノイドです。半環の総和可能性は、足し算を与える可換モノイドに関する総和可能性を使って定義できます。しかし、掛け算が関係する分配法則も必要です。
- [無限左分配性] a・Σ(i∈I | xi) = Σ(i∈I | a・xi) 。
- [無限右分配性] Σ(i∈I | xi)・b = Σ(i∈I | xi・b) 。
これらを使うと、一般的な無限分配法則が出ます。
- (Σ(i∈I | xi))・(Σ(j∈J | yj)) = Σ(i∈I, j∈J | xi・yj)
i∈I, j∈J の部分は、(i, j)∈I×J と同じ意味です。無限和の掛け算が、2次元の添字集合に渡る無限和になるのです。
可換モノイド豊饒圏の総和可能性
可換モノイド(commutative monoid)の圏をCMonとします。圏Cは、圏CMonで豊饒化(enriching, enrichment)された圏だとします。つまり、ホムセットC(A, B)に可換モノイドの構造が入っているということです。さらに、圏の結合(composition)に関しては左右の分配法則とゼロによる吸収法則が成立します。
- f:A→B、g, h:B→C に対して、f;(g + h) = f;g + f;h
- f, g:A→B、h:B→C に対して、(f + g);h) = f;h + g;h
- f;0 = 0、0;f = 0
CMon-豊饒圏(CMon-enriched category)におけるχ-総和可能性の定義は、半環のときとほとんど同じです。
まず、すべてのホムセットにはχ-総和可能な可換モノイドの構造が入ります。それと、左右の分配法則が無限和に関しても拡張されます。特に、対象Aの自己ホムセット EndC(A) = C(A, A) はχ-総和可能な半環となります。
χ-総和可能なCMon-豊饒圏とは、χ-総和可能な可換モノイドの圏で豊饒化された圏と言っても同じことです。ただし、豊饒圏構成のお作法から言えば、χ-総和可能な可換モノイドの圏に対称モノイド積(テンソル積)を入れる必要がありますが、これはメンドクサイので、はしょった定義を採用しています。「ωCPO(可算完備順序集合)で考える形式言語理論」も参考になるかも知れません。
半加法圏の総和可能性
半加法圏については、「テンソル半加法圏とプログラム意味論」に書いてあります。
半加法圏では、双積(多くの場合「直和」とも呼ぶ)と対角と余対角から足し算を構成できるので、各ホムセットは可換モノイドになります。つまり、半加法圏は常にCMon-豊饒圏とみなせます。
半加法圏にCMon-豊饒圏のχ-総和可能性の定義を適用すれば、χ-総和可能な半加法圏の定義が得られますが、これだけだともの足りないのです。双積に関しても無限双積が欲しくなります。
そこで、半加法圏Cにおいては次の条件を付け加えましょう。
- Iは基数条件χを満たす集合として、X:I→|C| を写像とするとき、Xを離散圏からCへの関手とみなして、その極限と余極限が存在して標準的に同型である。
「標準的に同型である」あたりがメンドクサイので、対象の族の無限双積が一意に確定するとして、それを Σ(i∈I | Xi) と書いてしまいましょう。これは強い条件となりますが、使い勝手はこのほうがいいですね。
対象の族の無限双積が作れると、圏係数の行列(「圏係数の行列の圏」を参照)の計算の意味論をC内に構成できます。
ここで定義したχ-総和可能な可換モノイド、半環、可換モノイド豊饒圏、半加法圏などは、「「M.W.ホプキンスの観察」への気長なアプローチ」で述べた気長な道のりを歩く道具になるだろうと思っています。