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

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.