有限コレクション：再配置の圏から - 檜山正幸のキマイラ飼育記 (はてなBlog)

圏に類似した代数系〈category-like algebraic {system | structure}〉には、複圏〈オペラッド〉、多圏、モジュラーオペラッドなどがあります。これらの代数系は、「射」「セル」「オペレーション〈オペレーター〉」「辺」「ボックス」「テンソル」などと呼ばれるモノの集りです。それらのモノには境界プロファイル〈boundary profile〉が決まっています。

「射／セル／オペレーション〈オペレーター〉／辺／ボックス／テンソル」の境界プロファイルは、「対象／型／ソート／色／頂点」などと呼ばれるモノの有限コレクションです。

では、有限コレクションとは何でしょうか？その事例を挙げることは出来ます。

ペアは有限コレクションの一種である。
リストは有限コレクションの一種である。
バッグは有限コレクションの一種である。
有限集合は有限コレクションの一種である。
リストのペアは有限コレクションの一種である。

しかし、有限コレクションの一般的な定義はなかなかに難しいです。

有限コレクションのキチンとした定義がないと、境界プロファイルの一般論が出来ず、圏類似代数系の一般論も出来ません。この記事で、有限コレクションの定義の一例を挙げます。過去にも、「コレクション」「色付きコレクション」「クラスター」といった名前で、有限コレクションの定義を試みていますが、今回は新しい定義です。$`
\newcommand{\cat}[1]{ \mathcal{#1} }
\newcommand{\mbf}[1]{ \mathbf{#1} }
\newcommand{\mrm}[1]{ \mathrm{#1} }
\newcommand{\o}[1]{ \overline{#1} }
\newcommand{\u}[1]{ \underline{#1} }
\newcommand{\id}{ \mathrm{id} }
\newcommand{\In}{ \text{ in }}
%\newcommand{\On}{ \text{ on }}
\newcommand{\Iff}{ \Leftrightarrow }
\newcommand{\Imp}{ \Rightarrow }
\newcommand{\op}{ \mathrm{op}}
\newcommand{\hyp}{\text{－} }
\newcommand{\twoto}{\Rightarrow }
\newcommand{\LT}{\mathrel{\triangleleft} }
`$

内容：

概要
有限ツリーと有限順序ツリー
有限ツリーとポジション付き有限ツリー
ポジション付き有限順序ツリーと再配置の圏
ポジション・ラベリングの前層
ポジション・ラベリング前層の要素の圏
再配置同値関係と商集合
具体例

概要

有限コレクションを定義するために、次の手順に従います。

ポジション付き有限順序ツリー（対象）と再配置（射）の圏 $`\cat{R}`$ を考える。
圏 $`\cat{R}`$ 上に、ポジション・ラベリング達の集合を対応させる前層を考える。
前層の要素の圏（グロタンディーク構成）を考える。
要素の圏の対象集合〈set of objects〉を再配置同値関係で割った商集合を考える。
商集合の要素が、圏 $`\cat{R}`$ が決める有限コレクション。

けっこうめんどくさい手順です。この手順による構成には次のメリットがあります。

圏 $`\cat{R}`$ を変えることにより、色々な種類の有限コレクションが得られる。
有限コレクションの集合を作る操作 $`X \mapsto \mrm{FinColl}_{\cat{R}}(X)`$ が、集合圏上の自己関手になることが分かる。
さらに、$`\mrm{FinColl}_{\cat{R}}`$ を台関手とするモナドを構成できる場合もある（いつでも出来るわけではない）。
同様な方法が、他の場面でも使用できる。

特に、「同様な方法が、他の場面でも使用できる」ことは大きなメリットです。ストリング図テンプレート〈string diagram template〉やバエズ／ドーラン・ツリーの構成のときにも同様な方法を使います。圏類似代数系を構成したり調べたりするツール／スキルのひとつとして、有限コレクションの扱い方は重要だと思います。

以前のアプローチと違う点は：

