4
$\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$ 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$ 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.