La forma más sencilla de demostrar que $|\mathcal{P}(\mathbb{N})| = |\mathbb{R}| = c$

Question

¿Cuál es la forma más sencilla de demostrar (para un no matemático) que el conjunto de potencias del conjunto de los números naturales tiene la misma cardinalidad que el conjunto de los números reales, es decir, cómo construir una biyección de $\mathcal{P}(\mathbb{N})$ a $\mathbb{R}$ ?

Answer 1

Aquí está mi favorito (el más intuitivo que he visto): Definir la biyección en tres partes

Lo primero es fácil: tome su bijación favorita entre $\mathbb{R}$ y $(0,1)$ . (Incluso para un no-matemático es intuitivamente claro que se existe con sólo "contraer" $\mathbb{R}$ y un ejemplo puede ser dado explícitamente por $\frac{1}{\pi}arctan(x) +\frac{1}{2}$ ).

Entonces, considerando la expansión binaria de los números reales casi obtener una biyección entre $(0,1)$ y el conjunto $S$ de cadenas binarias infinitas, donde el número $0.1001110110010\dots$ corresponde a la cadena $0.1001110110010\dots$ etc. Digo "casi" porque las cadenas binarias $100000\dots$ y $01111\dots$ corresponden al mismo número real $0.10000 \dots = 0.01111\dots$ A un no matemático se le podría decir "podemos arreglar estos problemas porque no hay muchas picaduras con repeticiones $1$ 's, en comparación con el conjunto de TODAS las cadenas binarias" y seguir adelante.
(Para un matemático, esto se debe a que una cadena terminada en todo $1$ está determinada por su prefijo, que tiene longitud finita, y los matemáticos saben que el conjunto de cadenas binarias finitas es contable, y además por el argumento de diagonalización $\mathbb{R}$ es incontable. Esto permite modificar el mapa natural $S\rightarrow (0,1)$ en uno que es una biyección utilizando el método descrito al final de este enlace: https://nrich.maths.org/discus/messages/67613/67678.html?1133563921 Pero como he dicho, para un no matemático estas cuestiones no son importantes).

Por último, otra fácil: una cadena binaria $s\in S$ es por definición una secuencia de $0$ y $1$ que técnicamente puede definirse simplemente como una función $s:\mathbb{N}\rightarrow\{0,1\}$ . Dicha función determina un subconjunto $A_s\subset\mathbb{N}$ por " $a\in A_s$ si $s(a)=1$ " y de forma similar un subconjunto determina una función (que llamamos $s$ el función característica de $A_s$ en $\mathbb{N}$ ). Una forma intuitiva de pensar en este fenómeno es que una cadena binaria $s$ pasa por los elementos de $\mathbb{N}$ uno por uno y decide si está en el conjunto $A_s$ (con un $1$ ) o no (con un $0$ ). Esta correspondencia da la biyección entre $S$ y el conjunto de poderes $\mathcal{P}(\mathbb{N})$ .

Si lo combinamos todo, obtenemos $\left|\mathbb{R}\right|=\left|(0,1)\right|=\left|S\right|=\left|\mathcal{P}(\mathbb{N})\right|$

P.D. Este es el tipo de discurso en el que la gran mayoría de la gente llega a entender este teorema, porque es el contexto en el que se formula: conjuntos y funciones y biyecciones inteligentes. Si prefieren una descripción más elemental, parafrasearé lo que Euclides le dijo a un general a las órdenes de Alejandro Magno: no hay un camino real hacia las matemáticas. Esto es lo más elemental que puedo hacer sin escribir una introducción sobre la teoría de conjuntos :)

Answer 2

Si tiene que ser una biyección, yo optaría por las fracciones continuas (como señala J.D.):