以前は、有限コレクションを対象とする圏を考えていたが、今回は有限コレクションを要素とする集合しか考えない。
有限コレクションの表示〈presentation〉と有限コレクションを区別する。有限コレクションは、有限コレクションの表示達の同値類となる。
有限コレクションの表示のあいだの射（それを再配置と呼ぶ）は考える。が、再配置は同値関係を定義するために使うので、有限コレクション（同値類）のあいだの再配置は無意味となる。

この記事では、集合 $`X`$ に対する $`\mrm{FinColl}_{\cat{R}}(X)`$ を定義するところまで述べます。関手やモナドに仕立てるのは別な機会にします。

有限ツリーと有限順序ツリー

ツリーの定義は色々ありますが、最近の僕のお気に入りはカートメルツリーです（「C-システム、分裂ディスプレイクラス、カートメルツリー構造 // カートメルツリー構造」参照）。圏論的背景を離れて、純粋にツリー構造だけの定式化にすると、カートメルツリー〈Cartmell tree〉は以下の構成素からなります。

ノードの集合〈set of nodes〉： $`A \in |\mbf{Set}|`$
ルートノード〈root node〉： $`r\in A`$
レベル関数〈level function〉： $`\ell : A \to \mbf{N}`$
親関数〈father function〉： $`\mrm{ft} : (A\setminus \{r\}) \to A`$

カートメルのオリジナルでは、$`\ell`$ は長さ関数〈length function〉ですが、レベル関数と呼んだほうが自然でしょう。集合 $`A`$ の要素を「ノード」と呼ぶか「頂点」と呼ぶかは趣味の問題です。

次の法則を要請します。

$`\forall x\in A.( \ell(x) = 0 \Iff x = r )`$
$`\forall x\in A.( x \ne r \Imp \ell(\mrm{ft}(x)) = \ell(x) - 1)`$

子ノード達の集合 $`\mrm{Children}(\hyp)`$ を次のように定義します。

$`\text{For }x\in A\\
\quad \mrm{Children}(x) := \mrm{ft}^{-1}(x) = \{y\in A\mid \mrm{ft}(y) = x \}
`$

以下、カートメルツリーを単にツリー〈tree〉と呼びます。

ツリー $`T = (A, r, \ell, \mrm{ft})`$ に対して次の集合を定義します。

リーフノード〈leaf node〉の集合：
$`\mrm{Leaf}(T) := \{x\in A \mid x \ne r \land \mrm{Children}(x) = \emptyset \}`$
中間分岐ノード〈intermediate branching node〉の集合：
$`\mrm{Branch}(T) := A \setminus (\{r\} \cup \mrm{Leaf}(T))`$

ノードの集合 $`A`$ はルートノードを含むので空にはなりません。が、$`A = \{r\}`$ のことはあります。そのとき、$`\mrm{Leaf}(T) = \emptyset`$ かつ $`\mrm{Branch}(T) = \emptyset`$ です。無限な $`A`$ では、$`\mrm{Leaf}(T) = \emptyset`$ かつ $`\mrm{Branch}(T) \ne \emptyset`$ になり得ます。任意のノードは、ルートノード、リーフノード、中間分岐ノードのどれかに分類されます。ルートノードはリーフノードにも中間分岐ノードにもなり得ないことに注意してください。

ノードの集合 $`A`$ が有限集合であるツリーを有限ツリー〈finite tree〉と呼びます。以下、有限ツリーだけを考えます。有限ツリーでは、ツリーの高さが確定します（無限ツリーでも高さを持つツリーがありますが）。

$`\quad \mrm{Height}(T) := \mrm{max} \{k \in \mbf{A} \mid \exists x\in A. \ell(x) = k\}`$

任意のノード $`x\in A`$ の子ノードの集合 $`\mrm{Children}(x)`$ に全順序構造が定まっているツリーを順序ツリー〈ordered tree〉と呼びます。正確に言えば、“兄弟間全順序付きツリー”ですが、「順序ツリー」と短く呼ぶのが習慣です。ここで扱うのは、有限順序ツリー〈finite ordered tree〉だけです。

