指標の話： ペースティング図とバタニン・ツリー

高次圏の射達の組み合わせを表現する方法のひとつとして、ペースティング図があります。ペースティング図は、テキスト形式に書き写すことができます。ペースティング図とテキスト形式の中間の形式として、バタニン・ツリーがあります。バタニン・ツリーはとても便利だと思うので紹介します。$`\newcommand{\mrm}[1]{ \mathrm{#1} }
%\newcommand{\cat}[1]{ \mathcal{#1} }
%\newcommand{\In}{\text{ in }}
%\newcommand{\id}{ \mathrm{id} }
\newcommand{\twoto}{ \Rightarrow }
%\newcommand{\op}{ \mathrm{op} }
\newcommand{\hyp}{\text{－} }
%%
\require{color} % Using
\newcommand{\NN}[1]{ \textcolor{orange}{\text{#1}} } % New Name
\newcommand{\NX}[1]{ \textcolor{orange}{#1} } % New EXpression
\newcommand{\T}[1]{\text{#1} }
`$

内容：

ハブ記事：

• 指標の組織化と表現方法と呼び名は色々だ

ペースティング図とプロファイルパス

次は、（球体形状の〈globular〉）2次元ペースティング図の一例です。

$`\quad \xymatrix@C+1pc{
A
\ar@/^1.2pc/[r]^{f}_{\alpha}
\ar[r]|{f'}
\ar@/_1.2pc/[r]^{\alpha'}_{f''}
&B
\ar[r]^{g}
&C
\ar@/^0.8pc/[r]^{h}
\ar@{}[r]|{\beta}
\ar@/_0.8pc/[r]_{h'}
&D
}`$

2-射〈2-セル〉の矢印を描いてませんが、方向は上から下です。ラベル〈名前〉の約束は：

• 0-射のラベルはラテン文字大文字
• 1-射のラベルはラテン文字小文字
• 2-射のラベルはギリシャ文字小文字

このペースティング図の一部（全部ではない）をテキスト形式に書き写してみると：

$`\quad \alpha :: f \twoto f'\\
\quad f, f' : A \to B\\
\quad \beta :: h \twoto h'
`$

ここで、矢印で区切られたペア $`f\twoto f'`$ や $`A \to B`$ はプロファイル〈profile〉と呼びます。プロファイルは、射（今の場合は1-射と2-射）の域と余域の仕様を表します。

上記の最初の2行の情報は1行にまとめて書くこともできます。

$`\quad \alpha :: f \twoto f' : A \to B\\
\quad \beta :: h \twoto h'
`$

複数のプロファイルを繋げて書いた $`f \twoto f' : A \to B`$ のような形式はプロファイルパス〈profile path〉と呼ぶことにします。ただし通常は、プロファイルパスも単にプロファイルと呼びます。特に「複数のペアを繋げている」ことを強調したいときに「パス」を付けるだけです。パス形式のプロファイルに関しては以下の過去記事でも書いています。

• 有界な圏論的宇宙と圏論的パス式

ラベルとプロファイルパスを全部列挙すれば、ペースティング図のテキスト表現になります。

$`\quad \alpha : f \twoto f' : A \to B\\
\quad \alpha' : f' \twoto f'' : A \to B\\
\quad g : B \to C\\
\quad \beta :: h \twoto h' : C \to D
`$

「指標の組織化と表現方法と呼び名は色々だ // 指標の具体例と書き方の変種」で紹介した指標構文（のひとつ）で書き下せば以下のようです*1。指標名はハイフン（無名）としています。

$`\T{signature }\hyp \:\{\\
\quad \T{0-mor } \NX{A, B, C, D}\\
\quad \T{1-mor } \NX{f, f', f''} : A \to B\\
\quad \T{1-mor } \NX{g} : B \to C\\
\quad \T{1-mor } \NX{h, h'} : C \to D\\
\quad \T{2-mor } \NX{\alpha} :: f \twoto f' : A \to B\\
\quad \T{2-mor } \NX{\alpha'} :: f' \twoto f'' : A \to B\\
\quad \T{2-mor } \NX{\beta} :: h \twoto h' : C \to D\\
\}
`$

バタニン・ツリー

バタニン・ツリーについては次の論文で知りました。

• [FM17-]
• Title: A Type-Theoretical Definition of Weak ω-Categories
• Authors: Eric Finster, Samuel Mimram
• Submitted: 9 Jun 2017
• Pages: 12p
• URL: https://arxiv.org/abs/1706.02866

p.7 の "Batanin trees" の節にバタニン・ツリーについて書いてあります。

バタニン・ツリーは、ペースティング図やテキスト形式の指標と同じ情報を持ちます。バタニン・ツリーも（球体形状の）ペースティング図と同様に、組み合わせ幾何的対象物〈combinatorial-geometric object〉ですが、ペースティング図に比べてずっと構造が簡単です。また、絵図的〈pictorial | graphical | diagrammatic〉な表現なのでテキスト構文を定義する必要もありません。素晴らしい。

バタニン・ツリーは有限有向グラフとしての形状とラベル付け〈labeling〉を持ちます。まず、有限有向グラフとしての形状についてこの節で説明します。

有限平面ツリー〈finite planar tree〉を、高さ付きのノード〈頂点〉の集合と親子関係で定義しましょう。有限平面ツリーは次の構成素と条件からなります。

• $`V`$ は有限集合、その要素をノード〈node〉または頂点〈vertex〉と呼ぶ。
• $`\mrm{h} : V \to {\bf N}`$ は写像、高さ関数〈height function〉と呼ぶ。逆像 $`\mrm{h}^{-1}(k)`$ ã‚’ $`V_k`$ と書く。
• $`V_0`$ は単元集合。唯一の要素をルート〈root〉と呼ぶ。
• 自然数 $`k`$ ごとに写像 $`\mrm{par}_k : V_{k+1} \to V_k`$ 、$`\mrm{par}_k(x)`$ を、ノード $`x`$ の親ノード〈parent node〉と呼ぶ。
• $`x\in V_k`$ に対して、$`\mrm{Chil}(x) := {\mrm{par}_k}^{-1}(x)`$ を、ノード $`x`$ の子ノード達の集合〈set of {children | child nodes}〉と呼ぶ。
• すべての $`x\in V`$ に対して、集合 $`\mrm{Chil}(x)`$ 上に全順序構造 $`\le_x`$ （兄弟順序〈sibling order〉）が指定されている。$`\mrm{Chil}(x)`$ が空集合のときは、自明な全順序構造があるとみなす。

$`\mrm{par}_k`$ の下付き $`k`$ 、$`\le_x`$ の下付き $`x`$ は、混乱のおそれがなければ省略します。

ペア $`(x, \mrm{par}(x))`$ 達の集合を $`E`$ として、ペアの第一成分／第二成分を取る写像を $`\mrm{src}, \mrm{trg}`$ とすると、$`(V, E, \mrm{src}, \mrm{trg})`$ はグラフ〈有向グラフ〉になります。自己ループ辺も多重辺も持たない有限グラフです。辺の向きは子ノードから親ノードに向かいます。ツリーの場合は、辺を枝とも呼びます。

有限平面ツリー $`(V, \mrm{h}, \mrm{par}, \le)`$ は、$`V`$ が有限であり、高さと兄弟順序があるので、座標平面 $`{\bf R}^2`$ への具体的な描出〈rendering〉が容易です。描き方のゆらぎが少なくなるように、次の約束をしましょう。

1. ルートが一番下で、高さが大きなノードほど上に描く。
2. 同じ高さのノードは、だいたい同じy-座標になるように描く。
3. 兄弟順序は左から右へと描く。

次は、XyJax（このブログの図式描画に使っているツール）で描いた有限平面ツリーの一例です。

$`\quad \xymatrix{
{\bullet} \ar@{-}[dr]
\ar@{.}[rrrrr]
&{}
&{\bullet} \ar@{-}[dl]
&{}
&{\bullet} \ar@{-}[d]
&{2}
\\
{}
\ar@{.}[rrrrr]
&{\bullet} \ar@{-}[drr]
&{}
&{\bullet}\ar@{-}[d]
&{\bullet}\ar@{-}[dl]
&{1}
\\
{}
\ar@{.}[rrrrr]
&{}
&{}
&{\bullet}
&{}
&{0}
}`$

横方向の点線は高さを示すための補助線で、ツリーの一部ではありません。

上に向かう枝が出てないノードはリーフノード〈leaf node〉と呼びます。親子関係で言えば、子ノードを持たないノードがリーフノードです。

次節でバタニン・ツリーのラベリングについて説明します。

バタニン・ツリーのラベリング

バタニン・ツリーの形状は、前節で述べたような有限平面ツリーです。それだけだと何の変哲もないツリーに過ぎません。バタニン・ツリーをバタニン・ツリーたらしめている構造はそのラベリングです。ノードや枝〈辺〉にラベルを付けるのではなくて、エリア〈領域〉にラベルを付けます。

前節の約束により、座標平面 $`{\bf R}^2`$ へと描出〈rendering〉した幾何グラフで考えます。各ノード（を表す点）を中心として、適当な半径の半円板を描きます。$`(a, b)`$ を中心とした半径 $`\varepsilon \gt 0`$ の半円板の具体的な定義は以下のようです。

$`\quad \{(x,y)\in {\bf R}^2\mid (x -a)^2 + (y - b)^2 \le \varepsilon^2 \land y \ge b \}`$

