## Definitions

The term *tree*^{1} below stands for a triple $(A, u, f)$, where:

- $A$ is a nonempty set;
- $u$ is an element of $A$, called the tree's root;
- $f \colon A \setminus\!\{u\} \to A$ is a function satisfying the following property: the sequence of its iterations
^{2}on any initial $x \in A$ ultimately ends in $u$. In other words, $\forall x \in A, \exists n \in \mathbb N_0\!: f^n(x)=u$, where $\mathbb N_0$ is the set of nonnegative integers, $f^0(x)=x$.

A tree is called a *divine tree* if it contains a "branch" of infinite length, i.e. there is an infinite sequence $x_0 = u, x_1, x_2, x_3, \dots$ such that $x_n = f(x_{n+1})$ for any $n \ge 0$. Otherwise it is called a *devil's tree*.^{3}

If there are two trees, $\tau =(A, u, f)$ and $\theta =(B, v, g)$, then $\tau$ is said to be *embeddable* in $\theta$, that is denoted by $\tau \preccurlyeq \theta$, if there is a function $h \colon A \to B$ such that:^{4}

- $x = u \iff h(x) = v$;
- $\forall x \in A \setminus\!\{u\}\!: h(f(x)) = g(h(x))$.

For any nonempty set $B$, let $\Upsilon _B$ be the set of all possible devil's trees on all nonempty $A \subseteq B$. Also, let $\Omega_B$ be the set of all ordinal numbers with cardinality not greater than $|B| - 1$.^{5}

A function $\psi \colon \Upsilon _B \to \Omega_B$ is called *gapless* if its image $I = \psi(\Upsilon _B)$ is an initial segment, i.e. $\forall \alpha \in I, \beta < \alpha\!: \beta \in I$.

## Statements

It is not hard to show that $\preccurlyeq$ is reflexive and transitive, i.e. it is a **preorder** on the class of all trees. But it turns out that

**Theorem 1.** $\preccurlyeq$ is a **total** preorder, i.e. for any two trees, $\tau$ and $\theta$: $$(\tau \preccurlyeq \theta) \lor (\theta \preccurlyeq \tau).$$

Moreover, $\preccurlyeq$ can be described as the order of ordinals assigned to corresponding
trees.^{6}

**Theorem 2.** For any nonempty set $B$, there is a unique gapless function $\psi \colon \Upsilon _B \to \Omega_B$ such that $$\forall \tau, \theta \in \Upsilon _B\!:\, \tau \preccurlyeq \theta \iff \psi(\tau) \le \psi(\theta).$$Besides that,

- $\psi$ is surjective;
- this function is unique not only in the above context but also in a sense of comparing its values on two isomorphic trees built on subsets of different base sets $B$. In other words, the ordinal number that is assigned to a devil's tree each time depends on this tree only; and of course for any devil's tree $\tau=(A, u, f)$ it is always true that $|\psi(\tau)| \le |A| - 1$.

In particular, this theorem implies that

- $\preccurlyeq$ is
**prewellordering**; - Classes of equivalent (w.r.t. $\preccurlyeq$) devil's trees can be viewed as another representation (or even definition) of ordinal numbers.

## Questions

Regarding the statements written out above, which, if I'm not mistaken, are true in ZFC.

- Is something similar already known (maybe under different names) in modern set theory? The closest thing that I've found so far is Kruskal's tree theorem, but it concerns finite trees only.
- What approach would you use to prove the above statements? Write a proof or a sketch if you wish. There is a chance that I've made a mistake and one or more of the above statements are wrong, so point this out too.

Thanks.

**Remarks**

^{1} The definition of tree used here is just another way to describe a tree commonly used in graph theory. The trees are rooted and directed (anti-arborescence).

^{2} known as Picard sequence,

^{3} Here are some examples to help distinguish these types of trees.

- Any finite (i.e. having finite $A$) tree is a devil's tree.
- Any tree of kind $f(x)=u$ for any $x \ne u$ is devil's tree regardless of the size of $A$. Depending on $A$, it may have infinite (and even uncountable) width at $u$ (not to be confused with treewidth), but its height is 1, so it is limited.
- A tree may even have unlimited height but don't have an infinite branch (in fact, this antilogy was the main motivation for the term
*devil's tree*). So is, for example, any finite tree with all possible finite trees attached (directly) to one of its leaves. Such a tree is also a devil's tree. - The tree with $A=\mathbb N_0,\, u = 0,\, f(n)=n-1 \; \forall n > 0$ and all trees containing such a subtree are divine trees.

^{4} In other words, $h$ is a homomorphism of trees preserving the unary relation "$x$ is the tree's root" and the binary relation $x = f(y)$. Note that there is neither requirement for $h$ to be injective nor requirement to be surjective.

^{5} This, or simply $|B|$ for infinite $B$, corresponds to all possible cardinalities of $A \setminus\!\{u\}$, the set of all non-root vertices of a tree.

^{6} Note that divine trees are of little interest here because any tree can be embedded in any divine tree.

well-foundedtree, for these are the trees whose order relation is well-founded. Every such tree has an ordinal rank, to which you refer. Meanwhile, your divine trees are precisely theill-foundedtrees. $\endgroup$ – Joel David Hamkins May 17 '18 at 22:55