有限ツリーとポジション付き有限ツリー

$`T`$ がツリーのとき、構成素を次のように表すとします。

ノードの集合： $`\mrm{Node}(T) \in |\mbf{Set}|`$
ルートノード： $`\mrm{root}_T \in \mrm{Node}(T)`$
レベル関数： $`\ell_T : \mrm{Node}(T) \to \mbf{N}`$
親関数： $`\mrm{ft}_T : (\mrm{Node}(T)\setminus \{\mrm{root}_T\}) \to \mrm{Node}(T)`$
ルート以外のノードの集合： $`\mrm{Node}_\bullet(T) := \{x\in \mrm{Node}(T) \mid x \ne \mrm{root}_T \}`$

$`S, T`$ がツリーだとして、$`f`$ がツリーの準同型射〈homomorphism〉だとは：

$`f: \mrm{Node}(S) \to \mrm{Node}(T) \In \mbf{Set}`$
$`f(\mrm{root}_S) = \mrm{root}_T`$
以下の2つの可換図式を満たす。$`f_\bullet`$ は、$`f`$ の $`\mrm{Node}_\bullet(S)`$ への制限。

$`\quad \xymatrix{
\mrm{Node}(S) \ar[r]^f \ar[d]_{\ell_S}
& \mrm{Node}(T) \ar[d]^{\ell_T}
\\
\mbf{N} \ar@{=}[r]
& \mbf{N}
}\\
\quad \text{commutative}\In \mbf{Set}
`$

$`\quad \xymatrix{
\mrm{Node}_\bullet(S) \ar[r]^{f_\bullet} \ar[d]_{\mrm{ft}_S}
& \mrm{Node}_\bullet(T) \ar[d]^{\mrm{ft}_T}
\\
\mrm{Node}(S) \ar[r]_{f}
& \mrm{Node}(T)
}\\
\quad \text{commutative}\In \mbf{Set}
`$

ノードのあいだの親子関係を、記号 $`\LT`$ で表します。

$`\text{For }x, y \in \mrm{Node}(T)\\
\quad x \LT y :\Iff x = \mrm{ft}(y)
`$

ツリーの準同型射 $`f : S \to T`$ は、親子関係を保ちます。

$`\text{For }x, y \in \mrm{Node}(S)\\
\quad x \LT y \Imp f(x) \LT f(y)
`$

対象が有限ツリーで、射がツリーのあいだの準同型射であるような圏を $`\mbf{FinTree}`$ とします。

リーフノードの集合の部分集合を指定した有限ツリーをポジション付き有限ツリー〈positioned finite tree〉と呼びます。指定した部分集合の要素をポジションノード〈position node〉、あるいは単にポジション〈position | 位置〉と呼びます。「ポジション」はコンテナ（「圏論的コンテナ」参照）の用語を借用しました。

ポジション付き有限ツリーは次のように書きます。

$`\quad T = (\mrm{Node}(T), \mrm{root}_T, \ell_T, \mrm{ft}_T, \mrm{Pos}(T))`$

$`\mrm{Pos}(T) \subseteq \mrm{Leaf}(T)`$ という条件は課します。

圏 $`\mbf{FinTree}`$ の射は、ツリーのリーフノードをリーフノードに移すとは限りません。リーフノードを中間分岐ノードに移すかも知れません。ましてや、ポジションをポジションに移す保証は全然ありません。ポジション付き有限ツリーを対象として、ポジションをポジションに移す準同型射だけを射とする圏を $`\mbf{PosFinTree}`$ とします。圏 $`\mbf{PosFinTree}`$ の射をポジション保存ツリー準同型射〈position-preserving tree homomorphism〉と呼ぶことにします。圏 $`\mbf{PosFinTree}`$ は圏 $`\mbf{FinTree}`$ の部分圏ではありませんが、忘却関手 $`\mbf{PosFinTree} \to \mbf{FinTree}`$ は持ちます。

圏 $`\mbf{PosFinTree}`$ 上では、$`\mrm{Pos}`$ を関手に拡張することができます。ツリー準同型射をポジション集合上に制限した写像を定義できるからです。

$`\quad \mrm{Pos} : \mbf{PosFinTree} \to \mbf{Set} \In \mbf{CAT}`$

ポジション付き有限順序ツリーと再配置の圏

ここで、少し変わった圏を定義します。対象はポジション付き有限順序ツリー〈positioned finite ordered tree〉です。兄弟間全順序を持ちます。しかし、射は兄弟間の順序を考慮しないポジション保存ツリー準同型射である圏を考えます。この圏を $`\mbf{PosFinOrdTree}^{\mrm{unord}}`$ とします。右肩の $`\mrm{unord}`$ は、射が順序なし（順序無視）であることを示します。

$`\mbf{PosFinOrdTree}^{\mrm{unord}}`$ の射を再配置〈rearrangement〉と呼ぶことにします。再配置は、ツリーの親子関係とポジションであることは保ちますが、兄弟の長幼の順は入れ替えてしまうかも知れません。

圏 $`\mbf{PosFinOrdTree}^{\mrm{unord}}`$ の部分圏を再配置の圏〈category of rearrangements〉と呼びます。「再配置の圏」は、特定の圏を意味するのではなくて、圏達のクラスに所属する圏を指す言葉です。

　　$`\cat{R}`$ は再配置の圏 ⇔ $`\cat{R}`$ は $`\mbf{PosFinOrdTree}^{\mrm{unord} }`$ の部分圏

例(1) 高さ 1 の有限順序ツリーに“リーフをすべてポジション”としたポジション付きツリーを対象とする $`\mbf{PosFinOrdTree}^{\mrm{unord}}`$ の充満部分圏は再配置の圏です。これは、有限全順序集合を対象として、任意の写像を射とする圏と圏同値な圏です。
例(2) 再配置として兄弟間の全順序を保つ準同型射を採用してもかまいません。例えば、順序二分木〈ordered binary tree〉に“リーフはすべてポジション”としたポジション付きツリーを対象として、ポジションと兄弟間の全順序を保つツリー準同型射を射〈再配置〉とする圏も再配置の圏の例です。
例(3) すべてのポジション付き有限順序ツリー達を対象集合として、恒等射だけを射とする圏（つまり離散圏）も再配置の圏の例です。
例(4) 圏 $`\mbf{PosFinOrdTree}^{\mrm{unord}}`$ は $`\mbf{PosFinOrdTree}^{\mrm{unord}}`$ の部分圏であるので、$`\mbf{PosFinOrdTree}^{\mrm{unord}}`$ 自体も再配置の圏の例です。
例(5) 圏 $`\mbf{PosFinOrdTree}^{\mrm{unord}}`$ の同型射〈可逆射〉だけを射とする充満部分圏（$`\mbf{PosFinOrdTree}^{\mrm{unord}}`$ のコア亜群〈core groupoid〉と呼ぶ）は $`\mbf{PosFinOrdTree}^{\mrm{unord}}`$ の部分圏なので、これも再配置の圏の例です。
例(6) ルートノード以外にリーフノードが1つだけ（ノードが2個）の有限順序ツリーを考え、ポジションはリーフノードとします。兄弟は一人なので、実は兄弟間全順序に意味はありません。そのような2ノード・ツリーだけを対象とする $`\mbf{PosFinOrdTree}^{\mrm{unord}}`$ の充満部分圏は再配置の圏の例です。

ポジション・ラベリングの前層

$`\cat{R}`$ を再配置の圏とします。つまり、次が成立しています。

$`\quad \cat{R} \subseteq \mbf{PosFinOrdTree}^{\mrm{unord}} \In \mbf{CAT}`$

