「有向コンテナと多項式コモナド」の続きの話をしたいわけですが、まずは、コンテナ／多項式界隈の、概念・用語・記法のしっちゃかめっちゃかを整理するところから書き始めました。そしたら、一般論がだいぶ長くなってしまいました。一般論の部分を別記事にすることにします、それがこの記事です。
概念的事物を区別するか／同一視するか？定義の微妙な差をどう取り扱うか？ それと、記号の乱用を緩和する方法について述べます。$`\newcommand{\mrm}[1]{\mathrm{#1}}
\newcommand{\In}{\text{ in } }
\newcommand{\coef}[1]{ {\langle #1 \rangle} }
\require{color} % 緑色
\newcommand{\Keyword}[1]{ \textcolor{green}{\text{#1}} }%
\newcommand{\For}{\Keyword{For } }%
\newcommand{\Define}{\Keyword{Define } }%
\newcommand{\Subject}{\Keyword{Subject } }%
\newcommand{\Where}{\Keyword{Where } }
\newcommand{\Let}{\Keyword{Let } }
\newcommand{\KWB}[1]{ \textcolor{blue}{\text{#1}} }% KeyWord Blue
\newcommand{\if}{\KWB{if } }
\newcommand{\then}{\KWB{ then } }
\newcommand{\else}{\KWB{else } }
`$
内容：
はじめに
圏論的コンテナ／圏論的多項式の話で、コンテナとそれが定義する多項式関手がゴッチャにされていて分かりにくいことがあります。思い起こせば、“多項式”って曖昧に扱われていて分かりにくいものでした。次節でそのことを話題にします。
圏論的コンテナ／圏論的多項式では、グラフ理論からの概念を使用します。パス、カローラ、低木〈shrub〉、ツリー、林〈forest〉などです。異なる概念に同じ呼び名が付いたり、同じ呼び名の概念でも微妙に定義が違ったりします。後の節でそのことを話題にします。
数理的記述一般において、理解を阻害したり誤解をまねく書き方に以下のようなもの（重複や絡み合い有り）があります。
- 記号の乱用
- 名前のオーバーロード
- 構造とその構成素に同じ名前
- 互いに対応するモノは同じ名前
- 少し違うだけの概念に同じ名前
- 省略
- 暗黙の前提
これら（特に記号の乱用）による弊害を少なくする方針を最後に述べます。
係数列と多項式関数
中学・高校で習った多項式においても、多項式の係数列と多項式関数を区別するか／同一視するか？ という問題はあります。このことを説明します。
$`{\bf R}^\coef{n}`$ という集合を定義します。$`{\bf R}^\coef{n}`$ は $`{\bf R}^{n + 1}`$ とよく似てますが、次の二点が違います。
- $`a \in {\bf R}^\coef{n}`$ は、$`(a_0, a_1, \cdots, a_n)`$ のように、ゼロから番号をふる。第$`n`$成分は、$`(n + 1)`$番目の成分。
- $`a \in {\bf R}^\coef{n}`$ ならば、$`a_n \ne 0`$ とする。つまり、第$`n`$成分〈$`(n + 1)`$番目の成分〉がゼロであることを許さない。
便宜上、$`{\bf R}^\coef{-\infty} = \{()\}`$ としておきます。念の為に具体的に書いておくと：
- $`{\bf R}^\coef{-\infty} = \{ () \}`$
- $`{\bf R}^\coef{0} = \{ (a_0) \mid a_0 \in {\bf R}\land a_0 \ne 0 \}`$
- $`{\bf R}^\coef{1} = \{ (a_0, a_1) \mid a_0, a_1 \in {\bf R}\land a_1 \ne 0 \}`$
さらに次のように定義します。
$`\quad {\bf R}^\coef{*} := {\displaystyle \bigcup_{k = -\infty, 0, 1, \cdots} } {\bf R}^\coef{k} \;\in |{\bf Set}|`$
たくさんの集合の合併をしてますが、互いに共通部分がない集合達を合併しているので、事実上直和と同じです（が、タグ付き合併〈tagged union〉ではないので、タギングしてません）。
$`{\bf R}^\coef{n} \subseteq {\bf R}^\coef{*}`$ の要素は、$`n`$次多項式の係数列として使う心づもりです。
$`{\bf R}^{(\infty)}`$ を次のように定義します。
$`\quad {\bf R}^{(\infty)} := \{a\in \mrm{Map}({\bf N}, {\bf R}) \mid
\{k\in {\bf N} \mid a(k) \ne 0\} \text{ は有限集合}
\}`$
$`{\bf R}^\coef{*}`$ と $`{\bf R}^{(\infty)}`$ は集合としては同型です。$`{\bf R}^{(\infty)}`$ 上に以下のような関数 $`\mrm{deg}`$ （次数〈degree〉のつもり）を定義して、$`\mrm{deg}`$ の逆像で組織化すれば $`{\bf R}^\coef{*}`$ が再現します。（以下、$`\Subject`$で、定義すべきモノを宣言してから実際の定義を続けます。）
$`\Subject \mrm{deg} : {\bf R}^{(\infty)} \to \{-\infty \}\cup{\bf N} \In {\bf Set}\\
\For a \in {\bf R}^{(\infty)}\\
\Define \mrm{deg}(a) := \\
\quad \if \lnot \exists k \in {\bf N}.\, a(k) \ne 0 \then -\infty\\
\quad \else \mrm{max}(\{ k \in {\bf N}\mid a(k) \ne 0 \})
`$
「$`\mrm{deg}`$ の逆像で組織化する」とは、あらためて次のように定義することです。
$`\quad {\bf R}^\coef{n} := \mrm{deg}^{-1}(n) \;\subseteq {\bf R}^{(\infty)}`$
新しく定義した $`{\bf R}^\coef{n}`$ は、最初の定義と100%同じとは言えませんが、事実上同じです。
$`a \in {\bf R}^\coef{*}`$（あるいは $`a\in {\bf R}^{(\infty)}`$）があると、次のような“多項式”が定義できます。
$`\quad a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n`$
あるいは総和記号を用いて：
$`\quad \sum_{i = 0}^n a_i x^i`$
次数が低い場合なら：
- $`-\infty`$次多項式： $`0`$
- $`0`$次多項式： $`a_0 \:\text{ where }a_0 \ne 0`$
- $`1`$次多項式： $`a_0 + a_1 x \:\text{ where }a_1 \ne 0`$
- $`2`$次多項式： $`a_0 + a_1 x + a_2 x^2 \:\text{ where }a_2 \ne 0`$
多項式が定義する関数は、ラムダ記法で次のように書けます。
$`\quad \lambda\, x\in {\bf R}.(\, \sum_{i = 0}^n a_i x^i \;\in {\bf R}\,)
\; : {\bf R} \to {\bf R} \In {\bf Set}
`$
ここで、3つのモノ（概念的事物）が出てきました。
- 実数の有限列 $`a \in {\bf R}^\coef{*}`$
- 記号的な形式 $`\sum_{i = 0}^n a_i x^i`$
- 関数 $`\lambda\, x\in {\bf R}.(\, \sum_{i = 0}^n a_i x^i \;\in {\bf R}\,)`$
これら3つのモノを区別すべきでしょうか？ 中学・高校では（おそらく）区別しないで曖昧に扱っています。区別するほどのこともないかも知れないし、曖昧にすることによる便利さもあります。
が、精密な議論では区別しないとまずいことがあります。タチの悪い習慣は、実際には区別しているにも関わらず、表面上は区別しないで語ることです。
有向グラフの誘導された部分グラフ
登場するグラフは有向グラフだけなので、単に「グラフ」と言ったら有向グラフです。
「有向コンテナと多項式コモナド」で、半径 1 のカローラという概念を定義しました（この記事内でも後で定義を繰り返します）。これは、高さ 1 のツリーとほぼ同じです。ほぼ同じなのですが、微妙な差はあります。その微妙な差が問題（心理的問題かも知れない）となることもあります。以下、少し細かい議論をします。
グラフ〈有向グラフ〉を、$`G = (V, E, \mrm{src}, \mrm{trg})`$ と書きます。$`V`$ は頂点の集合、$`E`$ は辺の集合で、$`\mrm{src}, \mrm{trg}`$ は辺に始点・終点を対応させる関数（プロファイルは $`E \to V \In {\bf Set}`$）です。グラフの部分グラフ〈subgraph〉は明確な意味を持つ概念なので、$`G`$ のすべての部分グラフの集合 $`\mrm{Subgraph}(G)`$ は明確な集合です。
頂点 $`v \in V`$ と、単一の頂点だけからなる部分グラフ $`(\{v\}, \{\}, \mrm{src}, \mrm{trg})`$ （ここでの $`\mrm{src}, \mrm{trg}`$ は空集合から単元集合への自明な写像）は違う概念です。辺 $`e \in E`$ と、単一の辺とその両端（$`a, b`$ とする）だけからなる部分グラフ $`(\{a, b\}, \{e\}, \mrm{src}, \mrm{trg})`$ も、もちろん違う概念です。頂点は $`V`$ の要素で、辺は $`E`$ の要素で、部分グラフは $`\mrm{Subgraph}(G)`$ の要素です。
グラフ $`G`$ の頂点の集合 $`V`$ の部分集合を $`A`$ とします（$`A \subseteq V`$）。$`A`$ から誘導された充満部分グラフ〈full subgraph induced from vertex set〉とは次のものです。
$`\quad \mrm{FullSubgraphFromVert}_G(A) := (A, E', \mrm{src'}, \mrm{trg'})\\
\Where\\
\quad E' := \{e \in E \mid \mrm{src}(e) \in A \land \mrm{trg}(e) \in A \}\\
\quad \mrm{src'} := \mrm{src}|_{E'}\\
\quad \mrm{trg'} := \mrm{src}|_{E'}
`$
同じ仮定で、$`A`$ から誘導された離散部分グラフ〈discrete subgraph induced from vertex set〉とは次のものです。
$`\quad \mrm{DiscSubgraphFromVert}_G(A) := (A, E', \mrm{src'}, \mrm{trg'})\\
\Where\\
\quad E' := \emptyset = \{\}\\
\quad \mrm{src'} := \mrm{src}|_\emptyset\\
\quad \mrm{trg'} := \mrm{src}|_\emptyset
`$
グラフ $`G`$ の辺の集合 $`E`$ の部分集合を $`B`$ とします（$`B \subseteq E`$）。$`B`$ から誘導された最小部分グラフ〈minimum subgraph induced from edge set〉とは次のものです。
$`\quad \mrm{MinSubgraphFromEdge}_G(B) := (V', B, \mrm{src'}, \mrm{trg'})\\
\Where\\
\quad V' := \{v \in V \mid \exists e\in B. v = \mrm{src}(e) \lor \mrm{trg}(e) = v \}\\
\quad \mrm{src'} := \mrm{src}|_{B}\\
\quad \mrm{trg'} := \mrm{src}|_{B}
`$
上記の誘導された部分グラフは部分グラフ（$`\mrm{Subgraph}(G)`$ の要素）ですが、$`A, B`$ は部分グラフではありません。グラフを生成する素材となる集合に過ぎません。単なる集合と部分グラフが違うことは当たり前なのですが、カローラや部分ツリーの話になると不明確になりがちです（次節の話題）。
カローラと部分ツリー
登場するツリーは根付き有向ツリー〈rooted directed tree〉だけなので、単に「ツリー」と言ったら根付き有向ツリーです。
グラフ $`G = (V, E, \mrm{src}, \mrm{trg})`$ と、頂点 $`r\in V`$ （根〈ルート | root〉と呼ぶ）の組 $`(G, r)`$ *1が、根〈ルート〉から葉〈リーフ〉への向きを持った{根付き}?ツリー〈{rooted}? root-to-leaf-directed tree 〉だとは次のことです。
- 任意の頂点 $`v`$ に対して、根 $`r`$ から $`v`$ に至る有向パスがただひとつだけ存在する。
グラフ $`G`$ がツリーでなくても、部分グラフ $`T \in \mrm{Subgraph}(G)`$ と $`T`$ の頂点 $`r`$ の組 $`(T, r)`$ がツリーになることはあります。
グラフ $`G = (V, E, \mrm{src}, \mrm{trg})`$ と頂点 $`a\in V`$ に対して、「有向コンテナと多項式コモナド」で定義した、中心 $`a`$ で半径 1 のカローラ〈corolla with center a and radius 1〉とは、次の集合です。
$`\quad \mrm{Corol}_G(a, 1) := \{e \in E \mid \mrm{src}(e) = a \}`$
半径 0, 2 のカローラなら次のようです。
$`\quad \mrm{Corol}_G(a, 0) := \{a\} \;\subseteq V\\
\quad \mrm{Corol}_G(a, 2) := \{(e, f) \in E\times E \mid \mrm{src}(e) = a \land \mrm{src}(f) = \mrm{trg}(e) \}
`$
これらは $`G`$ の部分グラフではありません。しかし、カローラを素材にして部分グラフを誘導できます。$`C \in \mrm{Corol}_G(a, 1)`$ ならば、カローラ $`C`$ から誘導された最小部分グラフは高さ 1 のツリーになりますなることもあります*2。その根〈ルート〉は中心 $`a`$ です。また、$`C \in \mrm{Corol}_G(a, 0)`$ ならば、カローラ $`C`$ （これは頂点の集合）から誘導された離散部分グラフは単一頂点だけのグラフになりますが、高さ 0 のツリーといえます。
半径 n のカローラからは、高さ n のツリーがすぐさま構成できる構成できることがあるので*3、半径 n のカローラと高さ n のツリー（ただし、葉〈リーフ〉の高さが揃っている）は事実上同じものです。が、まったく同じか？ というと、定義上は違います。カローラは、$`G`$ の部分グラフにはなってません。
「高さ 1 のツリーを（半径 1 の）カローラと呼ぶ」という定義も当然にアリです。その定義でも特に問題は起きないでしょう。しかし、辺の集合（あるいはパスの集合）としてカローラを定義しているなら、それは、高さ 1 のツリーとは微妙に違うのです。このような微妙な違いは、ロジカルに云々というよりは、なんかスッキリしない／不愉快／気持ち悪い感覚に繋がります*4。
この節で、打ち消し線で訂正してある箇所は、僕が最初に迂闊に書いてしまった記述です。カローラをパスの集合だとすると、もとのグラフに多重辺やサイクル（自己ループ辺含む）があると、カローラから誘導した部分グラフにも多重辺やサイクルが生じます。多重辺やサイクルがあってはツリーとは呼べません。
パスの集合と、それを親のグラフ上に落とした部分グラフはだいぶ違う、ということです。脚注の追記もみてください。
[/追記]
記号の乱用を緩和する方法
記号の乱用〈abuse of notation〉は便利だし、なしで済ませることは無理です。が、幾つかの記号の乱用／名前のオーバーロードが組み合わさると、極端に解釈の負荷が増大してしまうことがあります。
典型的な記号の乱用は、モノイドを、
$`\quad M = (M, *, e)`$
のように書くことです。モノイド構造と、その台集合を同じ名前でオーバーロードしています。次のように書いたほうが誤解・混乱は減ります。
$`\quad M = (U, m, e)`$
すべての構成素に名前を付けて、例えば、構成素の参照を「構造の名前 ドット 構成素の名前」という構文で書くなら：
$`\quad M = (M.\mrm{Und}, M.\mrm{mult}, M.\mrm{unit}) = (U, m, e)`$
これは次のような宣言をしていることになります。ダブルスラッシュの後はコメント〈注釈〉の文言です。
$`\For M \in |{\bf Mon}|\\
\Let U := M.\mrm{Und} \text{ // Underlying set of }M\\
\Let m := M.\mrm{mult} \text{ // multiplication of }M\\
\Let e := M.\mrm{unit} \text{ // unit of }M
`$
構成素を参照する構文は色々あるので（「構造とその素材の書き表し方」参照）、次のような書き方も（その他色々な書き方が）あります。
$`\quad M = (\mrm{Und}(M), \mrm{mult}^M, \mrm{unit}^M) = (U, m, e)`$
前の節で話題にしたグラフならば：
$`\quad G = (\mrm{Vert}(G), \mrm{Edge}(G), \mrm{src}^G, \mrm{trg}^G) =
(V, E, \mrm{src}, \mrm{trg})
`$
演算子記号や特殊な定数記号を使う場合は、記法の規約〈notational conventions〉を明示的に書くほうがいいでしょう。例えば：
- モノイドの乗法〈multiplication〉には、二項中値演算子記号 '$`*`$' を使ってもよい。
- モノイドの単位〈unit〉を、'1' と書いてもよい。
この規則は、次のように書いてもたぶん伝わるでしょう。
$`\quad M = (\mrm{Und}(M), \mrm{mult}^M, \mrm{unit}^M) = (U, *, 1)`$
「モノイド $`M`$」という言い方をすれば、結合法則と左右の単位法則が含意されます。しかし、単に $`M = (U, m, e)`$ という書き方だと、$`M`$ は付点マグマ〈poited magma〉（特定要素が指定された集合に、無法則な二項演算が載った構造）かも知れません。構造の種類を次のように明示すれば曖昧さを避けられます。
$`\quad M = \mrm{Mon}(U, m, e)\\
\text{i.e. } M \in |{\bf Mon}|, \, M = (U, m, e)\\
\quad M = \mrm{PtMagma}(U, m, e)\\
\text{i.e. } M \in |{\bf PtMagma}|, \, M = (U, m, e)
`$
記号の乱用（の乱用）を緩和する（完全に避けるのは無理）方法をまとめると：
- 構造の構成素名を使う。
- 記法の規約をハッキリと書く。
- 必要なら、構造の種類（構造のインスタンスが所属する圏）を明示する。
