日記 (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