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