任意の集合 $`X \in |\mbf{Set}|`$ に対して、圏 $`\cat{R}`$ 上の前層 $`\mrm{PL}_X`$ を定義します。'PL' は position labeling からです。以下の $`\mrm{PL}_X(T)`$ の要素は、ツリー $`T`$ の$`X`$-値ポジション・ラベリング〈$`X`$-valued position labeling〉と呼びます。

$`\mrm{PL}_X : \cat{R}^\op \to \mbf{Set} \In \mbf{CAT}\\
\text{For }T \in |\cat{R}|\\
\quad \mrm{PL}_X(T) := \mbf{Set}(\mrm{Pos}(T), X)\\
\text{For }f:S \to T \In \cat{R}
\quad \mrm{PL}_X(f) := ( (\mrm{Pos}(f))^* : \mbf{Set}(\mrm{Pos}(T), X) \to \mbf{Set}(\mrm{Pos}(T), X) \In \mbf{Set})
`$

ここで、$`(\mrm{Pos}(f))^*`$ は、写像 $`\mrm{Pos}(f)`$ によるプレ結合引き戻しです。集合圏のホム双関手を使って書けば：

$`\quad (\mrm{Pos}(f))^* := \mbf{Set}(\mrm{Pos}(f), \id_X)`$

この形だと、対象パートも射パートも同じ形なので、$`\mrm{PL}_X`$ の定義は次のように書けます。ただし、$`X`$ と $`\mrm{id}_X`$ のオーバーロードは使います。

$`\quad \mrm{PL}_X(\hyp) := \mbf{Set}(\mrm{Pos}(\hyp), X)`$

集合圏のホム双関手を指数形式で書けば、次のように簡潔に書けます。

$`\quad \mrm{PL}_X(\hyp) := X^{\mrm{Pos}(\hyp)}`$

インデックス／引数の渡し方の書き方を変えてみます。

$`\quad \mrm{PL}[\hyp](X) := \mbf{Set}(\mrm{Pos}(\hyp), X)`$

Diag構成（「Diag構成：圏論的構成法の包括的フレームワークとして」参照）を知っているなら、$`\mrm{PL}`$ はDiag構成の特別な場合だと分かるでしょう。

$`\quad \mrm{PL}[\hyp](X) := \mbf{Set}\text{-}\mrm{Diag}^{\cat{R},\mrm{Pos}}[\hyp](X)`$

Diag構成の言葉で言えば：

アンビエント・ドクトリン（この場合は圏）は $`\mbf{Set}`$
形状ドクトリンは $`\cat{R}`$
編入関手は $`\mrm{Pos} : \cat{R} \to \mbf{Set}`$
ターゲット対象は $`X \in |\mbf{Set}|`$

前層 $`\mrm{PL}_X`$ の定義は、ターゲット対象（ラベリングの値の集合）$`X`$ を固定して、形状ドクトリン $`\cat{R}`$ 上でのDiag構成（を行う関手）です。ツリーのポジション・ラベリングは、Diag構成の言葉では図式〈diagram〉です。Diag構成はいたる所に出現しますが、ここでもまた登場しました。

ポジション・ラベリング前層の要素の圏

再配置の圏 $`\cat{R}`$ と集合 $`X`$ が与えられると、前層 $`\mrm{PL}_X`$ が構成できました（正確には $`\mrm{PL}^{\cat{R}}_X`$ のように $`\cat{R}`$ も添えるべきです）。

$`\quad \mrm{PL}_X : \cat{R}^\op \to \mbf{Set} \In \mbf{CAT}`$

前層を特別なインデックス付き圏だとみなして、グロタンディーク構成を施して作った平坦化圏〈flattened category〉を要素の圏〈category of elements〉と呼びます。要素の圏は $`\mrm{El}(\hyp)`$ と書きましょう。

要素の圏 $`\mrm{El}(\mrm{PL}_X)`$ を具体的に記述すると：

