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

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

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

［参照用 記事］

カートメル林の圏

雑記／備忘

木〈ツリー〉や林〈フォレスト〉は重要なデータ構造です。以下の過去記事で説明したことがあります。

カートメル〈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`$ は次の構成素からなります。

  1. ノード達の集合： $`\mrm{Node}(A) \in |{\bf Set}|`$
  2. ノード達の集合の上の二項関係： $`(\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' \,)`$

カートメル林の条件〈公理〉をまとめると：

  1. 親子関係 $`\ILT`$ はアンチ反射的である。（親と子が一致することはない。）
  2. 親子関係 $`\ILT`$ は整礎である。（無限な減少列はない。）
  3. 親子関係の親が存在するならば一意的である。

[追記]アンチ反射性は不要でしたね。もし $`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. 無サイクルである。
  2. すべての頂点で、出る辺は1本以下である。
  3. （少なくとも1つの）出る辺がない頂点（ルート）が存在する。
  4. どの頂点からも、ルートに至るパスが存在する。

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:「反反射的」は誤字のように見えるので「アンチ」を使います。