¿El conjunto de la suma sobre un diagrama es un conjunto incontable?

Question

Considere el siguiente diagrama:

Dejemos que $0<x<\frac{1}{2}$

Tenga en cuenta que $[.]$ no es una función de caja

Es fácil ver que $1$ dividido en $x$ y $(1-x)$ . En la siguiente etapa $x$ dividido en $x^2$ y $x(1-x)$ y $(1-x)$ dividido en $x(1-x)$ y $(1-x)^2$ . Tenga en cuenta que no escribo $x(1-x)$ dos veces, en lugar de eso en esta etapa tenemos tres valores $x^2,x(1-x),(1-x)^2$ . Continúe este proceso en la siguiente etapa (vea el diagrama para más detalles)

Ahora viene la parte importante:

Añadir toma $1$ primero. A continuación, añada $x$ o $(1-x)$ . Si se añade $x$ a continuación, añada $x^2$ o $x(1-x)$ y si se añade $(1-x)$ y a continuación añada $x(1-x)$ o $x^2$ . Continúe este proceso de nuevo.

Por ejemplo, obtendrá un valor $1+\sum_{n=1}^{\infty}x^n$ . Otro podría ser $1+\sum_{n=1}^{\infty}x(1-x)^{n-1}$ . Depende del camino que elijas. Cada zigzag le dará un $\color{red}{\text{different sums}}$ .

$\color{red}{\text{different sums}}$ significa la suma de diferentes zigzag camino. Tenga en cuenta que $\color{red}{\text{different sums}}$ no significa que dos caminos diferentes den siempre valores diferentes.

$\large{F}$ o ejemplo $1+(1-x)\sum_{n=0}^{\infty}x^n$ y $1+x\sum_{n=0}^{\infty}(1-x)^n$ son dos $\color{red}{\text{different sums}}$ pero tienen el mismo valor $2$ es decir $1+(1-x)\sum_{n=0}^{\infty}x^n=1+x\sum_{n=0}^{\infty}(1-x)^n=2$

Digamos que $T_x=\{\text{set of all $ |color{rojo}{texto}{sumas diferentes} $ for a given $ x $ }\}$

Se puede ver fácilmente que hay un número incontable de $\color{red}{\text{different sums}}$ .

Pregunta es que hay un número incontable de elementos distintos en $T_x$ para un determinado $x$ ?

Observación:

1. Se puede ver fácilmente que el elemento mínimo de $T_x$ es $\frac{1}{1-x}$ y el elemento máximo de $T_x$ es $\frac{1}{x}$ .

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

Pero no pude encontrar una manera de probar o refutar la incontabilidad. Cualquier ayuda sería apreciable.

$\blacksquare\space\space\blacksquare\space\space\blacksquare\space\space$ Gracias a MANMAID adjunto un nuevo esquema:

Dejemos que $0<x<1$

Answer 1

Formalización

• Para $n \in \mathbb{N}$ dejar $\{ 0, 1 \}^n$ denotan el conjunto de $n$ -secuencias binarias de elementos, es decir, el conjunto de funciones $f : \{ 0, 1, \ldots, n-1 \} \to \{ 0, 1 \}$ .
• Dejemos que $\{ 0, 1 \}^{\mathbb{N}}$ denotan el conjunto de secuencias binarias infinitas, es decir, el conjunto de funciones $s : \mathbb{N} \to \{ 0, 1 \}$ .
• Para $s \in \{ 0, 1 \}^{\mathbb{N}}$ y $n \in \mathbb{N}$ (o $s \in \{ 0, 1 \}^m$ y $n \leqslant m$ respectivamente) por $s \upharpoonright n$ denotamos el prefijo de $s$ de longitud $n$ es decir, la restricción $s \upharpoonright \{ 0, 1, \ldots, n-1 \}$ .
• Para $f \in \{ 0, 1 \}^n$ dejar $\alpha(f) = \# \{ k < n : f(k) = 0 \}$ y $\beta(s) = \# \{ k < n : f(k) = 1 \}$ (el número de ceros y unos en $f$ respectivamente).

Nótese que cualquier camino en el diagrama puede ser representado por una secuencia binaria infinita, por lo que podemos pensar en $\{ 0, 1 \}^{\mathbb{N}}$ como el conjunto de todos los caminos posibles.

Fijar $x \in \left( 0, \frac{1}{2} \right)$ y definir $\varphi : \{ 0, 1 \}^{\mathbb{N}} \to \mathbb{R}$ como

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

Así, $\varphi(s)$ representa claramente la suma asociada a la trayectoria $s$ . Así que la pregunta es: ¿es $\varphi \left[ \{ 0, 1 \}^{\mathbb{N}} \right]$ ¿incontable?

Solución

En $\{ 0, 1 \}^{\mathbb{N}}$ existe un orden lexicográfico natural, dado por $$s \prec t \iff (\exists n \in \mathbb{N}) \big[ s \upharpoonright n = t \upharpoonright n \wedge s(n) < t(n) \big].$$

En palabras: si $s, t$ son diferentes, encuentra la primera posición $n \in \mathbb{N}$ en la que difieren, por lo que $s(n) \neq t(n)$ y compararlos por el valor en esa posición. En tu diagrama, dos caminos diferentes divergen en algún punto y el que va hacia la izquierda será más pequeño con respecto a esta ordenación.

La observación clave es: dejemos $s \prec t$ . Entonces $\varphi(s) \leqslant \varphi(t)$ y $\varphi(s) = \varphi(t)$ si y sólo si hay $n \in \mathbb{N}$ tal que $s$ y $t$ acordar hasta $n$ y luego $s$ continúa como $0, 1, 1, 1, \ldots$ y $t$ continúa como $1, 0, 0, 0, \ldots$

