Assume labeled rooted trees with labels from a fixed set $\{1\ldots m\}$.
For a tree $T$, we have:
- $V(T)$ the set of vertexes,
- $root(T)$ the root of the tree,
- $l_T: V(T)\rightarrow \{1\ldots m\}$ the labeling function,
- $children: V(T) \rightarrow 2^{V(T)}$ maps vertexes to their set of child nodes.
We will extend the definition of $l_T$ for set of vertexes: $l_T(W)$ is a multiset of labels of the set $W \subseteq V(T)$.
Assume an infinite sequence of labeled rooted trees $\{T_i\}_{i=1}^\infty$.
Does there exist indexes $i<j$ such that $T_i \leq T_j$?
$T_i \leq T_j$, if there is an injection $f: T_i\rightarrow T_j$ such that:
- $f(root(T_i)) = root(T_j)$
- $l_{T_i}(v) = l_{T_j}(f(v))$ for each $v\in V(T_i)$
- $l_{T_i}(children(v)) \subseteq l_{T_j}(children(f(v)))$ for each $v\in V(T_i)$