Equivalent definitions for trees (as partial orders)

Question

Definition. A tree is a partial order $(T,\le)$ which has a least element, and is such that for every $x\in T$, the set $$ \downarrow(x):=\{y\in T\mid y\le x\}$$ is well-ordered by the relation $\le$. Finite trees are finite posets $T$ with least element, such that each $\downarrow(x)$ is linearly ordered.

a) Show that a finite tree is the same thing as a finite sequence of nonempty finite sets and functions $$A_n\to\dots\to A_1 \to A_0$$ where $A_0$ is a one-element set.

b) Show that a finite tree is the same thing as a finite set $V$ together with a function $f:V\to V$ which has the properties that $f$ has exactly one fixed point $r=f(r)$, and there are no elements $x\ne r$ such that $x=f^n(x)$ for some $n\in \mathbb{N}_{>0}$.

My attempt:

a) Let $r$ be the least element of the (finite) poset $T$, and let $A_0:=\{r\}$. For each $x\in T$ define $f(x) = \,\,\downarrow(x)\backslash\{x\}$. Set $A_n=T$. Then set $A_{n-1} = \bigcup_{x\in A_n} f(x), \forall n\ge 1$. Essentially, in each step, we remove the 'highest layer' of $T$. Eventually, we'll reach $r$. Is this alright? The exercise seems to suggest that I need to find several functions.

b) Consider a finite tree $T$ with least element $r$. Let $V=T$ as a set. Then $\forall x\in V\backslash\{r\}: \exists y_x\in \,\,\downarrow(x)\backslash\{x\}$. Define $f(x)=y_x$ if $x\ne r$, and $f(r)=r$. Then $f^n(x)\ne x\forall n$ because $x> f(x)> f^2(x)> \dots > r$, per definition of $f$.

Is this alright?

Thanks.

Answer 1

When you have to prove that two structures are equivalent, you usually show that you can translate the first structure to the second, that you can translate the second structure to the first, and that translating a structure forwards and backwards yields (something isomorphic to) the original structure.

For example in a) you need to answer the following four questions:

• if you are given a finite tree $(T,\leq)$, what would the corresponding sequence $A_n\overset{f_n}\to\cdots\overset{f_2}\to A_1\overset{f_1}\to A_0$ be?
• if you are given a sequence of functions $A_n\overset{f_n}\to\cdots\overset{f_2}\to A_1\overset{f_1}\to A_0$, what would the corresponding finite tree $(T,\leq)$ look like?
• if you take a finite tree $(T,\leq)$, translate it to a sequence $A_n\overset{f_n}\to\cdots\overset{f_2}\to A_1\overset{f_1}\to A_0$ and translate that back to a finite tree $(S,\preceq)$, then are $(T,\leq)$ and $(S,\preceq)$ isomorphic trees?
• if you take a sequence $A_n\overset{f_n}\to\cdots\overset{f_2}\to A_1\overset{f_1}\to A_0$, translate it to a finite tree $(T,\leq)$ and translate that back to a sequence $B_m\overset{g_m}\to\cdots\overset{g_2}\to B_1\overset{g_1}\to B_0$, then are the two sequences isomorphic? That is, $n=m$ and there exist bijections $h_k:A_k\to B_k$ for each $0\leq k\leq n$ such that if $k\geq 1$ and $x\in A_k$ then $g_k(h_k(x))=h_{k-1}(f_k(x))$. In other words the following diagram should commute:

$$\require{AMScd} \begin{CD} A_n @>{f_n}>> A_{n-1} @>{f_{n-1}}>> \cdots @>{f_2}>> A_1 @>{f_1}>> A_0\\ @V{h_n}VV @V{h_{n-1}}VV @. @V{h_{1}}VV @V{h_{0}}VV\\ B_n @>{g_n}>> B_{n-1} @>{g_{n-1}}>> \cdots @>{g_2}>> B_1 @>{g_1}>> B_0 \end{CD} $$

---

As a hint for a): try building your trees from the root upwards, instead of from the top downwards. Don't remove the highest layer, but consider the lowest layer that hasn't been added yet. As an additional hint, it might be easier if you try to make each of the $A_k$ disjoint from each other.

As a hint for b): you should not choose $y_x$ to be any arbitrary element. There is exactly one element $y_x$ that should be the correct choice, since any other choice will not survive translating back and forth; you would lose information in the translation.