1
$\begingroup$

Let $T_*$ be a tree on which the parent $e_*$ of the root is added and $x\in\mathbb{V}$ a vertex in the Ulam-Harris tree. Then the tree $T_*^{\leq x}$ is defined as

\begin{cases} \mathsf{T}_*\setminus\{ v\in\mathbb{V}:x<v\}& \text{, falls } x\in\mathsf{T}_*\\ \delta &\text{, falls } x\notin\mathsf{T}_*.\\ \end{cases}

If $x\in\mathbb{V}$, then $T^{\leq x}_*$ is the tree $T_*$ in which all strict descendants of $v$ are removed. Otherwise it is the cemetery tree $\delta$.

What is in this context a cemetery tree? Does it consists only of the root $e$?

arxiv.org/abs/1111.4313 [1] (page 4)

I ask for the definition because of Lemma 2.1 [1] on page 6: I want to check that the distributions of the backward tree $\mathfrak{B}_x(\mathbb{T}_*)$ and $\mathbb{T}_*^{\leq \bar{x}}$ are the same for $x\notin\mathbb{T}_*$.

I thought:

$\mathfrak{B}_x(\mathbb{T}_*)\stackrel{(1)}{=}\Psi_x(\mathbb{T}_*^{\leq x})\stackrel{(2)}{=}\Psi_x(\delta)\stackrel{(3)}{=}\delta$

(1) is the definition of the backward tree

(2) is because in the case $x\notin\mathbb{T}_*$: $\mathbb{T}_*^{\leq x}=\delta$

(3) is the definition of the function $\Psi_x$ in [1]

But then $\delta$ must be $\mathbb{T}_*^{\leq \bar{x}}$ which i do not see.

Do someone see my mistake?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.