Prueba.

A partir de la definición de $s \prec t$ tenemos $n$ tal que $s$ y $t$ acordar hasta $n$ (exclusivamente) y luego $0 = s(n) < t(n) = 1$ . Dejemos que $s^*$ sea una secuencia infinita definida como $s \upharpoonright n$ seguido de $0, 1, 1, 1, \ldots$ Del mismo modo, dejemos que $t_*$ empezar con $t \upharpoonright n$ y continuar como $1, 0, 0, 0, \ldots$

Tenga en cuenta que para cada $k \in \mathbb{N}$ tenemos $\beta( s \upharpoonright k) \leqslant \beta( s^* \upharpoonright k )$ desde $s$ y $s^*$ acordar hasta $n+1$ y luego $s^*$ se vuelve constantemente $1$ . Por lo tanto, $\varphi(s) \leqslant \varphi(s^*)$ ya que multiplicar las cosas por $1-x$ hace que sean mayores que multiplicar por $x$ . Del mismo modo, demostramos que $\varphi(t_*) \leqslant \varphi(t)$ .

También es fácil ver que si $u, v$ son secuencias binarias infinitas y $f \in \{ 0, 1 \}^m$ es una secuencia binaria finita tal que $u = f \frown v$ (donde $\frown$ denota contención), entonces

• si $k < m$ entonces $\alpha( u \upharpoonright k ) = \alpha( f \upharpoonright k )$ y $\beta( u \upharpoonright k ) = \beta( f \upharpoonright k ),$
• para $k \geqslant 0$ : $\alpha( u \upharpoonright (m+k) ) = \alpha( f ) + \alpha( v \upharpoonright k )$ y $\beta( u \upharpoonright (m+k) ) = \beta( f ) + \beta( v \upharpoonright k ).$

Por lo tanto,

$$\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).$$

Tomando $f$ para ser el prefijo común de $s$ y $t$ es decir $f = s \upharpoonright n = t \upharpoonright n$ obtenemos

$$\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).$$

Informática $\varphi(0, 1, 1, 1, \ldots) = 2 = \varphi(1, 0, 0, 0, \ldots)$ produce $\varphi(s^*) = \varphi(t_*)$ Así que $\varphi(s) \leqslant \varphi(t)$ .

Ahora bien, si $\varphi(s) = \varphi(t)$ entonces $\varphi(s) = \varphi(s^*)$ y $\varphi(t_*) = \varphi(t)$ , lo que implica claramente $s = s^*$ y $t = t_*$ Así que la reclamación ha sido probada.

Ahora dejemos que $A \subseteq \{ 0, 1 \}^{\mathbb{N}}$ sea el conjunto de todas las secuencias binarias infinitas que eventualmente se estabilizan en $1$ . A partir del hecho anterior, la restricción de $\varphi$ a $\{ 0, 1 \}^{\mathbb{N}} \setminus A$ es estrictamente creciente, y por tanto inyectiva. Pero $A$ es contable, por lo que $|\{ 0, 1 \}^{\mathbb{N}} \setminus A| = \mathfrak{c}$ Por lo tanto $\varphi \left[ \{ 0, 1 \}^{\mathbb{N}} \right]$ tiene cardinalidad $\mathfrak{c}$ así que en particular es incontable.

Más información

En esta sección daré menos detalles y me concentraré en cómo es más que en por qué es cierto. Espero que puedas llenar los vacíos si estás interesado.

El conjunto $\{ 0, 1 \}^{\mathbb{N}}$ puede considerarse como un espacio métrico conocido como conjunto de Cantor con la métrica definida como

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

No es difícil ver que el mapa $\varphi$ es continua, porque si $s, t$ acordar hasta $n$ es decir $s = f \frown u$ y $t = f \frown v$ para algunos $f \in \{ 0, 1 \}^n$ y $u, v$ infinito, entonces

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

por lo que la diferencia puede hacerse arbitrariamente pequeña haciendo $n$ grande. Ahora bien, el hecho demostrado anteriormente implica que $\varphi = \psi \circ p$ para alguna continua $\psi : [0, 1] \to \mathbb{R}$ , donde $p : \{ 0, 1 \}^{\mathbb{N}} \to [0, 1]$ es la suryección continua estándar

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

Desde $\psi$ es continua, desde la propiedad de Darboux es onto $\left[ \frac{1}{1-x}, \frac{1}{x} \right]$ por lo que también lo es $\varphi$ . Así que cada número $y \in \left[ \frac{1}{1-x}, \frac{1}{x} \right]$ puede obtenerse como una suma sobre un camino $s \in \{ 0, 1 \}^{\mathbb{N}}$ que es único hasta el caso descrito por el hecho que hemos demostrado.

Answer 2

La forma más habitual de dibujar esto es como un árbol binario, por lo que las trayectorias descendentes no llegan al mismo vértice. Entonces tienes un vértice en la raíz, dos en el siguiente nivel, cuatro en el siguiente, y $2^n$ en el nivel $n$ . A medida que se recorre el árbol se añade un bit al número binario que es la suma, $0$ si tomas la bifurcación de la izquierda y $1$ si tomas la derecha. Entonces está claro que se puede tener cualquier número en $[0,1]$ como la suma, por lo que hay un número incontable de sumas posibles. Sólo hay un número contable de vértices en el árbol, ya sea $1+2+3+4+\ldots$ o $1+2+4+8+\ldots$