木〈ツリー〉や林〈フォレスト〉は重要なデータ構造です。以下の過去記事で説明したことがあります。
- 木と林(有向グラフ)
- 木と林(有向グラフ) その2
- レベル付き林の圏 (最後の追記参照)
カートメル〈John Cartmell〉による木・林の定義が使いやすいと最近気付いたので、カートメルの定義に基づいて林の圏を構成します。木〈ツリー〉の圏は林の圏の部分圏となります。$`\newcommand{\In}{\text{ in }}
\newcommand{\mrm}[1]{\mathrm{#1} }
\newcommand{\mbf}[1]{\mathbf{#1} }
\newcommand{\u}[1]{\underline{#1} }
\newcommand{\Imp}{\Rightarrow}
\newcommand{\Iff}{\Leftrightarrow}
%\newcommand{\twoto}{\Rightarrow }
%\newcommand{\op}{ \mathrm{op} } % used
%\newcommand{\hyp}{\text{-} } % used
\newcommand{\ILT}{ \triangleleft } % immediately less than
\newcommand{\IGT}{ \triangleright } % immediately greater than
`$
内容:
カートメルによるツリーの定義
カートメル/ヴォエヴォドスキーによるC-システムは、ある種の圏ですが、その対象達の集合はツリー構造を持ちます(「C-システム、分裂ディスプレイクラス、カートメルツリー構造」参照)。カートメルは、ツリー構造を、長さ関数 $`\ell`$ と親関数 $`\mrm{ft}`$ を備えた集合と定義しました。
親関数 $`\mrm{ft}`$ により、拡張関係〈extension relation〉という関係 $`\ILT`$ を定義できます。
$`\quad x \ILT y :\Iff x = \mrm{ft}(y)`$
$`\ell, \mrm{ft}`$ の代わりに、ノードのあいだの関係 $`\ILT`$ をベースにしてツリーを定義することもできます。この記事では、$`\ILT`$ をベースにしたツリーの定義を採用します。型理論や拡張包括構造とは独立な話なので、関係 $`\ILT`$ は(拡張関係ではなくて)親子関係〈parent-child relation〉と呼びます。
林〈フォレスト〉は木〈ツリー〉の集まりのことですが、木と林は関連させて一緒に考えたほうが便利です。ここでは、林達が形成する圏を先に定義して、木〈ツリー〉の圏はその部分圏として定義することにします。
カートメル林
カートメル林〈Cartmell forest〉 $`A`$ は次の構成素からなります。
- ノード達の集合: $`\mrm{Node}(A) \in |{\bf Set}|`$
- ノード達の集合の上の二項関係: $`(\ILT_A) \subseteq \mrm{Node}(A)\times \mrm{Node}(A)`$
ノード達の集合を、カートメル林の台集合〈underlying set〉と考えて、$`\u{A} := \mrm{Node}(A)`$ と書きます。$`\u{A}`$ は空集合でもかまいません。空なツリーは認めませんが、空な林(木が一本も生えてない場所)は認めます。
関係 $`\ILT_A`$ は次の条件〈公理 その1〉を満たすとします。この条件を満たす関係はアンチ反射的〈anti-reflexive〉ということがあります*1。
$`\quad \forall x, y \in \u{A}.\, x \ILT_A y \Imp x \ne y`$
$`\u{A} = \emptyset`$ なら、この条件は自動的に満たされます。それは、上の論理式は以下のようにも書けるからです。'$`\Imp`$' の左側〈前件〉が偽なら、命題は問答無用に真です。
$`\quad \forall x, y.(\, (x \in \u{A} \land y\in \u{A}) \Imp (x \ILT_A y \Imp x \ne y) \,)`$
関係 $`\ILT_A`$ を、カートメル林 $`A`$ の親子関係〈parent-child relation〉と呼びます。下付きの $`A`$ は、紛れがないなら省略します。
以下はすべて同じ意味だとします。
- $`x \ILT y`$
- $`x`$ は $`y`$ の親〈parent | father〉である。
- $`y \IGT x`$
- $`y`$ は $`x`$ の子〈child〉である。
カートメル林の親子関係は、整礎な関係〈well-founded relation〉であるという条件〈公理 その2〉を付けます。このことを以下に説明します。
便宜上、$`y \IGT x`$ のとき、「$`x`$ は $`y`$ より小さい」と考えます。次の列は減少列ということになります。
$`\quad x_0 \IGT x_1 \IGT \cdots \IGT x_n`$
$`\ILT`$ が(あるいは $`\IGT`$ が)整礎であるとは、上記のような減少列で無限に伸びるものが存在しないことです。減少列は有限で終わってしまいます。列の最後の要素〈ノード〉 $`y := x_n`$ は次の性質を持ちます。
$`\quad \lnot \exists x\in \u{A}.\, x \ILT y`$
上記の性質を持つ要素〈ノード〉 $`y`$ は、カートメル林 $`A`$ のルート〈root〉と呼びます。$`\u{A}`$ が空でないならルートは存在します。カートメル林 $`A`$ のルート達の集合を $`\mrm{Root}(A)`$ とします。次が成立します。
$`\quad \mrm{Root}(A) = \emptyset \Iff \u{A} = \emptyset`$
カートメル林の条件〈公理 その3〉として、親の一意性を入れます。それは次の論理式で表せます。
$`\quad \forall y, x, x'\in \u{A}.(\, x\ILT y \land x'\ILT y \Imp x = x' \,)`$
カートメル林の条件〈公理〉をまとめると:
- 親子関係 $`\ILT`$ はアンチ反射的である。(親と子が一致することはない。)
- 親子関係 $`\ILT`$ は整礎である。(無限な減少列はない。)
- 親子関係の親が存在するならば一意的である。
[追記]アンチ反射性は不要でしたね。もし $`x \IGT x`$ である $`x`$ があるなら、$`x \IGT x \IGT x \IGT \cdots`$ という無限列を作れてしまいます。つまり、整礎の条件からアンチ反射性は出るので、これは公理としては不要です。[/追記]
カートメル林の圏
$`A = (\u{A}, \ILT_A)`$ と $`B = (\u{B}, \ILT_B)`$ をカートメル林とします。台集合のあいだの写像 $`f:\u{A} \to \u{B}`$ がカートメル林のあいだの準同型射〈homomorphism〉であるとは次のことです。
$`\quad \forall x, y\in \u{A}.(\, x\ILT y \Imp f(x)\ILT g(y) \,)`$
これは要するに、写像 $`f`$ が親子関係を保つことです。
カートメル林の準同型射がルートを保つことは要求していません。例えば、以下のような $`f`$ では、ルートがルートには移りません。
- $`A := \{0\ILT 1 \}`$
- $`B := \{0\ILT 1\ILT 2\}`$
- $`f := (0\mapsto 1, 1\mapsto 2)`$
親子関係さえ保てばいいので、準同型射は単射である必要もありません。親子関係が空(どんな要素のペアも親子関係にない)でもいいので、任意の写像はカートメル林の準同型射とみなすことができます。
カートメル林のあいだの準同型射の結合〈合成〉は再び準同型射になることは容易に示せます。台集合の恒等写像がカートメル林の準同型射になり、それが圏論の意味の恒等射になることもほぼ自明です。これらにより、カートメル林達とそのあいだの準同型射達は圏を形成します。この圏を、カートメル林の圏〈category of Cartmell forests〉と呼び $`\mbf{CForest}`$ と書きます。
カートメル木の圏
$`\mrm{Root}(A)`$ が単元集合〈singleton set〉であるようなカートメル林をカートメル木〈カートメルツリー | Cartmell tree〉と呼びます。$`A`$ がカートメル木であるとき、長さ関数 $`\ell`$ と親関数 $`\mrm{ft}`$ は定義できます。
$`x\in \u{A}`$ に対して、$`x \IGT x_1`$ なる $`x_1`$ が存在しないとき $`\ell(x) = 0`$ とします。木の条件「$`\mrm{Root}(A)`$ が単元集合」から次が言えます。
$`\quad \ell(x) = 0 \Iff x\in \mrm{Root}(A)`$
$`x\in \u{A}`$ がルートでないとき $`x\IGT x_1 \IGT \cdots \IGT x_n`$ という減少列で最長のものが一意に取れます。この長さ $`n`$ を $`\ell(x)`$ と定義します。また、ルート以外の $`x`$ に対して $`x \IGT y`$ である $`y`$ は一意に決まるので、それを $`\mrm{ft}(x)`$ とします。以下も明らかでしょう。
- $`\ell(\mrm{ft}(x)) = \ell(x) - 1 \text{ where } x \not\in \mrm{Root}(A)`$
これらは、オリジナルのカートメルの公理です(「C-システム、分裂ディスプレイクラス、カートメルツリー構造 // カートメルツリー構造」参照」)。
ツリーに限らず、一般のカートメル林に対しても $`\ell, \mrm{ft}`$ を定義できます。カートメル林の準同型射は、$`\mrm{ft}`$ を保つ写像としても定義できます。しかし、$`\ell`$ を保つとは限りません。
カートメル木を対象とする、$`\mbf{CForest}`$ の充満部分圏をカートメル木〈カートメルツリー〉の圏と呼び、$`\mbf{CTree}`$ と書きます。
他の定義との比較
「木と林(有向グラフ)」では、林は次の条件を満たす有向グラフとして定義しました。
- 無サイクルである。
- すべての頂点で、出る辺は1本以下である。
- (少なくとも1つの)出る辺がない頂点(ルート)が存在する。
- どの頂点からも、ルートに至るパスが存在する。
3番目の条件から台集合が空な場合は除外されますが、空な場合も許せば、この記事のカートメル林の定義と同じになります。
有向グラフをベースにしようが、親子関係をベースにしょうが、定義されるモノに変わりはありません。カートメル流の定義のメリットは、台集合(ノードの集合)と親子関係 $`\ILT`$ だけしか使ってないことでしょう。
カートメル林 $`A`$ の親子関係 $`\ILT_A`$ の反射的推移的閉包をとると、それは順序関係になります。$`\ILT_A`$ から定義された順序関係を $`\le`$ とすると、順序関係 $`\le`$ は次の性質を持ちます。
- 任意の $`x\in \u{A}`$ に対して、部分集合 $`\{y\in \u{A} \mid y \le x\}`$ は有限な全順序集合である。
ワイスは、上記の性質を持つ順序を基本としてツリーの定義をしています。
- [Wei10-11]
- Title: From Operads to Dendroidal Sets
- Author: Ittay Weiss
- Submitted: 20 Dec 2010 (v1), 12 Jun 2011 (v3)
- Pages: 40p
- URL: https://arxiv.org/abs/1012.4315
ワイスの場合、台集合 $`\u{A}`$ の要素を頂点〈ノード〉ではなくて辺〈エッジ〉と考えています。ルートやリーフもエッジです。このような発想については「開放ツリー: 半グラフ・ベースのツリー」で書いています。
そしてそれから
この記事内では、カートメル流に定義したということで、$`\mbf{CForest}, \mbf{CTree}`$ など、先頭に $`\mbf{C}`$ を付けた名前を使いましたが、定義される対象物は定義の仕方によらないので、後で実際に使うときは $`\mbf{Forest}, \mbf{Tree}`$ という名前で使うつもりです。
林や木〈ツリー〉自体は、形状を持っているだけでそれ以上の意味は持たないのですが、文脈と設定によりものすごく多様な解釈が可能です。それ自体には味がなくても、味付け次第で色々な料理に使える食材のようなものです。
[追記]
「レベル付き林の圏」で定義したレベル関数 $`\mrm{level}`$ は、カートメルの長さ関数 $`\ell`$ と同じです。ネクスト関数 $`\mrm{next}`$ はカートメルの親関数 $`\mrm{ft}`$ と同じです。結局、レベル付き林/レベル付き木は、カートメルのオリジナルの定義に沿った林/木と同じです。
「レベル付き林の圏」は2024-03-25 の記事なので、C-システムを知る前で、偶然同じ定義をしていたわけです。忘れていたけど。
2024-03-25 の過去記事の目的は、集合圏に限らない圏 $`\mathcal{C}`$ に対してレベル付き林の圏 $`\mrm{LvlForeset}(\mathcal{C})`$ を作る構成法です。過去記事で空集合の扱いを気にしてますが、今思うに、空集合を特に気にする必要はないですね。
この記事の親子関係を使う方法は簡潔で分かりやすいですが、要素概念がない一般の圏 $`\mathcal{C}`$ だとそのままでは使えないですね。ルートを保存する必要がない射の定義が難しいなー。終対象があればある程度いけるかな?
[/追記]
*1:「反反射的」は誤字のように見えるので「アンチ」を使います。