About the rank of a tree

75 Views Asked by At

I've found three different definitions of rank for a well-founded tree and I have some questions about it.

First of all, these are the definitions:

Definition 1: Let $T$ be a well-founded tree on $\omega$. We define the derivative of $T$ as the well-founded tree $$T'=\left\{s \in T: \exists t \in T \text{ such that } s < t\right\}$$ Then by transfinite recursion we define

$$ \begin{align} T^0 & = T\\ T^{\alpha+1} & = \left(T^\alpha\right)'\\ T^{\alpha} & = \bigcap_{\beta < \alpha} T^\beta \text{ if } \beta \text{ is a limit ordinal} \end{align} $$ Then, the rank of $T$ is defined as $$o(T)=\min\{\alpha \in \Omega: T^\alpha = \emptyset\}$$

Definition 2: Let $T$ be a well-founded tree on $\omega$. For every $n \in \omega$ we define $$ T_n= \{s \in \omega^{<\omega}: n \frown s \in T\} $$ It is clear that if $T_n \not = \emptyset$ then it is a well-founded tree.

Then, the rank of $T$ is defined recursively as the function $r: WF \rightarrow \Omega$ given by $$ r(T)= \sup\left\{r(T_n)+1: n \in \omega \text{ such that } T_n \not = \emptyset \right\} $$

Definition 3: Let $T$ be a well-founded tree on $\omega$. We define recursively the function $\rho_T: T \rightarrow \Omega$ as the unique function satisfying $$ \rho_T(s)=\sup\{\rho_T(t)+1: t \in T \wedge s<t\} $$ Then, the rank of $T$ is defined as $$ \rho(T)=\rho_T(\emptyset) $$

Given the definitions I have two questions:

Question 1: Why is it true that for any well-founded tree there exits an ordinal $\alpha < \omega_1$ sucht that $T^\alpha = \emptyset$?

Question 2: Why is Definition 2 correct? I mean, what results on recursive definitions can give you the existence and uniquenes of the function $r$?

Question 3: Which is the relation between all this definitions? I think I've managed to prove that $o(T)=r(T)+1$ but I'm not completely sure. And, for the relation with $\rho$ I think that it is equal to $r$, but I'm not able to fully prove it.

1

There are 1 best solutions below

0
On BEST ANSWER

For a set $\Lambda$, I let $$\Lambda^{<\omega}=\bigcup_{n=0}^\infty \Lambda^n=\bigcup_{n=0}^\infty \prod_{i=1}^n \Lambda,$$ which is the set of all finite sequences (including the empty sequence) whose terms lie in $\Lambda$.

Based on your question, I'm going to make the following assumptions:

Your definition of tree requires that it's non-empty. Not everyone obeys this convention, but it doesn't make any important difference.

Your definition of "well-founded" is that there doesn't exist any sequence $(m_n)_{n=1}^\infty$ such that $(m_n)_{n=1}^p\in T$ for all $p$. Let $s\leqslant t$ denote the relation that $s$ is an initial segment of $t$, and $s<t$ denotes that $s$ is a proper initial segment of $t$. The definition of well-founded that I gave above is equivalent to each of the following.

  1. There does not exist any infinite, strictly ascending $<$-chain in $T$.
  2. Every non-empty subset of $T$ has a $<$-maximal element.
  3. Every subtree of $S$ has a $<$-maximal element.
  4. For every ordinal $\alpha$, either $T^\alpha=\varnothing$ or $T^{\alpha+1}\subsetneq T^\alpha$.
  5. There exists an ordinal $\alpha$ such that $T^\alpha=\varnothing$.
  6. The inverse relation $\geqslant$ is a well-founded relation on $T$.

I think it's instructive to check that these are equivalent, so I won't go into detail on these unless requested.

I'll define $\text{rank}(T)$ to be the minimum $\alpha$ such that $T^\alpha=\varnothing$. Such an ordinal exists if $T$ is well-founded by the equivalences mentioned above. You denote this by $o(T)$, which I did as well. But I found that the authors from whom I took this notation sometimes referred to it as the "order" of the tree rather than the "rank", and there is a very common use of the term "order" of a tree which is very different than the rank. So I moved away from the notation $o(T)$.

Question $1$: This question is either asking why there exists an ordinal $\alpha$ such that $T^\alpha=\varnothing$, or why must there exist a countable ordinal with this property.

We can define $\varnothing^\alpha=\varnothing$ for all $\alpha$, which is a convention that we must establish to get around the fact that our definition of tree requires non-emptiness. We note that for all $\alpha$, $T^\alpha$ is either empty or also a tree.

To address the first part, note that for any tree (well-founded or ill-founded), if there exists an ordinal $\beta$ such that $T^{\beta+1}=T^\beta$, then $T^\gamma=T^\beta$ for all $\gamma\geqslant \beta$. The equality $T^{\beta+1}=T^\beta$ means that $T^\beta$ has no maximal elements (with respect to the initial segment ordering). If $T^{\beta+1}=T^\beta$, then it's an easy induction to show that $T^{\beta+\gamma}=T^\beta$ for all $\gamma$, which implies that $T^\gamma=T^\beta$ for all $\gamma\geqslant \beta$. The $\gamma=0$ case is a tautology, the $\gamma=1$ case is by hypothesis, the limit ordinal case follows by taking intersections. If $T^{\beta+\gamma}=T^\beta=T^{\beta+1}$, then $$T^{\beta+\gamma+1}=(T^{\beta+\gamma})'=(T^\beta)'=T^{\beta+1}=T^\beta.$$

