Avendia20

日記 (2019 年 11 月 29 日)

11 月 16 日に引き続き、 今回は hylomorphism と metamorphism を定義する。

これらの射は、 下方射や上方射と同様に、 ある自己関手 F に対する F-始代数や F-終余代数から誘導されるものである。 しかし、 全ての (もちろん F-始代数や F-終余代数が存在するのは前提として) F に対して定義できるわけではなく、 F がある特殊な性質をさらに満たしている必要がある。

まず、 命題 3.1 を思い出そう。 この命題によると、 F-始代数 (S,σ) に定まっている σ は同型射であるから、 逆射 σ−1:S→FS が存在する。 これによって、 F-余代数 (S,σ−1) が誘導されることになる。 これは一般に F-終余代数になるとは限らない。 そして、 これが F-終余代数になるというのが、 今回重要になる特殊な性質である。

同じ議論は F-終余代数から始めることもできる。 F-終余代数 (T,τ) があると、 先程の命題の証明と同様にして τ が同型射になることが示せるので、 F-代数 (T,τ−1) が誘導される。 これも一般に F-始代数になるわけではない。

以上により、 始代数が誘導する余代数が終余代数になるという主張と、 終余代数が誘導する代数が始代数になるという主張が考えられるが、 これは同値になる。

命題 4.1.

圏 󰒚 上の自己関手 F:󰒚→󰒚 をとる。 2 つの条件

は同値である。

証明.

自明である。

定義 4.2.

圏 󰒚 上の自己関手 F:󰒚→󰒚 をとる。 F が上の命題の同値な 2 条件のいずれか (したがって両方) を満たすとき、 F は代数的コンパクト (algebraically compact) であるという。

F が代数的コンパクトであるとは、 要するに F-始代数と F-終余代数が一致するということである。

今後のため、 いくつか記号を用意しておく。 自己関手 F に対し、 F-始代数と F-終余代数をそれぞれ μF と νF で表すことにする。 F が代数的コンパクトであればこの 2 つは一致するので、 その場合は一致していることを明確にするため記号を変えて φF と書くことにする。

さて、 代数的コンパクトな関手の例が気になるところだが、 残念ながら Set 上の自己関手は代数的コンパクトになりづらく、 私は定値関手くらいしか知らない。 例えば、 11 月 16 日に例として挙げた関手 FV: Set ⟶ Set A ⟼ 1+V×A を考えると、 FV-始代数が V の元から成る有限リスト全体であった一方、 FV-終余代数は V の元から成る有限もしくは無限のリスト全体であったから、 これらは一致しておらず FV は代数的コンパクトではない。 多くの Set 上の自己関手 F に対し、 F-始代数はある意味 「有限的」 な値の集まりになり、 F-終余代数は 「無限的」 な値の集まりになってしまうのが原因である。

点付き完備順序集合と厳密連続写像が成す圏 (ここで PDcpo! と書かれている圏) であれば、 実用上現れるような関手は全て代数的コンパクトになることが知られている。 これについてはここでは詳しく触れない。 とりあえず現段階では、 多くの関手が代数的コンパクトになってくれるような都合の良い圏が存在することだけ留意しておいてもらえれば良い。

さて、 hylomorphism を定義する。 相変わらず勝手に日本語訳を当てる。

定義 4.3.

圏 󰒚 上の代数的コンパクトな自己関手 F:󰒚→󰒚 をとる。 F-代数 (A,α) と F-余代数 (C,γ) に対し、 合成 CφFAana(C,γ)cata(A,α) を、 (A,α) と (C,γ) による質料射 (hylomorphism) と呼んで hylo(A,C,α,γ) で表す。

metamorphism はこの双対概念で、 射の合成の順序が逆になる。

定義 4.4.

圏 󰒚 上の代数的コンパクトな自己関手 F:󰒚→󰒚 をとる。 対象が同じ F-代数 (A,α) と F-余代数 (A,γ) に対し、 合成 φFAφFcata(A,α)ana(A,γ) を、 (A,α) と (A,γ) による形相射 (metamorphism) と呼んで meta(A,α,γ) で表す。

では具体例といきたいところだが、 すでに述べたように、 直感的に理解しやすい Set 上の自己関手はあまり代数的コンパクトにならないので、 数学的文脈での例は少し挙げづらい。 次回は質料射と形相射を Haskell で実装しようと思っているので、 具体例はそのときまで先送りにすることにする。