5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Commented Nov 9, 2022 at 18:38
  • $\begingroup$ 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. $\endgroup$ Commented Nov 9, 2022 at 19:49

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .