森っぽいfunctional graphは直積に関して簡約法則が成り立つ

集合$S$と写像$f:S \rightarrow S$の組$(S,f)$を標識 functional graphと言う.
また$|S|$を$(S,f)$の頂点数と言う.
頂点数が有限個の標識 functional graph全体の集合を$\mathbf{G}$とする.

functional graph$F = (S,f)$, $G = (T,g)$について, 全単射な写像$h:S \rightarrow T$が存在し
$h \circ f \circ h^{-1} = g$が成り立つとき$F$と$G$は同型であると言い, $F \cong G$と表す.
また$h$を$F$から$G$への同型と言う.

$\mathbf{G} / \cong$の元を非標識 functional graphと言う.
非標識 functional graph 全体の集合を$\mathbb{G}$とする.

閉路がすべて自己ループである$\mathbf{G}$の元を標識 functional graph 森と言う.
標識 functional graph 森のうち連結であるものを標識 functional graph 木と言う.
非標識のほうも同様に定義する.
非標識 functional graph 森全体の集合を$\mathbb{f}$, 非標識 functional graph 木全体の集合を$\mathbb{t}$とする.

$A=(G,f),B=(H,g) \in \mathbf{G}$について,
$A \cdot B = (G \times H, f \times g)$とする. ($f \times g:G \times H \rightarrow G \times H$は$(x,y) \mapsto (f(x),g(y))$という写像)
また$A + B$を非交和で定義する.

高さ$0,1$の木は, 根の入次数を$n$とすると非負整数$n$と同一視できる.
高さ$n-1$以下の木の表し方が定義されているとき, 高さ$n$以下の木$t$は, $t$の根の子を$a_1, \cdots , a_k$とすると
$(t \setminus (深さnの頂点),\hspace{4pt} \{ (a_1を根とする木), \cdots , (a_nを根とする木) \})$という, 高さ$n-1$以下の木と, 高さ$n-1$以下の木の多重集合の組として見ることで, 実際の木と一対一の対応のある表し方が定義できる.

$S=(s,\{ s_1 , \cdots , s_i \}),T=(t,\{ t_1 , \cdots , t_i \})$が高さ$n$以下の木のとき,
$$S \cdot T = (s \cdot t, \{ s_1 , \cdots , s_i \} \cdot \{ t_1 , \cdots , t_i \})$$
とする. ただし多重集合の積は, 集合同士の積と同じようにそれぞれの元を掛け合わせてできた元全体の集合である(多重集合なので重複も含む).

高さ$0,1$の木については非負整数と同一視することで狭義全順序$<$を定義する.
高さ$n-1$以下の木について狭義全順序$<$が定義されているとき, 高さ$n$以下の木$T_1 , T_2$について, $T_1 < T_2$を

• 高さを比べたとき$T_2$の方が高い
• 高さが同じであれば, $T_1 = (t_1, S_1)$, $T_2 = (t_2, S_2)$のとき$$T_1 < T_2 \Leftrightarrow t_1 < t_2 または (t_1 = t_2 かつ S_1 <_M S_2)$$

と定義する.

$Cut_n(x) = (xの深さがnより大きい頂点を全て削除して得られる木)$とする.

$X,Y \in \mathbb{t}$について, $X< Y$を
$X,Y$の無限列表示が$(X_0,X_1,\cdots), (Y_0,Y_1,\cdots)$であるとき
$$X< Y \Leftrightarrow あるiが存在しX_i < Y_i$$
とすると, $X_n = Cut_n(X_m) \hspace{4pt} (m>n)$なので命題2よりこれはwell-defindである.
そして命題4により$X,Y,A \in \mathbb{t}$について$X< Y \Rightarrow AX< AY$となる.