要素の圏の対象は、ポジション付き有限順序ツリー $`S`$ と、ポジション・ラベリング $`a : \mrm{Pos}(S) \to X \In \mbf{Set}`$ のペア（依存ペア） $`(S, a)`$
2つの対象 $`(S, a), (T, b)`$ のあいだの射は、再配置 $`f:S \to T \In \cat{R}`$ と等式 $`a = f^*(b)`$ のペア $`(f, a = f^*(b))`$ 。$`f^*`$ は、$`f`$ によるプレ結合引き戻し。
要素の圏の射を、別な言い方で定義するなら、等式 $`a = f^*(b)`$ を満たす3つ組 $`(f, a, b)`$ が $`(S, a)`$ から $`(T, b)`$ への射。

要素の圏 $`\mrm{El}(\mrm{PL}_X)`$ から $`\cat{R}`$ への射影関手 $`P`$ が定義できて、次はファイバー付き圏（「関手のデカルト射とファイバー付き圏」参照）になります*1。

$`\quad P:\mrm{El}(\mrm{PL}_X) \to \cat{R} \In \mbf{CAT}`$

しかし、今回はファイバー付き圏（つまり射影関手）は利用しません。

再配置同値関係と商集合

一般に、圏 $`\cat{C}`$ の対象の集合 $`|\cat{C}|`$ に非常に強い同値関係を導入できます。「強い」とは、同一視能力が強く、矢鱈になんでも同一視してしまう、ということです。強い同値関係による分類は荒っぽい分類となります。

まず、（同値関係とは限らない）関係 $`\sim`$ を次のように定義します。

$`\text{For} A, B \in |\cat{C}|\\
\quad A \sim B :\Iff \exists f\in \mrm{Mor}(\cat{C}).( f : A \to B \In \cat{C})
`$

2つの対象 $`A, B`$ を繋ぐ射が（なんでもいいから）在れば $`A\sim B`$ です。この二項関係 $`\sim`$ から生成される最小の同値関係を $`\simeq`$ とします。任意の圏 $`\cat{C}`$ に対して $`\simeq`$ を一意的に定義できます。商集合 $`|\cat{C}|/\simeq`$ は、$`\pi_0(\cat{C})`$ と書かれることがあります。$`|\cat{C}|/\simeq`$ の要素は、ある種の“連結成分”と考えられるので、集合 $`|\cat{C}|/\simeq`$ は、ある種の“0次ホモトピー集合”です。$`\pi_0(\hyp)`$ は0次ホモトピー集合の記法です。

さて、要素の圏 $`\mrm{El}(\mrm{PL}_X)`$ の場合を考えて、$`|\mrm{El}(\mrm{PL}_X)|`$ 上の同値関係 $`\simeq`$ を、再配置同値関係〈rearrangement equivalece relation〉と呼ぶことにします。2つの対象 $`(S, a), (T, b)`$ が同値であるのは、再配置（$`\cat{R}`$ の射）のジグザグ列をたどって $`a`$ から $`b`$ に移れることです。ジグザグ列の一例（いろいろなタイプがある）は：

$`\quad a \overset{f_0^*}{\to} \bullet \overset{f_1^*}{\leftarrow} \bullet \cdots \bullet \overset{f_n^*}{\to} b`$

商集合 $`|\mrm{El}(\mrm{PL}_X)|/\simeq`$ が、我々の目的である有限コレクション〈finite collection〉（有限個のモノを集めて編成したデータ）の集合です。ポジション・ラベリング前層 $`\mrm{PL}_X`$ と同値関係 $`\simeq`$ の構成には、再配置の圏 $`\cat{R}`$ も関与しているので、$`\cat{R}`$ も添えて $`\mrm{PL}^\cat{R}_X`$、$`\simeq^\cat{R}`$ と書くとして：

$`\quad \mrm{FinColl}_\cat{R}(X) := |\mrm{El}(\mrm{PL}^\cat{R}_X)|/{\simeq^\cat{R}}`$

再配置の圏 $`\cat{R}`$ により、有限コレクションの種類が決まります。集合 $`X`$ は、有限コレクションの“成分”を決めます。

