Hello everybody,
I would like to say, before stating the question, that I'm not a mathematician, and therefore i apologize in advance if the question is trivial, or well-known. I'll try to state it as precisely as I can.
Let us define a well founded countably branching tree, as a set
$T\subset {\mathbb{N}}^{*}$, i.e. a subset of finite sequences of naturals,
such that
- $T$ is prefix-closed: if $\vec{n}.m\in T$ then $\vec{n}\in T$, where $\vec{n}\in {\mathbb{N}}^{*}$
- Writing $\vec{n}< \vec{m}$ for $\vec{n}$ is a prefix of $\vec{m}$, there are no infinite ${<}$-increasing sequences.
So more informally $T$ is a tree whose nodes are labeled by naturals, each node can have at finitely or at most $\omega$ children, and there are no infinite branches.
Let me also define a well founded finite branching tree as above, but with the constraint that each node can have at most finitely many children.
Now let us fix an ordinal $\alpha$. We say that $(T,F)$ is a $\alpha$-labeled tree, if
- $T$ is a countably branching w.f. tree, and
- $F: T \rightarrow \alpha$
In other words, $F$ labels the nodes of $T$ with ordinals $\beta<\alpha$.
For the sake of simplicity let us consider from now on $\omega$-labeled trees, but my question extends to the general case.
Now I would like to define a well-ordering on the set of $\omega$-labeled trees.
Here I'll be a bit informal, because I don't know how to state exactly my intuition, but the ordering should be something like the lexicographical ordering.
So when judging if a tree $T$ (with root labeled with $n$, say) is smaller than $U$ (with root labeled also with $n$, say) I would just check if the leftmost branch is – recursively – smaller, if not, i'll move to the second leftmost branch etc.
I'm not sure exactly how to judge coherently two trees having different labels for the root, but of course the trivial tree with just root=leaf labeled with $5$ should be smaller than the some tree where the root is labeled with $6$.
QUESTION:
Let say that we define somehow this ordering, by defining recursively a map $o: \mathcal{T}\rightarrow \gamma$, where $\mathcal{T}$ denotes the set of countably branching $\omega$-labeled trees and $\gamma$ is some ordinal.
What is the smallest ordinal $\gamma$ such that a well ordering $o$ of $\mathcal{T}$ exists? I know that $\gamma\leq\omega_{1}$.
However it is perhaps the case that $\gamma<\omega_{1}$.
In particular if we consider $\omega$-labeled finite branching w.f. trees, I know that $\gamma$ would be $\epsilon_{0}$, defined as here.
So I wonder if the least $\gamma$ that can well order countably branching $\omega$-labeled trees, is something smaller than $\omega_{1}$, perhaps $\epsilon_{1}$, or something.
As I said, the question generalizes to "what is the least ordinal sufficient for well ordering $\alpha$-labeled countably branching well founded trees?
SIDE QUESTION:
Can you suggest an easy reading about $\epsilon_{0}$, $\epsilon_{0}$-induction and in general the usefulness of $\epsilon$ numbers? By easy I mean accessible to a non expert.
Thank you in advance for any answer,
bye
Matteo
Best Answer
I have several observations:
There is a very commonly used ranking function for well-founded trees, defined so that the rank $\rho(x)$ of a node $x$ in the tree is the supremum of $\rho(y)+1$ for all children $y$ of $x$. This is well-defined exactly because the tree order is well-founded. The rank of the tree itself is $\rho(\langle\rangle)+1$, where $\langle\rangle$ is the root node (the empty string).
This ranking function has the property that whenever $y$ is a descendent of $x$, then $\rho(y)\lt\rho(x)$. That is, the ranking respects the tree order. This is somewhat different than your weaker notion of labeling.
In particular, the tree $T_s$ of all strings $t$ such that $st\in T$, which can be thought of as the part of $T$ below node $s$, has a strictly lower rank than $T$, if $s$ is nontrivial.
The rankings of well-founded countable trees is always a countable ordinal, but it is not bounded by $\epsilon_0$ or indeed, by any countable ordinal. The reason is that if we have a tree of rank $\alpha$, we can build a tree of rank $\alpha+1$ simply by adding a new root (which corresponds to prepending a symbol to every string in the tree); and if we have trees $T_n$ of rank $\alpha_n$, then we can make a tree of rank larger than $\sup_n\alpha_n$ by making a tree $T$ with a root node, having children nodes, whose subsequent descendents make a copy of $T_n$. Thus, by induction, the countable trees have ranks unbounded in the countable ordinals.
Every well-founded finitely branching tree is actually finite. This is an immediate consequence of Konig's lemma, since every infinite finitely branching tree has an infinite branch, and so cannot be well-founded. The ordinal $\epsilon_0$ arises with such trees, when $\omega$-labeled, by thinking of them as representing countable ordinals according to the Cantor normal form (for example, as used in Goodstein's theorem).
You didn't specify your intuitive order on trees precisely, but I believe that the natural interpretations of it (on the countably branching trees) will not be a well-order, as you desired. First, one common understanding of the lexical order has longer strings being lower in the order, and so we easily get descending sequences that way. Apart from this, consider the trees $T_n$ consisting of the initial segments of the string $000\cdots1$, with $n$ many $0$s. The left-most branches of these trees are exactly those terminal strings, and these are descending in the lexical order. So this is probably not what you want. Perhaps you might explain your intuitive idea a bit more fully? (In particular, why do you expect a well-order?)
You ask about the least ordinal sufficient for well-ordering a given set. If you don't insist that the order respect any structure (which on my reading of your question you don't), then the answer is simply the cardinality of the set. For example, since there are continuum many well-founded $\omega$-labeled trees, the smallest well-ordering of them has order type $\beth_1$. Since there are only countably many finitely branching well-founded trees, the smallest ordering of these has order type $\omega$.
Finally, perhaps the best answer to your question is to point you towards the Kleene-Brouwer ordering on trees. If $T$ is a tree of finite sequences of ordinals, then $s\lt_{KB} t$ if and only if either $t\subset s$ or for the least $i$ such that $s(i)\neq t(i)$, we have $s(i)\lt t(i)$. This turns the tree order into a linear order, using the idea of lexical order, and any well-founded tree order turns into a well-order under the Kleene-Brouwer ordering. One can now compare trees by their Kleene-Brouwer order-types, and this might be the order which you are seeking.