(I apologize in advance if a similar question was posted on this site. If it is the case I was unable to find it).
I'm wondering whether one can express any real number in $[0,1]$ as a (possibly infinite) binary tree in the following way.
A tree $t=(N,c)$ is such that
- $N\subseteq \{0,1\}^*\cup\{0,1\}^\omega$ is a set of nodes
- $u\in N\Rightarrow pref(u)\subseteq N$
- $c:N\to \{0,1\}$ is a label function such that $c(u)=0$ if $u$ is not a leaf.
Such tree represent the number $\sum_{u\in N,c(u)=1}1/2^{height(u)}$.
I am almost sure you can reach any real number with such tree but I was unable to prove (or disprove) it. For the rational number I have an easy construction, but I struggle with the reals.
I would appreciate any reference on such matter or any idea on why this is true (or false) and how to prove it. Thanks
EDIT to clarify notations
$u\in\{0,1\}^\omega$ if $u$ is an infinite word on $\{0,1\}$
$pref(u)$ denotes the set of all prefixes of $u$. More formally if $u=u_0..u_n\in\{0,1\}^*$ then $pref(u)=\{u_0..u_k\mid k\leq n\}$ and if $u=u_0u_1..\in\{0,1\}^\omega$ then $pref(u)=\{u_0..u_k\mid k\geq 0\}$
A node $u\in N$ is a leaf if $u\in\{0,1\}^*$ and $u0\notin N$ and $u1\notin N$.
What you are describing is basically equivalent to the binary expansion of real number, so yes you can describe any real between $0$ and $1$ this way. You're just writing real numbers in base 2 instead of the usual base 10.
A few details are important to note though.
First the binary expansion, juste like base 10 expansion, is not unique. For example $0.99999\ldots=1$ in base 10 and with your tree the infinite word $(0;1;1;1;1;1;1;1;\ldots)$ would give you the same real number than $(1;0;0;0;0;0;\ldots)$, a.k.a. $1/2$. This means that some numbers are represented twice on your tree. You could avoid this problem by saying you're only allowing paths that don't end up with an ininterupted sequence of $1$. The binary expansion then becomes unique.
The other important thing is that while you could represend every number with finite binary expansion (also called dyadic numbers) as a node of your tree, the other real numbers are not representable as a node. You will need infinite words for that. The interesting thing to note is that while your infinite tree has a countable number of nodes the number of infinite words you can create is uncountable. This is "not surprising" since the dyadic numbers are countable but $(0;1)$ isn't.
For a more doodling speedtalking point of view about this you can watch this video of Vi Hart : https://www.youtube.com/watch?v=BEz-vGJvaik