1. Afirmar que para todo número real sólo existe una representación más corta del mismo como fracción continua ( $a_0 \in \mathbb{Z}$ , $a_i \in \mathbb{N}-\{0\}$ y si la fracción es finita, $a_{\text{last}} \in \mathbb{N}-\{0,1\}$ ).
2. Entonces explica que $P(\mathbb{N})$ es lo mismo que una secuencia infinita de 0s y 1s.
3. Demuestre que la secuencia infinita de 0s y 1s es la misma que la secuencia de números naturales de cualquier longitud (codificados en base 1 con unos intercalados por ceros, es decir, 2,3,0,1,0,0,0... = 11 0 111 0 0 1 00000..., la secuencia finita tiene un número finito de ceros, la secuencia vacía = 11111...).
4. La secuencia de números naturales es una fracción continua:
   • secuencia vacía es 0;
   • secuencia de longitud 1 debe ser transformada por cualquier $\mathbb{N} \to \mathbb{Z} -\{0\}$ bijection;
   • si la secuencia es de longitud 2 o mayor, transformar el primer término por cualquier $\mathbb{N}\to\mathbb{Z}$ biyección y añadir $1$ al resto;
   • si la secuencia es finita, aumentar el último término en 1 adicional.

Esto es lo más sencillo biyección Se me ocurre. Pero probablemente no tenga que ser una biyección, en cuyo caso el argumento es mucho más sencillo:

1. Para un conjunto determinado $X$ Primero, clasifícalo.
2. Toma el primer número más pequeño, si es impar, el resultado es negativo.
3. Toma el segundo más pequeño, éste será la parte entera del real.
4. Tomar el resto (en orden ascendente) todo modulo $10$ --esta será la cola del real.

Volviendo:

1. Tomar sólo los reales de $[0,1]$ , donde $1$ está representado por $0.(9)$ ,
2. $n \in Y$ si y sólo si el dígito del $n$ -El cuarto lugar es impar.

Editar 1: para simplificar un poco el paso 4 en la biyección, se podría interpretar la secuencia de números naturales de manera que el primero diga cuántos 1s hay al final del flujo.

Editar 2: Se me pasó el caso del número finito de ceros en (3), gracias a Marc van Leeuwen por señalarlo. Creo que el resultado después de la corrección es aún más bonito que antes.

Espero que eso ayude ;-)

Answer 3

Para esta respuesta, utilice $\{1,2,\ldots\}=\mathbb{N}$ .

A. Para cada real positivo $x\in (0,1]$ existe un único subconjunto infinito $A$ de $\mathbb{N}$ tal que $x = \sum_A 2^{-p}$ .

(Para encontrar números en $A$ se podría empezar con algunos $p$ para que $2^{-p}$ es al menos la mitad de la distancia a $x$ pero no $x$ sí mismo. A continuación, continúe con esa idea para cada distancia restante).

B. Todo subconjunto infinito de $\mathbb{N}$ corresponde a un elemento de $(0,1]$ de esta manera.

(Pídales que se imaginen sumando todos esos $2^{-p}$ y apelar a su sentido intuitivo de convergencia de una serie acotada creciente).

C. Ahora sólo tienes que usar $f(x) = \tan(\pi x - \frac\pi2)$ que lleva $(0,1)$ en $\mathbb{R}$ (y no te preocupes por el punto final $1$ ). Esto demuestra que los subconjuntos infinitos de $\mathbb{N}$ son equitativos con $\mathbb{R}$ .

(Se podría explicar estirando $(0,1)$ hasta que se "convierte" en $\mathbb{R}$ .)

D. Como la colección de subconjuntos finitos de $\mathbb{N}$ es contable, esto completa la prueba.

(Agitar las manos y decir algo como "los conjuntos finitos son más pequeños que los infinitos" ;)

Answer 4

He aquí una biyección inspirada en la dada por dtldarek pero he tratado de reformularlo de la manera menos técnica posible. En lugar de fracciones continuas, hago uso de las Stern-Brocot (o mejor, uno con raíz $0$ y se completa con una imagen reflejada añadida a su izquierda para cubrir tanto los números negativos como los positivos).

Pero no necesitaré una descripción técnica de la misma. De hecho, puedo hacerlo con cualquier árbol etiquetado por números racionales (o incluso se podrían permitir números reales arbitrarios), con las siguientes propiedades:

• Para cualquier nodo etiquetado con un número $y$ las etiquetas $x$ de todos los nodos del subárbol izquierdo por debajo de él tienen $x<y$ y las etiquetas $z$ de todos los nodos del subárbol derecho por debajo de él tienen $z>y$ .
• Si en este nodo $y$ uno va al hijo izquierdo, y luego sigue yendo de un nodo a su hijo derecho indefinidamente, se obtiene una secuencia de etiquetas (crecientes) $x$ que converge a $y$ .
• Si en este nodo $y$ uno va al hijo de la derecha, y luego sigue yendo de un nodo a su hijo de la izquierda indefinidamente, se obtiene una secuencia de etiquetas (decrecientes) $z$ que converge a $y$ .
• Si desde el nodo raíz se desciende al hijo izquierdo (resp. derecho) indefinidamente, la secuencia decreciente (resp. creciente) de etiquetas obtenidas diverge a $-\infty$ (resp. a $+\infty$ ).

Estas propiedades garantizan que el conjunto (contable) de todas las etiquetas forma un subconjunto denso de los números reales (el conjunto de todos los racionales en el caso del árbol de Stern-Brocot simetrizado), y que para cualquier número real $r$ que no aparecen en el árbol, se tiene un único camino a infinito cuyas etiquetas convergen a $r$ que se puede encontrar utilizando el árbol como árbol de búsqueda binario Cuando en una etiqueta $y$ , descienden al subárbol de la izquierda si $r<y$ y al subárbol de la derecha si $r>y$ . Tenga en cuenta que, dado que $r$ no es en sí misma una etiqueta que esté bien definida, y el camino infinito así obtenido no continuará más allá de algún punto en una misma dirección indefinidamente En otras palabras, sigue (en última instancia) cambiando de dirección, para siempre.

Ahora la idea básica es utilizar, dado un subconjunto $S$ de $\mathbb N$ la presencia/ausencia de números sucesivos para determinar la dirección de descenso en el árbol; por ejemplo, ir a la izquierda en el paso $i$ si $i\notin S$ y a la derecha si $i\in S$ . Salvo las dos posibilidades extremas, las etiquetas a lo largo del camino infinito obtenido convergen, y tomando su límite casi define una biyección a los números reales (con $\{-\infty,\infty\}$ añadido para los extremos divergentes).

Sin embargo, el mapa no es inyectivo: todos los números que aparecen como etiqueta $y$ son el límite para $2$ diferentes caminos, ambos pasando por el nodo etiquetado $y$ : uno que desciende al hijo izquierdo de $y$ y luego a la derecha para siempre, y otro que desciende al hijo derecho de $y$ y luego se fue para siempre. Este defecto, así como los extremos divergentes, pueden casi se repara mediante la siguiente regla: para aquellos caminos que más allá de algún punto continúan indefinidamente en la misma dirección (estos corresponden a subconjuntos de $\mathbb N$ que son finitos o el complemento de un conjunto finito), se detienen después del último movimiento en la dirección opuesta, y toman como imagen la etiqueta del nodo alcanzado. Este cambio elimina las dos trayectorias infinitas cuyas etiquetas convergían a $y$ y lo sustituye por el camino único que era de la forma: descender a $y$ , cambiar de dirección allí y después de eso no cambiar de dirección nunca más.

El único pequeño defecto que queda es que para los dos caminos extremos, nuestra regla estipula truncar después del último paso en la dirección opuesta, paso que no existe: lo natural es eliminar todos los pasos, y mapear a la etiqueta de la raíz del árbol ( $0$ para el árbol de Stern-Brocot simetrizado). Los dos subconjuntos que "colisionan" aquí son el conjunto vacío y todo $\mathbb N$ . Para reparar esto empiezo por modificar $\mathcal{P}(\mathbb N)$ con el fin de "esconder" (hacer desaparecer) el conjunto vacío. La siguiente regla lo hace: para todos los segmentos iniciales finitos, es decir, subconjuntos de la forma $\{i\in\mathbb N\mid i<n\}$ para algunos $n\in\mathbb N$ (que incluye el conjunto vacío para $n=0$ ), añadirle el elemento mínimo $n$ originalmente ausente de ella. Este mapa $\mathcal{P}(\mathbb N)$ de forma biyectiva a $\mathcal{P}(\mathbb N)\setminus\{\emptyset\}$ y después de esta transformación se puede utilizar el mapa descrito anteriormente, que ahora es una biyección a $\mathbb R$ . ¡Uf!