Therefore if $T^{\alpha+1}=T^\alpha$, then $T^\beta$ stays constant for $\beta\geqslant \alpha$. In this case we say that $T$ stabilizes by $\alpha$. That means that by the time we've reached $\alpha$, $T^\alpha$ has stabilized at some constant value. If $\alpha$ is the minimm ordinal such that $T^{\alpha+1}=T^\alpha$, we say that $T$ stabilizes at $\alpha$. We say that $T$ stabilizes if it stabilizes at some $\alpha$.

We note that every tree on $\omega$ must stabilize at some $\alpha<\omega_1$. This is because, since $T^{\alpha+1}\subset T^\alpha$ for all $\alpha$, if $T^\alpha$ did not stabilize at any $\alpha<\omega_1$, it would be the case that $T^\alpha\setminus T^{\alpha+1}\neq \varnothing$ for all $\alpha<\omega_1$. For each $\alpha<\omega_1$, choose $f(\alpha)\in T^\alpha\setminus T^{\alpha+1}$. Then $f:\omega_1\to \omega^{<\omega}$ is an injection (the sets $T^\alpha\setminus T^{\alpha+1}$ are disjoint), but this is an injection from an uncountable set into a countable set. This is a contradiction.

Therefore each tree on $\omega$, well-founded or not, stabilizes at a countable ordinal. We note that $T$ is well-founded iff when it stabilizes, it stabilizes at the empty set. These should answer your first question.

In general, for a tree on a non-empty set $\Lambda$, if $\kappa$ is the minimum ordinal exceeding $|\Lambda^{<\omega}|=\max\{\omega,|\Lambda|\}$, then any tree on $\Lambda$ must stabilize at a value less than $\kappa$, and $T$ is well-founded iff it stabilizes at the empty set.

For the second question, let's define the following: For a tree $T$ on a set $\Lambda$ and $t\in \Lambda^{<\omega}$, let $$T[t]=\{s\in \Lambda^{<\omega}:t\smallfrown s\in T\}.$$ Here, $s\smallfrown t$ denotes concatenation. For convenience, we have made this definition even if $t$ is not a member of $T$. But we note that $T[t]$ is a tree iff it's non-empty iff it contains $\varnothing$ iff $t=t\smallfrown \varnothing\in T$. Your sets $T_n$ are the sets $T[(n)]$ in my notation.

Note that $T[t]^\alpha=T^\alpha[t]$ for any tree $T$ on $\Lambda^{<\omega}$, $t\in \Lambda^{<\omega}$, and any ordinal $\alpha$. Our conventions have been established in such a way that this remains true even if the sets are empty/$T[t]$ is not a tree, etc.

By our definition of tree, a tree is non-empty and downward closed, so every tree contains $\varnothing$. Therefore $\text{rank}(T)\neq 0$, because $T^0=T$ is not empty. Also, it's not possible that $\text{rank}(T)$ is a limit ordinal. This is because if $\alpha$ is a limit ordinal and $T^\beta\neq \varnothing$ for all $\beta<\alpha$, then $\varnothing\in \bigcap_{\beta<\alpha}T^\beta=T^\alpha$, and $T^\alpha\neq \varnothing$. If this looks like the finite intersection property in a compact space, that's not too much of a coincidence, because well-founded trees (with unique roots) are compact in the coarse wedge topology. If you go searching for more details on that, I think you'll be likely to run into people who have very different definitions of trees, and those we've defined here are only a special case of those.

Anyway, we now know that a well-founded tree must have $\text{rank}(T)$ equal to a successor ordinal, say $\text{rank}(T)=\alpha+1$. In this case, $\alpha$ is the maximum ordinal for which $T^\alpha\neq \varnothing$, and since each $T^\beta$ is either empty or contains $\varnothing$, $\alpha=\max\{\beta:\varnothing\in T^\beta\}$.

I've said this to bridge the between the first of your definitions and the second two (which are equivalent to each other). Your $o(T)$ is my $\text{rank}(T)$. Your $\rho_T$, which is defined on all of $T$, satisfies the following: $$\rho_T(s)=\max\{\beta:s\in T^\beta\}.$$ When we recall that $\rho(T)=\rho_T(\varnothing)$, this exactly captures the relationship that you mentioned: $$o(T)=\rho(T)+1.$$ That is, $\rho(T)=\rho_T(\varnothing)=\alpha$ iff $\alpha$ is the maximum $\beta$ such that $\varnothing\in T^\beta$ iff $\alpha+1$ is the minimum $\beta$ such that $T^\beta=\varnothing$ iff $\text{rank}(T)=o(T)=\alpha+1$.