商集合 $`|\mrm{El}(\mrm{PL}^\cat{R}_X)|/{\simeq^\cat{R}}`$ の要素が有限コレクションなので、商を作る前の $`|\mrm{El}(\mrm{PL}^\cat{R}_X)|`$ の要素は有限コレクションの表示〈presentation of finite collection〉と呼びます。有限コレクションの表示は、有限コレクション（同値類）の代表元です。

具体例

前節までに述べた方法で、典型的な有限コレクションを定義してみます。

集合 $`X`$ の要素を成分〈項目〉とするリスト
集合 $`X`$ の要素を成分とするバッグ
集合 $`X`$ の要素を要素とする有限集合
集合 $`X`$ の要素を成分とする順序ペア〈ordered pair〉
集合 $`X`$ の要素を成分とする順序無しペア〈unordered pair〉
集合 $`X`$ の要素を成分〈項目〉とする2つのリストの順序ペア

それぞれの有限コレクションを定義する再配置の圏を $`\cat{R}1, \cat{R}2, \cdots , \cat{R}6`$ とします。ポジション付き有限順序ツリーを $`(T, A)`$ のように書きます。$`T`$ は有限順序ツリー、$`A`$ はポジション集合です。$`\mrm{card}(\hyp)`$ は集合の基数です。

$`(T, A) \in |\cat{R}1|`$ である条件：
1. $`\mrm{Height}(T) \le 1 `$
2. $`A = \mrm{Leaf}(T)`$ （$`\mrm{Height}(T) = 0`$ のときは $`A = \emptyset`$ ）
$`\cat{R}1`$ の射は、ツリーの兄弟間の順序を保つ同型射〈可逆射〉。
$`\cat{R}1`$ は、すべての有限全順序集合と順序同型射の圏（亜群）と圏同値。

バッグ

$`(T, A) \in |\cat{R}2|`$ である条件：
1. $`\mrm{Height}(T) \le 1`$
2. $`A = \mrm{Leaf}(T)`$
$`\cat{R}2`$ の射は、ツリーの兄弟間の順序を考慮しない同型射〈可逆射〉。

有限集合

$`(T, A) \in |\cat{R}3|`$ である条件：
1. $`\mrm{Height}(T) \le 1`$
2. $`A = \mrm{Leaf}(T)`$
$`\cat{R}3`$ の射は、ノード集合のあいだの写像として全射なもの（兄弟間の順序は考慮しない）。

順序ペア

$`(T, A) \in |\cat{R}4|`$ である条件：
1. $`\mrm{Height}(T) = 1`$
2. $`\mrm{card}(\mrm{Node}(T)) = 3`$
3. $`A = \mrm{Leaf}(T)`$
$`\cat{R}4`$ の射は、ツリーの兄弟間の順序を保つ同型射〈可逆射〉。

順序無しペア

$`(T, A) \in |\cat{R}5|`$ である条件：
1. $`\mrm{Height}(T) = 1`$
2. $`2 \le \mrm{card}(\mrm{Node}(T)) \le 3`$
3. $`A = \mrm{Leaf}(T)`$
$`\cat{R}5`$ の射は、ノード集合のあいだの写像として全射なもの（兄弟間の順序は考慮しない）。

リストの順序ペア

$`(T, A) \in |\cat{R}6|`$ である条件：
1. $`1 \le \mrm{Height}(T) \le 2`$
2. $`\mrm{card}(\{x\in \mrm{Node}(T) \mid \ell(x) = 1\}) = 2`$
3. $`\mrm{Height}(T) = 2`$ のときは、$`A = \{x\in \mrm{Leaf}(T) \mid \ell(x) = 2\}`$
4. $`\mrm{Height}(T) = 1`$ のときは、$`A = \emptyset`$
$`\cat{R}6`$ の射は、ツリーの兄弟間の順序を保つ同型射〈可逆射〉。

*1:ファイバーが離散圏になる特別なファイバー付き圏です。