3
$\begingroup$

Definitions

The term tree1 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 iterations2 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

  1. $x = u \iff h(x) = v$;
  2. $\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

  1. $\preccurlyeq$ is prewellordering;
  2. 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.

  1. 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.
  2. 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.

$\endgroup$
  • 3
    $\begingroup$ Some users may prefer the standard terminology: what you call a Devil's tree is commonly known as a well-founded tree, 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 the ill-founded trees. $\endgroup$ – Joel David Hamkins May 17 '18 at 22:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.