# Is there a standard Borel space of finitely branching real trees?

Given a set $$X$$, by a tree in $$X$$ I mean a set $$T$$ of finite sequences of elements of $$X$$ which is closed under initial segments. It is pruned of every element has a proper extension, and finitely branching if every element has at most finitely many immediate successors.

If $$X$$ is countable, then trees in $$X$$ are subsets of the countable set $$X^{<\infty}$$ of all finite sequences in $$X$$, and thus can be viewed as elements of the space $$2^{X^{<\infty}}$$, which is homeomorphic to the Cantor space $$2^\mathbb{N}$$ and thus Polish. Moreover, in this topology, the set of trees is a Borel subset of $$2^{X^{<\infty}}$$. Alternatively, if we consider only pruned trees, then these can be identified with their sets of infinite branches, which are exactly the closed subsets of the Polish space $$X^\mathbb{N}$$ (where $$X$$ is discrete), and thus inherits a standard Borel structure from the Effros Borel space of closed subsets of $$X^{\mathbb{N}}$$. The finitely branching pruned trees then correspond to the compact subsets of $$X^{\mathbb{N}}$$, and thus can be viewed as a compact Polish space under the Vietoris or Hausdorff topology on the space of compact subsets of $$X^{\mathbb{N}}$$.

My question: If we replace $$X$$ in the above by $$\mathbb{R}$$ (or any other uncountable Polish space), is there a natural standard Borel structure on the set of finitely branching pruned trees in $$\mathbb{R}$$?

My gut instinct is no, and probably one can use something like the fact that there is no nice standard Borel structure on the space of all countable subsets of $$\mathbb{R}$$, but I don't see how at the moment.

• I probably don't really get the question, but it doesn't seem so problematic. For any $X$, we can consider the basic open subsets of $X^{\mathbb N}$ to be determined by finite sequences, so we have a topology and thus a notion of Borel. As you said, the finitely branching trees correspond to compact sets in this topology, right? Nov 9, 2022 at 18:38
• Ah, I meant standard Borel, as in coming from a (separable) Polish topology. The issue is the finitely branching trees correspond to compact subsets of $X^{\mathbb{N}}$ where $X$ is discrete. Nov 9, 2022 at 19:49

A natural way to represent a finitely branching tree over $$\mathbb{R}$$ is to separate the structure of the tree from the content (ie its labels from $$\mathbb{R}$$).

We can describe the structure of the tree by a function $$d : \mathbb{N} \to \mathbb{N}$$, where $$d(n)$$ is the number of children the $$n$$-th vertex in the tree has. We number the children by giving $$0$$ to the root, and always counting through an entire layer of the tree first, before moving on the next layer.

In addition, we have the labelling function $$\ell : \mathbb{N} \to \mathbb{R}$$ telling us which real number the $$n$$-th vertex of the tree carries. There is a condition to impose here, namely that if $$n,n+1,\ldots,n + k$$ are all siblings, then $$\ell(n) < \ell(n+1) < \ldots < \ell(n+k)$$.

This views the space of finitely branching tree as a $$\Pi^0_2$$-subspace of the Polish space $$\mathbb{N}^\mathbb{N} \times \mathbb{R}^\mathbb{N}$$. As such, it is Polish itself. The space of pruned tree is in turn a $$\Pi^0_1$$-subspace, thus again Polish.

If we were to try the same approach for countably-branching trees, the problem would be that defining a canonic order for the siblings becomes far more complex.