Is the set of sum over a diagram is uncountable set?

Question

Consider the following diagram:

Let $0<x<\frac{1}{2}$

Note that $[.]$ is not box function

It is easy to see that $1$ split into $x$ and $(1-x)$. In next stage $x$ split into $x^2$ and $x(1-x)$ and $(1-x)$ split into $x(1-x)$ and $(1-x)^2$. Note that I do not write $x(1-x)$ twice, instead of that in this stage we have three values $x^2,x(1-x),(1-x)^2$. Continue this process in the next stage (see the diagram for more detail)

Now comes the important part:

Add take $1$ first. Then add either $x$ or $(1-x)$. If you added $x$ then next add either $x^2$ or $x(1-x)$ and if you added $(1-x)$ then up next add either $x(1-x)$ or $x^2$. Continue this process again.

For example you will get a value $1+\sum_{n=1}^{\infty}x^n$. Another one could be $1+\sum_{n=1}^{\infty}x(1-x)^{n-1}$. It depends on which path you choose. Every zigzag path will give you a $\color{red}{\text{different sums}}$.

$\color{red}{\text{different sums}}$ means sum over different zigzag path. Note that $\color{red}{\text{different sums}}$ does not mean two different path always give different values.

$\large{F}$or example $1+(1-x)\sum_{n=0}^{\infty}x^n$ and $1+x\sum_{n=0}^{\infty}(1-x)^n$ are two $\color{red}{\text{different sums}}$ but they yeilds same value $2$ i.e. $1+(1-x)\sum_{n=0}^{\infty}x^n=1+x\sum_{n=0}^{\infty}(1-x)^n=2$

Let say $T_x=\{\text{set of all $\color{red}{\text{different sums}}$ for a given $x$ }\}$

It can be easily seen there is uncountable number of $\color{red}{\text{different sums}}$.

Question: is there uncountable number of distinct elements in $T_x$ for a given $x$?

Observation:

1. It can be easily seen that minimum element of $T_x$ is $\frac{1}{1-x}$ and maximum element of $T_x$ is $\frac{1}{x}$.

2. $2\in T_x$ for every $x\in \Big(0,\frac{1}{2}\Big)$

But I could not find a way to prove or disprove uncountability. Any help would be appreciable.

$\blacksquare\space\space\blacksquare\space\space\blacksquare\space\space$ Thanks to MANMAID I am attaching a new diagram:

Let $0<x<1$

Answer 1

Formalization

• For $n \in \mathbb{N}$ let $\{ 0, 1 \}^n$ denote the set of $n$-element binary sequences, i.e. the set of functions $f : \{ 0, 1, \ldots, n-1 \} \to \{ 0, 1 \}$.
• Let $\{ 0, 1 \}^{\mathbb{N}}$ denote the set of infinite binary sequences, i.e. the set of functions $s : \mathbb{N} \to \{ 0, 1 \}$.
• For $s \in \{ 0, 1 \}^{\mathbb{N}}$ and $n \in \mathbb{N}$ (or $s \in \{ 0, 1 \}^m$ and $n \leqslant m$ respectively) by $s \upharpoonright n$ we denote the preffix of $s$ of length $n$, i.e. the restriction $s \upharpoonright \{ 0, 1, \ldots, n-1 \}$.
• For $f \in \{ 0, 1 \}^n$ let $\alpha(f) = \# \{ k < n : f(k) = 0 \}$ and $\beta(s) = \# \{ k < n : f(k) = 1 \}$ (the number of zeros and ones in $f$ respectively).

Note that any path in the diagram can be represented by an infinite binary sequence, so we may think of $\{ 0, 1 \}^{\mathbb{N}}$ as the set of all possible paths.

Fix $x \in \left( 0, \frac{1}{2} \right)$ and define $\varphi : \{ 0, 1 \}^{\mathbb{N}} \to \mathbb{R}$ as

$$\varphi(s) = \sum_{n=0}^{\infty} x^{\alpha(s \upharpoonright n)} \cdot (1-x)^{\beta(s \upharpoonright n)}.$$

Thus $\varphi(s)$ clearly represents the sum associated with the path $s$. So the question is: is $\varphi \left[ \{ 0, 1 \}^{\mathbb{N}} \right]$ uncountable?

Solution

On $\{ 0, 1 \}^{\mathbb{N}}$ there is a natural lexicographical order, given by $$s \prec t \iff (\exists n \in \mathbb{N}) \big[ s \upharpoonright n = t \upharpoonright n \wedge s(n) < t(n) \big].$$

In words: if $s, t$ are different, find the first position $n \in \mathbb{N}$ on which they differ, so $s(n) \neq t(n)$ and compare them by the value on that position. On your diagram, any two different paths diverge at some point and the one going to the left will be smaller with respect to this ordering.

The key observation is: let $s \prec t$. Then $\varphi(s) \leqslant \varphi(t)$ and $\varphi(s) = \varphi(t)$ if and only if there is $n \in \mathbb{N}$ such that $s$ and $t$ agree up to $n$ and then $s$ continues as $0, 1, 1, 1, \ldots$ and $t$ continues as $1, 0, 0, 0, \ldots$

Proof.

From the definition of $s \prec t$ we have $n$ such that $s$ and $t$ agree up to $n$ (exclusively) and then $0 = s(n) < t(n) = 1$. Let $s^*$ be an infinite sequence defined as $s \upharpoonright n$ followed by $0, 1, 1, 1, \ldots$ Similarly, let $t_*$ start with $t \upharpoonright n$ and continue as $1, 0, 0, 0, \ldots$

Note that for each $k \in \mathbb{N}$ we have $\beta( s \upharpoonright k) \leqslant \beta( s^* \upharpoonright k )$ since $s$ and $s^*$ agree up to $n+1$and then $s^*$ becomes constantly $1$. Therefore $\varphi(s) \leqslant \varphi(s^*)$ since multiplying things by $1-x$ makes them greater than multiplying by $x$. Similarly we prove that $\varphi(t_*) \leqslant \varphi(t)$.

It's also easy to see that if $u, v$ are infinite binary sequences and $f \in \{ 0, 1 \}^m$ is a finite binary sequence such that $u = f \frown v$ (where $\frown$ denotes contatenation), then

• if $k < m$, then $\alpha( u \upharpoonright k ) = \alpha( f \upharpoonright k )$ and $\beta( u \upharpoonright k ) = \beta( f \upharpoonright k ),$
• for $k \geqslant 0$: $\alpha( u \upharpoonright (m+k) ) = \alpha( f ) + \alpha( v \upharpoonright k )$ and $\beta( u \upharpoonright (m+k) ) = \beta( f ) + \beta( v \upharpoonright k ).$

Hence

$$\varphi(u) = \sum_{k=0}^{m-1} x^{\alpha(f \upharpoonright k)} (1-x)^{\beta(f \upharpoonright k)} + x^{\alpha(f)} (1-x)^{\beta(f)} \cdot \varphi(v).$$

Taking $f$ to be the common preffix of $s$ and $t$, i.e. $f = s \upharpoonright n = t \upharpoonright n$, we obtain

$$\varphi(s^*) = \sum_{k=0}^{m-1} x^{\alpha(f \upharpoonright k)} (1-x)^{\beta(f \upharpoonright k)} + x^{\alpha(f)} (1-x)^{\beta(f)} \cdot \varphi(0, 1, 1, 1, \ldots) \\[1ex] \varphi(t_*) = \sum_{k=0}^{m-1} x^{\alpha(f \upharpoonright k)} (1-x)^{\beta(f \upharpoonright k)} + x^{\alpha(f)} (1-x)^{\beta(f)} \cdot \varphi(1, 0, 0, 0, \ldots).$$

Computing $\varphi(0, 1, 1, 1, \ldots) = 2 = \varphi(1, 0, 0, 0, \ldots)$ yields $\varphi(s^*) = \varphi(t_*)$, so $\varphi(s) \leqslant \varphi(t)$.

Now if $\varphi(s) = \varphi(t)$, then $\varphi(s) = \varphi(s^*)$ and $\varphi(t_*) = \varphi(t)$, which clearly implies $s = s^*$ and $t = t_*$, so the claim has been proved.

Now let $A \subseteq \{ 0, 1 \}^{\mathbb{N}}$ be the set of all infinite binary sequences eventually stabilizing at $1$. From the above fact, the restriction of $\varphi$ to $\{ 0, 1 \}^{\mathbb{N}} \setminus A$ is strictly increasing, hence injective. But $A$ is countable, so $|\{ 0, 1 \}^{\mathbb{N}} \setminus A| = \mathfrak{c}$, thus $\varphi \left[ \{ 0, 1 \}^{\mathbb{N}} \right]$ has cardinality $\mathfrak{c}$ so in particular is uncountable.

Further insight

In this section I will provide less details and concentrate on how it is rather than why it is true. Hopefully you can fill the gaps if you're interested.

The set $\{ 0, 1 \}^{\mathbb{N}}$ can be regarded as a metric space known as the Cantor set with the metric defined as

$$d( s, t ) = \begin{cases} 0 & \text{if } s = t \\ 2^{-\min \{ n : s(n) \neq t(n) \}} & \text{otherwise} \end{cases}$$

It's not hard to see that the map $\varphi$ is continuous, because if $s, t$ agree up to $n$, i.e. $s = f \frown u$ and $t = f \frown v$ for some $f \in \{ 0, 1 \}^n$ and $u, v$ infinite, then

$$|\varphi(s) - \varphi(t)| = x^{\alpha(f)} (1-x)^{\beta(f)} \cdot |\varphi(u) - \varphi(v)| \leqslant (1-x)^n \cdot \left[ \frac{1}{x} - \frac{1}{1-x} \right]$$

so the difference can be made arbitrarily small by making $n$ large. Now the fact proven above implies that $\varphi = \psi \circ p$ for some continuous $\psi : [0, 1] \to \mathbb{R}$, where $p : \{ 0, 1 \}^{\mathbb{N}} \to [0, 1]$ is the standard continuous surjection

$$p(s) = \sum_{n=0}^{\infty} \frac{s(n)}{2^{n+1}}.$$

Since $\psi$ is continuous, from the Darboux property it is onto $\left[ \frac{1}{1-x}, \frac{1}{x} \right]$, thus so is $\varphi$. So every number $y \in \left[ \frac{1}{1-x}, \frac{1}{x} \right]$ can be obtained as a sum over a path $s \in \{ 0, 1 \}^{\mathbb{N}}$ which is unique up to the case described by the fact we have proven.

Answer 2

The more usual way to draw this is as a binary tree, so the downward paths do not come to the same vertex. Then you have one vertex at the root, two at the next level, four at the next, and $2^n$ at level $n$. As you traverse the tree you add a bit to the binary number that is the sum, $0$ if you take the left fork and $1$ if you take the right. Then it is clear that you can have any number in $[0,1]$ as the sum, so there are an uncountable number of possible sums. There are only countably many vertices in the tree, whether it is $1+2+3+4+\ldots$ or $1+2+4+8+\ldots$