Conjunto de los números reales y conjunto de potencias de los números naturales

Question

He aprendido que la cardinalidad del conjunto de potencias de los números naturales es igual a la cardinalidad de los números reales. ¿Cuál es la función que da la correspondencia uno a uno entre estos dos conjuntos?

También he aprendido que no existe ningún conjunto cuya cardinalidad esté estrictamente comprendida entre los números naturales y los números reales. ¿Existe alguna prueba de ello o al menos alguna intuición?

Answer 1

No es del todo correcto preguntar por "la función", porque si hay una, entonces hay muchas. Además, las biyecciones explícitas están muy sobrevaloradas. Podemos escribir una, pero es muy muy oh tanto más fácil utilizar el teorema de Cantor-Bernstein, y simplemente exhibir dos inyecciones.

Si insistes en escribir una biyección real, déjame identificar $\mathcal P(\Bbb N)$ con secuencias binarias infinitas (lo cual es bastante habitual). Ahora permítanme describir los pasos. Queremos llevar una secuencia binaria al número real en $[0,1]$ que tiene esta cadena binaria como expansión. Sin embargo, algunos números, por ejemplo $\frac12=0.1\bar0_2=0.0\bar1_2$ una secuencia con un número finito de $1$ y la otra tiene un número finito de $0$ 's.

1. Primero enumera todas las cadenas que contienen un número finito de $0$ las cadenas que contienen un número finito de $1$ 's. Se puede demostrar que ambos conjuntos son contablemente infinitos, incluso se pueden enumerar de una manera muy bonita. Escribámoslos como $p_n$ para la $n$ -con un número finito de ceros y $q_n$ para la $n$ -con un número finito de $1$ 's.

   El siguiente paso es tomar $f\colon2^\Bbb N\to2^\Bbb N$ definido como: $$f(x)=\begin{cases} q_{2k} & x=p_k\\ q_{2k+1} & x=q_k\\ x &\text{otherwise}\end{cases}$$ Fácilmente se trata de una inyección cuyo rango es $2^\Bbb N\setminus\{p_n\mid n\in\Bbb N\}$ .

2. Mapa actual $x\in2^\Bbb N$ a $r\in[0,1)$ tal que, $$r=\sum_{n\in\Bbb N}\frac{f(x)}{2^{n}}$$ que es el número real cuya expansión binaria es $f(x)$ . Se puede demostrar que se trata de una función suryectiva, ya que si un número tiene una expansión binaria entonces tiene una que tiene infinitas $0$ 's. También es inyectiva, ya que si un número real uno tiene dos expansiones binarias diferentes, podemos demostrar que exactamente una de ellas tiene un número finito de $0$ y el otro número finito de $1$ 's. Pero como usamos $f(x)$ Esto es imposible.

3. Encontrar una biyección entre $[0,1)$ y $\Bbb R$ . Normalmente se hace primero "doblando $0$ en" y tener una biyección entre $[0,1)$ y $(0,1)$ y luego usar algo como $\frac{2x-1}{x(x-1)}$ o una función similar para una biyección con $\Bbb R$ .

---

Utilizando el teorema de Cantor-Bernstein es mucho más fácil.

1. Tenga en cuenta en primer lugar que $\Bbb R$ puede inyectar en $\mathcal P(\Bbb Q)$ mediante mapeo $r$ a $\{q\in\Bbb Q\mid q<r\}$ . Desde $\Bbb Q$ es contable existe una biyección entre $\cal P(\Bbb Q)$ y $\cal P(\Bbb N)$ . Así que $\Bbb R$ inyecta en $\cal P(\Bbb N)$ .

2. A continuación, observe que podemos asignar $x\in2^\Bbb N$ a la fracción continua definida por la secuencia $x$ . O a un punto en $[0,1]$ definido por $\sum\frac{x(n)}{3^{n+1}}$ que podemos demostrar que es inyectiva en una demostración algo más sencilla.

Por último, como ya se ha dicho, la última parte es falsa. A partir de los axiomas habituales de la teoría de conjuntos moderna (léase: $\sf ZFC$ ) no podemos demostrar ni refutar que no existan cardinalidades intermedias entre $\Bbb N$ y $\Bbb R$ . La prueba de ello es difícil y requiere un profundo conocimiento de la teoría de conjuntos moderna [léase: axiomática], así como de la lógica.

Si la última parte le ha confundido de algún modo, quizá mi respuesta a esta pregunta pueda ayudarle, ¿Por qué (no) es cierta la hipótesis del continuo? .

Answer 2

Un mapeo explícito es difícil de escribir. Pero se puede ver una forma posible de construirlo a través de este argumento que muestra que el conjunto de potencias de $\mathbb{Z}$ y $\mathbb{R}$ tienen la misma cardinalidad. Empezaré mostrando $\mathbb{R}$ es incontable y luego utilizar esa idea para demostrar que los dos conjuntos tienen la misma cardinalidad.