The claim on $\rho_T(s)$ seems more general that the claim on $\rho_T(\varnothing)$. That is, it appears stronger to say that $$\rho_T(s)=\max\{\alpha:s\in T^\alpha\}$$ for all $s\in T$ rather than simply for $s=\varnothing$. However, Since $T[s]^\alpha=T^\alpha[s]$, we deduce that $T^\alpha[s]\neq \varnothing$ iff $\varnothing\in T^\alpha$ (by properties of trees) iff $s\in T^\alpha$ (by definition of $T^\alpha[s]$). Since $T^\alpha[s]=T[s]^\alpha$ (which we stated but didn't prove), each of these conditions is equivalent to the condition that $T[s]^\alpha\neq \varnothing$, which is equivalent to the condition that $\text{rank}(T[s])>\alpha$. And if, as I've claimed, $\rho(T[s])+1=\text{rank}(T[s])$, then $\text{rank}(T[s])>\alpha$ is equivalent to $\rho(T[s])\geqslant \alpha$. But it's almost a tautology that $\rho(T[s])=\rho_T(s)$.

If we wanted to prove that $\rho_T(s)=\max\{\alpha:s\in T^\alpha\}$, we could show by induction for $\alpha\in \text{rank}(T)$ that $\rho_T(s)=\alpha$ for all $s\in T^\alpha\setminus T^{\alpha+1}$. We only need to worry about $\alpha\in \text{rank}(T)=[0,\text{rank}(T))$ because $T^{\text{rank}(T)}=\varnothing$. By our discussion above, we know that for each $\alpha \in \text{rank}(T)$, $T^\alpha\setminus T^{\alpha+1}$ is non-empty.

For the proof, we note that $s\in T^\alpha\setminus T^{\alpha+1}$ iff $s$ is a leaf in $T^\alpha$. The base case is essentially just this observation: $\rho_T(s)=0$ iff $s$ is a leaf in $T$ iff $s\in T^0\setminus T^1$.

Next suppose that $0<\alpha<\text{rank}(T)$ and the result holds for all $\beta<\alpha$. Then $s\in T^\alpha\setminus T^{\alpha+1}$ iff $s$ is a leaf in $T^\alpha$ iff $s\in T^\alpha$ and for all $s<t\in T$, $t\notin T^\alpha$. The first of these two conditions, $s\in T^\alpha$, is equivalent to the condition that for each $\beta<\alpha$, $s$ is not a leaf in $T^\beta$, which is equivalent to the condition that for each $\beta<\alpha$, there exists $s<t\in T^\beta$, which is equivalent to the condition that for each $\beta<\alpha$, there exists $s\in t\in T$ with $\rho_T(t)\geqslant \beta$. The second condition, that for each $s<t\in T$, $t\notin T^\alpha$, is equivalent to the condition that for each $s<t\in T$, $\rho_T(s)<\alpha$. So $s\in T^\alpha\setminus T^{\alpha+1}$ iff $s$ is a leaf in $T$ iff for every $\beta<\alpha$, there exists $s<t\in T$ with $\rho_T(t)\geqslant \beta$, but for every $s<t\in T$, $\rho_T(t)<\alpha$. These last two conditions yield that $$\alpha=\sup\{\rho_T(t)+1:s<t\in T\}=\rho_T(s).$$ This completes the inductive proof.

Now that we know that $\rho(T)=\rho_T(\varnothing)=\max\{\alpha:\varnothing\in T^\alpha\}$, $\text{rank}(T)=\rho(T)+1$ immediately follows.

How does this connect to $r$? Assuming there exists a unique function $r$ satisfying the recursive definition (which was a separate question of yours), we note that $\rho(T)$ satisfies it. We can prove by induction on $\alpha$ that if $\rho(T)\leqslant \alpha$, then $r(T)=\rho(T)$. The base case is $T=\{\varnothing\}$, which is clear, since each is the supremum over the empty set.

For the inductive step, the key observation is the following: We know that $$\rho_T(\varnothing)=\sup\{\rho_T(t)+1:\varnothing<t\in T\}.$$ Since we're not in the base case, this set must be non-empty. However, for any $\varnothing<t\in T$, there exists $n\in \omega$ such that $\varnothing<(n)\leqslant t$, and $\rho_T((n))\geqslant \rho_T(t)$. Therefore the supremum in the definition of $\rho_T(\varnothing)$ is attained among the nodes of the form $t=(n)$. In other words, $$\rho_T(\varnothing)=\sup\{\rho_T((n))+1:(n)\in T\}.$$ By the inductive hypothesis and our work in the preceding paragraph, $\rho_T((n))=r(T_n)$, and $$\sup\{\rho_T((n))+1:(n)\in T\}=\sup\{r(T_n):(n)\in T\}=r(T).$$

Here, it's worth saying a word on why $\rho_T((n))=r(T_n)$. This is because $\rho_T((n))$ is the maximum ordinal $\alpha$ such that $(n)\in T^\alpha$, which is the maximum ordinal such that $\varnothing\in T[(n)]^\alpha$, which is the maximum ordinal such that $T[(n)]=T_n$ is non-empty, which is (by our work above) $\rho (T_n)$, and is equal to, by the inductive hypothesis, $r(T_n)$.