半径 $`\varepsilon`$ は、他のノードや枝が半円板に入りこまないような値に設定します。ツリーの枝は線分で描くとすると、半円板は $`l`$ 本の枝で $`(l + 1)`$ 個のパイエリア〈pie area〉に分割されます。混乱を避けるために、パイエリアは境界を含まない〈開集合である〉としておきます。リーフノードでは、半円板の内部が1個のパイエリアです。

バタニン・ツリーのラベルは、ノードでも枝〈辺〉でもなく、今説明したパイエリア（半円板内部でもよい）に付けます。が、半円板やパイエリアを律儀に描くのは（描画ツールの都合もあって）面倒なので、次の約束をします。

1. パイエリアが半円板内部のときは、ラベルをノードのラベルのように描いてよい。
2. 枝で分割されたパイエリアのラベルは、枝の左側または枝の右側のラベルとして描いてよい。

この方式で、前節のツリーにラベリングしてみます。

$`\quad \xymatrix{
{\alpha\,\bullet} \ar@{-}[dr]_{f}^{f'}
\ar@{.}[rrrrr]
&{}
&{\alpha'\, \bullet} \ar@{-}[dl]^{f''}
&{}
&{\beta \, \bullet} \ar@{-}[d]_{h}^{h'}
&{2}
\\
{}
\ar@{.}[rrrrr]
&{\bullet} \ar@{-}[drr]_{A}^{B}
&{}
&{g\, \bullet }\ar@{-}[d]^{C}
&{\bullet}\ar@{-}[dl]^{D}
&{1}
\\
{}
\ar@{.}[rrrrr]
&{}
&{}
&{\bullet}
&{}
&{0}
}`$

有限平面ツリーの形状と、パイエリアへのラベリングからなる構造がバタニン・ツリー〈Batanin tree〉です。上記のバタニン・ツリーは、最初に挙げたペースティング図と同じ情報を持っています。

バタニン・ツリーと指標

バタニン・ツリーをテキスト形式の指標に書き写すのは非常に直接的で直感的です。

バタニン・ツリーの任意のパイエリアに注目します。例えば、前節のバタニン・ツリーのパイエリア $`f'`$ に注目します。次に、パイエリアの中心であるノードに注目します。その後で、当該ノードから出ている枝（親に向かう枝）の左右のパイエリアに注目します。これらの情報が、射〈セル〉のプロファイルを与えます。

1. パイエリア： 注目した射、ラベルは射の名前
2. ノード： その高さが射の次元
3. 枝の左側のパイエリア： 射の域
4. 枝の右側のパイエリア： 射の余域

パイエリア $`f'`$ からプロファイルを抽出すると：

$`\quad f': A \to B`$

コロンの個数と矢印の“太さ”は、次元〈高さ〉に合わせて調整します。

バタニン・ツリーの一番右、一番上のパイエリア $`\beta`$ に注目すれば、次のプロファイルが抽出できます。

$`\quad \beta :: h \twoto h'`$

ツリーを下へと（ルートのほうに）たどっていけば、プロファイルパスを書き下せます。

$`\quad \beta :: h \twoto h' : C \to D`$

テキスト形式の指標では、次元が低いほうから射を全部列挙するので、バタニン・ツリーをルートから上に向かって見ていきます。ルートが持つパイエリアの情報を次元付きで全部書き出すと：

$`\quad \T{0-mor }A\\
\quad \T{0-mor }B\\
\quad \T{0-mor }C\\
\quad \T{0-mor }D
`$

あるいは、

$`\quad \T{0-mor }A, B, C, D`$

次元が 1 である3つのノードに関してパイエリアの情報を全部書き出すと：

$`\quad \T{1-mor }f, f', f'' : A \to B\\
\quad \T{1-mor }g : B \to C\\
\quad \T{1-mor }h, h' : C \to D
`$

次元が 2 である3つのノードに関してパイエリアの情報を全部書き出すと：

$`\quad \T{2-mor }\alpha :: f \twoto f' : A \to B\\
\quad \T{2-mor }\alpha' :: f' \twoto f'' : A \to B\\
\quad \T{2-mor }\beta : h \twoto h' : B \to C
`$

ペースティング図に比べて、平面ツリーは辿り方〈traversal | トラバーサル〉の順序が明確で分かりやすいので、テキスト形式へのシリアライズが楽ちんです。コンピュータ処理のデータ構造としてバタニン・ツリーを採用すれば、データ構造の仕様も処理の実装も楽ちんです。

バタニン・ツリー、楽ちんでいいでしょ。

*1:初出の名前〈ラベル〉を区切るカンマは黒のほうがよかったと思いますが、面倒なのでカンマも含めて色付けしてます。