En primer lugar, mostramos la prueba clásica de Cantor de que $\mathbb{R}$ es incontable. Bastaría con demostrar que $[0,1]$ es incontable. Suponemos que todo número real $x\in [0,1]$ tiene una expansión decimal que no termina en una secuencia infinita de 9's. Supongamos que $\mathbb{R}$ es contable. Podríamos entonces construir una biyección desde $\mathbb{Z}_+$ a $[0,1]$ . Escribir $x$ de la expansión decimal, $$x_1 = n_{1,1}n_{1,2},\cdots,n_{1,j}$$ $$x_2 = n_{2,1}n_{2,2},\cdots,n_{2,j}$$ y así sucesivamente, donde $n_{i,j}$ es algún número en $\{0,1,2,3,4,5,6,7,8,9\}$ . Supongamos que todos los números aparecen en el orden que hemos escrito anteriormente. Ahora $y_j=1$ si $n_{j,j}=0$ y $y_j=0$ si $n_{j,j}>0$ . Pero ahora tenemos desacuerdos con $y_j$ y $x_j$ en el $n$ ¡posición! Así que $y_{j}$ no está en nuestra lista. Sin embargo, $y_j$ es un número real. Por lo tanto, el intervalo $[0,1)$ es incontable. Además, los reales son incontables.

Ahora definimos una función $f: [0,1)\rightarrow \mathbb{Z}_+$ . Aviso $x \in [0,1)$ tiene una expansión binaria única (ya que la restricción anterior sobre los 9 infinitos no repetitivos es equivalente a los 1 repetitivos no infinitos). Por tanto, $x=\sum_{i=1}^{\infty} \, \frac{x_i}{2^i}$ donde cada $x_i$ es 0 o 1. Entonces tenemos $f(x)=\{i \, \, | \, \, i \in \mathbb{Z}_+ \wedge x_i=1\}$ como inyección. Observe que también podemos definir una inyección $g:P(\mathbb{Z}_+)\rightarrow [0,1)$ por $x_{i,n}=0$ si $i \notin n$ y $x_{i,n}=1$ si $i \in n$ donde $n\in P(\mathbb{Z}_+)$ . A continuación, utilizando la expansión decimal ordinaria en $n$ tenemos una inyección. Entonces, por el Teorema de Cantor-Schroeder-Bernstein, existe una función biyectiva desde $P(\mathbb{Z}_+)$ y $[0,1)$ . Pero tenemos la función inyectiva $h(x)=\frac{x}{2}$ de $[0,1]$ a $[0,1)$ y la función inyectiva $i(x)=x$ de $[0,1)$ a $[0,1]$ . Por lo tanto, existe una función biyectiva desde $[0,1]$ a $[0,1)$ . Por lo tanto, existe una función biyectiva desde $P(\mathbb{Z}_+)$ a $\mathbb{R}$ . Así que deben tener la misma cardinalidad, pero por encima, $\mathbb{R}$ es incontable. Entonces $P(\mathbb{Z})$ es incontable y de la misma cardinalidad que $\mathbb{R}$ .

En cuanto a tu otra pregunta, no se sabe si existe un conjunto con cardinalidad comprendida entre la de $\mathbb{N}$ y $\mathbb{R}$ . Sin duda no es una cuestión trivial y se conoce como el Hipótesis de continuidad .

Answer 3

Mi respuesta a su primera pregunta:

La estrategia que voy a seguir es utilizar el teorema de Schröder-Bernestein, que dice que para dos conjuntos $A$ y $B$ si existe una función inyectiva $f: A \rightarrow B$ y una función inyectiva $g: B \rightarrow A$ entonces existe una biyección entre $A$ y $B$ .

Voy a suponer que ya sabemos que existe una biyección entre el conjunto de potencias de los naturales, y el conjunto $B=\{(a_{1},a_{2},a_{3},\dots): a_{i} \in \{0, 1\}\}$ es decir, el conjunto de todas las tuplas ordenadas de 0 y 1. Y que existe una biyección entre los reales y el intervalo $A=[0,1)$ .

Si una biyección entre $A$ y $B$ existe, entonces existe una biyección entre el conjunto de potencias de los naturales y los reales.

Empecemos por $f: B \rightarrow A$ . Para cada elemento de $B$ utilizamos los elementos de la tupla como la expansión decimal de un elemento en A. Por ejemplo, $(0,1,1,0,\dots)$ mapas a $0.0110\dots$ . Se trata de una inyección, ya que, mientras no se repita ningún elemento en B, el elemento mapeado en A es distinto.

Para $g: A \rightarrow B$ donde $g$ mapea cualquier $a \in A$ espaciando el número de 1s en la tupla utilizando los dígitos de la expansión decimal de $a$ . Por ejemplo, si $a=0.2130\dots$ entonces $g(a)=(0, 0, 1, 0, 1, 0, 0, 0, 1, 1 \dots)$ . Esto también es una inyección, ya que ninguna expansión decimal distinta puede asignarse a la misma tupla.

Puesto que ambos $f$ y $g$ son inyectivas, entonces por el teorema de Schröder-Bernstein, existe una biyección entre $A$ y $B$ y, por tanto, entre $\mathcal{P}(\mathbb{N})$ y $\mathbb{R}$ .

Answer 4

El método más sencillo que conozco es relacionar elementos en $\mathcal{P}(\mathbf{N})$ a secuencias binarias en $(0,1)$ . Para cualquier $A \subset \mathbf{N}$ existe una secuencia natural $(a_n)$ tal que $a_n = 1$ si $n \in A$ , $a_n=0$ si $n \notin A$ . A continuación, podemos ver cualquier $x\in (0,1)$ como $\sum_{n=1}^{\infty}\frac{a_n}{2^n}$ donde $a_i \in \{0,1\}$ .

Una vez que lo tengas, utiliza el mapa $x \mapsto f(x)=\tan(\pi (x-1/2))$ para producir todos los números reales. Hay que tener un poco de cuidado, ya que los números racionales producen dos representaciones reales. Sin embargo, la idea debe quedar clara y te dará una idea de por qué esto es cierto.