Algebras and Coalgebras, Section 12. Covarieties

代数の variety に対応する、余代数の covariety の話。HSP theorem の余代数版をやります。

ちなみに実際に本を読んでいるときは、図式を大量に描きながら計算しています。

homomorphic images

代数と同様に余代数にも準同型像というものが考えられる。定義は代数と全く同じで、全射準同型 $A \rightarrow B$ があるときに B は A の homomorphic image であるという。

また、これも代数と同様に準同型があれば kernel を考えることができる。これは Ω が weak pullback を保存すれば bisimulation equivalence になる。また一般に bisimulation equivalence があれば、それによる集合としての剰余に余代数の構造が入り、標準射影は準同型となる。

subcoalgebras

余代数(の台集合)の部分集合が open であるとは、inclusion map が準同型になるように余代数の構造が入ることをいう。open subset に対して、そのような余代数の構造を入れたものを subcoalgebra という。

set functor は単射を保存する*1。このことから、ある部分集合が open ならば、その subcoalgebra としての構造は一意であることがわかる。

余代数 A について、その open set の全体は位相をなす。特に、部分余代数の全体は set-theoretic union を join とする完備束をなす。

また、位相空間を filter functor の余代数とみなすとき、余代数の意味での open set と位相の意味での open set は一致する。

余代数の準同型 $f : A \rightarrow B$ が与えられたとき、その像は B の subcoalgebra であり、f はその像への全射準同型である。

sums

代数の場合は直積が基本的な演算の一つになっていましたが、余代数でそれに当たるものは直和になるようです。modal algebra の直積に対応するものは Kripke frame では直和だったので、確かにそれが自然な気もします。

$\alpha_i : A_i \rightarrow \Omega A_i$ を余代数の族とするとき、それらの直和 $\coprod_i A_i$ の上の余代数の構造は $(\Omega e_i) \circ (\alpha_i) : A_i \rightarrow \Omega A_i \rightarrow \Omega (\coprod_i A_i)$ の lift により定まる。

covarieties

S, H, Σ をそれぞれ subcoalgebra, homomorphic image, sum とする。*2

K が covariety であるとは、K がこれらの演算で閉じていること。すなわち S(K) = H(K) = Σ(K) = K が成立することをいう。また K を含む最小の covariety を Covar(K) で表す。

universal algebra における Tarski's HSP theorem と同様に Covar(K) = HSΣ(K) が証明できる。これは単純に、右辺が H, S, Σ で閉じていることをいえばよく、地道にやればできる。

building blocks?

代数では variety は subdirectly irreducible member から生成されるという定理があったが、それに対応するようなことがいえるかどうか、という話が少し。代数は積への分解を考えますが、余代数の場合には和への分解を考えます。

余代数 A の conjunct representation とは、埋め込みの族 $e_i : A \rightarrow A_i$ であって、 $\bigcup_i e_i[A_i] = A$ が成り立つもののことをいう。conjunct representation が自明であるとは、ある $e_i$ が同型となっていることである。余代数は、非自明な conjunct representation をもたないとき conjunctly irreducible であるという。

以上の定義のもとで自然に考えられるのは「すべての余代数は conjunctly irreducible coalgebra による conjunct representation をもつか？」という問題ですが、どうやらこれは否定的に解決しているようです。フォローできてないのですが、位相空間を filter functor の余代数とみなすと反例が作れるそうです。

それから subdirect decomposition が congruence lattice の構造と関係しているという事実の類似に見える現象が紹介されています。S が conjunctly irreducible であることは、ある s ∈ S を含む非自明な subcoalgebra が存在しないことと同値である、という事実です。言われてみればいかにもという感じなのですが、これはつまり subcoalgebra のなす束の構造が conjunct irreducibility と関係しているということであり、代数の側にあった congruence lattice の構造と subdirect irreducibility とのつながりに類似しているように思いました。

*1:集合の圏で単射 $f : A \rightarrow B$ は retract $g : B \rightarrow A$ をもつ (つまり $g \circ f = id$ となる g がとれる)。関手 F を考えると、F は恒等射を保存するから $id = F(g \circ f) = Fg \circ Ff$ となり、Ff も単射でなければならない。

*2:正確には、クラス K に対して S(K) は K に属する coalgebra の subcoalgebra 全体。他も同様。