このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

単調作用素と閉包作用素のプレ不動点


\newcommand{\cat}[1]{\mathcal{#1}}
\newcommand{\id}{\mathrm{id} }
\newcommand{\mrm}[1]{\mathrm{#1} }
\newcommand{\In}{\text{ in } }
\newcommand{\Imp}{\Rightarrow }
昨日の「有法則代数と無法則代数」から連想した小ネタ。

昨日の話

F = (F, \mu, \eta)/\cat{C} (記号の乱用)を圏 \cat{C} 上のモナドとします。このモナドのクライスリ圏とアイレンベルク/ムーア圏は次のように書くことが多いです(僕だけでなく世間的に)。

  • クライスリ圏: \mrm{Kl}(F, \cat{C}) = \mrm{Kl}(F/\cat{C}) = \mrm{Kl}(F)
  • アイレンベルク/ムーア圏: \mrm{EM}(F, \cat{C}) = \mrm{EM}(F/\cat{C}) = \mrm{EM}(F)

アイレンベルク/ムーア代数を単に“代数〈algebra〉”と呼ぶ流儀なら、次の書き方もあります。

昨日、「けっこう困っていた」と言ったのは、単なる自己関手に対する \mrm{Alg}(F) もあることです。解決策の案は、 \mrm{LawfulAlg}(F),\, \mrm{LawlessAlg}(F) と区別することです。ここで、 法則 = 結合法則と単位法則 のつもりです。

順序集合の場合

A = (A, \le), B = (B, \le) (記号の乱用)を順序集合とします。順序集合のあいだの準同型写像とは単調写像〈{monotone | monotonic} map〉のことです。

  • f:A \to B の単調性: \forall x, y\in A. x \le y \Imp f(x)\le f(y)

順序集合はやせた圏〈thin category〉とみなせます。単調写像は共変関手とみなせ、反単調写像〈{antitone | anti-monotonic} map〉は反変関手とみなせます。

自己写像〈endomap | self-map〉を作用素〈operator〉と呼ぶことにします(ここだけの気分から)。順序集合の単調作用素 f:A \to A圏論的に解釈すると自己関手なので、f の無法則代数の圏と有法則代数の圏〈アイレンベルク/ムーア圏〉が作れます。

  • 無法則代数の圏: \mrm{LawlessAlg}(f/A)
  • 有法則代数の圏: \mrm{LawfulAlg}(f/A) = \mrm{EM}(f/A)

以上の話は、圏論的概念を順序集合に適用しただけです。が、具体的には何を意味するのでしょうか?

具体的に

有法則代数の圏は、単なる自己関手〈単調作用素〉に対しては定義できませんモナドである必要があります。自己関手〈単調作用素f:A \to Aモナドである条件を順序の言葉で書けば:

  1. \eta :: \forall x\in A. x \le f(x)モナドの単位)
  2. \mu :: \forall x\in A. f(f(x)) \le f(x)モナドの乗法)

モナドは、単調作用素と2つの不等式で定義されます。二番目の不等式は、等式 f(f(x)) = f(x) でもかまいませんが、圏論との素直な対応としては不等式のままがいいでしょう。

単調作用素のあいだの不等式は、圏論的には自然変換に相当するので、上記の定義は「モナドは台関手と2つの自然変換で定義される」ことを反映しています。

こうして定義されるモナド相当の(不等式付きの)単調作用素閉包作用素〈closure operator〉と呼びます。

自己関手〈単調作用素〉の代数とは、特定の要素 a\in A に対する不等式 f(a)\le a のことです。この不等式を満たす点〈要素〉を fプレ不動点〈pre-fixed point〉と呼びます。

不等式が逆向き a \le f(a) だとポスト不動点〈post-fixed point〉を定義します。僕は、プレとポストの区別が憶えられないので、f の縮小点/増大点とかのほうがいいのですが … まっ、憶えましょ。

自己関手〈単調作用素〉がモナド〈閉包作用素〉のとき、代数に対する法則(結合法則と単位法則)は可換図式で次のように書けます。\beta は代数〈プレ不動点〉を定義する不等式です。矢印を不等号に読み替えれば不等式条件になります。

\require{AMScd}
\begin{CD}
f(f(a)) @>{\mu_a}>>    f(a)\\
@Vf({\beta})VV          @VV{\beta}V\\
f(a)    @>{\beta}>>    a
\end{CD}\\
\:\\
\begin{CD}
a @>{\eta_a}>>  f(a) \\
@|              @VV{\beta}V\\
a @=            a
\end{CD}\\
\:\\
\text{commutative in } A

モナド〈閉包作用素〉の場合の代数〈アイレンベルク/ムーア代数〉は、不動点〈fixed point | fixpoint〉 a = f(a) になります。

このことは、モナドの代数=アイレンベルク/ムーア代数=有法則代数 は、単なる自己関手の代数=無法則代数 より条件がきつい事例になっています。


こんな感じで、順序集合に圏論的概念/圏論的構成を適用して対応を探ってみるのは面白いかも知れません。

[追記]
順序集合を圏とみなす話題については、次の記事からリンクされています。

今日の話題に特に関係が深いのは:

[/追記]