Answer 5

Aquí está mi intento de hacer los pasos tan matemáticamente no amenazantes como sea posible, incluso a expensas de la elegancia:

Partimos de un número real cualquiera, y queremos transformarlo en un conjunto único de números naturales, tal que todo subconjunto de $\mathbb N$ es golpeado exactamente una vez.

Paso 1: Apretar la línea real en el intervalo semiabierto entre $0$ y $1$ :

• Si el número era $0$ entonces se mantiene sin cambios.
• Si el número era un entero positivo $n$ y sustituirlo por $\frac 1{2n}$ .
• Si el número fuera un no-integro positivo, digamos $+x$ y sustituirlo por $\frac1{2(x+1)}$ .
• Si el número fuera negativo, digamos $-y$ y sustituirlo por $\frac12 + \frac1{2(y+1)}$ .

(Esta no es una forma especialmente bonita de hacerlo, matemáticamente hablando, pero es más fácil de entender que muchas otras alternativas más ingeniosas).

Pausa. Compruebe que cada número entre 0 (inclusivo) y 1 (exclusivo) es golpeado exactamente una vez.

Paso 2: Escribe la fracción decimal del número. Empezará por " 0. " seguido de una secuencia contablemente infinita de decimales. Si se puede representar el número exactamente con un número finito de dígitos, se puede completar con infinitas repeticiones 0 s que la parte de atrás. No utilices representaciones que terminen en infinitos "9".

(Hay una cantidad considerable de sofisticación matemática que se barre bajo la alfombra en este paso, pero estoy asumiendo que estás intuitivamente familiarizado con las fracciones decimales, y sabes que $0.999... = 1$ ).

Paso 3: Retire la inicial 0. .

Pausa. Comprueba que cada secuencia infinita de dígitos es golpeada exactamente una vez, excepto que las secuencias que terminan en infinitas repeticiones 9 s son no golpear.

Paso 4: Codificar los dígitos como unos y ceros, utilizando una tabla como

0 becomes 0000    5 becomes 0101
1 becomes 0001    6 becomes 0110
2 becomes 0010    7 becomes 0111
3 becomes 0011    8 becomes 10
4 becomes 0100    9 becomes 11

Los detalles precisos de la codificación no son importantes, salvo para señalar que si codificamos cualquier secuencia de dígitos de esta manera, no necesitamos mantener alrededor ningún separador entre los dígitos sucesivos. Se pueden reconstruir los dígitos sin ellos, porque el primer bit de un dígito codificado determina si se trata de una codificación de 4 o 2 bits. Además, una secuencia que termina en una repetición infinita 9 (pero sólo tales secuencias) se asignarían a una secuencia que termina en una repetición infinita 1 s.

Pausa. Comprueba que cada secuencia infinita de dígitos es golpeada exactamente una vez, excepto que las secuencias que terminan en infinitas repeticiones 1 s son no golpear.

Paso 5: Obtener las secuencias que terminan en infinito repetidas 1 s incluido, por esta norma:

• Si la secuencia ya tiene un número infinito de 1 s (que deben intercalarse con infinitas 0 s en algún patrón o no), entonces déjelo como está.
• Si la secuencia sólo tiene un número finito de 1 s, y comienza con un 0 y luego cortar la parte inicial 0 y dejarlo de otra manera como está.
• Si la secuencia sólo tiene un número finito de 1 s y comienza con un 1 y luego cortar la parte inicial 1 y voltear cada elemento restante de la secuencia de 1 a 0 o viceversa .

Pausa. Asegúrese de que cada secuencia infinita de ceros o unos es golpeada exactamente una vez, sin excepciones.

Paso 6: Tome el subconjunto de $\mathbb N$ que consiste en las posiciones de la secuencia donde un 1 se encuentra.

Asegúrese de que cada subconjunto de $\mathbb N$ es golpeado exactamente una vez.