日記 (2019 年 11 月 23 日)
11 月 16 日では、 始代数や終余代数が様々なデータ構造を定めることを見たが、 具体的な構成については 1 つ例を挙げただけで詳しく触れなかった。
ということで、 今回は Adámek†1 による構成を紹介しようと思う。
なお、 基本的な圏論の知識は仮定する。
この構成では、 以下のような形の図式の余極限を考える。
定義 2.1.
圏 において、
S0S1S2⋯f0f1f2
の形の図式を 上の鎖 (chain) という。
より簡潔に言えば、 圏 上の鎖とは、 自然数全体の集合 を通常の大小関係で圏と見なしたときの関手 K:→ のことである。
定理 2.2.
圏 上の自己関手 F:→ が、 2 条件
- は始対象をもつ。
- F は全ての鎖の余極限を保存する。
をともに満たすとする。
このとき、 の鎖
0F0F20⋯!F!F2!
の余極限が存在すれば、 それは F-始代数を与える。
なお、 !:0→F0 は始対象からの唯一の射である。
証明.
定理中の図式の余極限を S とおく。
すると、 各自然数 n に対し、 構造射 un:Fn0→S が存在する。
ここで、 Fun∘Fn!:Fn0→FS を考えると、 これは F の余錐を構成する。
したがって、 余極限の普遍性によって、 図式
Fn0SFn+10FSunFn!Funσ
を可換にする射 σ が存在する。
仮定から、 F は鎖の余極限を保存するので、 特に S を保存する。
すなわち、 ここで作られた σ は同型射であるから、 その逆射 σ:=σ−1 がとれる。
すると、 (S,σ) が F-始代数になる。
このことを証明するため、 任意に F-代数 (A,α) をとる。
各自然数 n に対し、 射 hn:Fn0→A を、
h0:=!hn:=α∘Fhn−1
によって帰納的に定める。
すると、 帰納法によって、
Fn0Fn+10AFn!hnhn+1
が可換になることが分かるので、 hn たちは F の余錐を構成する。
したがって、 図式
Fn0SAunhnf
を可換にする射 f が一意に存在する。
その一方で、 これまでの図式の可換性によって、
Fn0SFn+10FSFAAunFn!hnσFunFhnhn+1Ffα
は可換であるから、 普遍性による分解の一意性によって、 f=α∘Ff∘σ が成り立つ。
σ=σ−1 であったことを思い出すと、 これはすなわち、
FSFASAFffσα
が可換であるということであり、 f は代数の射であるということである。
また、 同じく普遍性による分解の一意性により、 このような代数の射 f は一意である。
したがって、 (S,σ) が F-始代数であることが示された。
これにより、 定理中の条件を満たす圏と自己関手を扱っているのであれば、 その圏における鎖の余極限の具体的な構成を用いて、 始代数も具体的に書き下すことができる。
例えば、 前回と同様 Set を挙げよう。
Set は当然始対象 (空集合) をもち、 さらにフィルター余極限が有限極限と交換することから、 有限積 (普通の直積) と余積 (非交和) だけから構成された自己関手であれば、 これは鎖の余極限を保存する。
特に、 前回例として挙げた FV は鎖の余極限を保存するので、 この定理の構成が利用できる。
各自然数 n に対し、
FVn=1+V+V2+⋯+Vn
と計算でき、 Fn!:FVn→FVn+1 はここに自然に考えられる埋め込みになる。
したがって、 この余極限は、
colimn∈FVn=1+V+V2+⋯=n∈Vn
となる。
これは V の元からなる有限列全体の集合であるから、 前回の話と合致している。
参考文献
- J. Adámek (1974) 「Free algebras and automata realizations in the language of categories」 『Commentationes Mathematicae Universitatis Carolinae』 15(4):589–602