La biyección entre $\mathbb{R}$ y $\{(X,Y), X\subset Y\subset \mathbb{N}\}$

Question

¿Alguien sabe cómo construir una biyección entre $\mathbb{R}$ y $\{(X,Y), X\subset Y\subset \mathbb{N}\}$ ?( $\subset$ significa "se encuentra en o es igual a")

Agradeceré cualquier ayuda.

Gracias de antemano.

Answer 1

Tenga en cuenta que en lo que sigue asumo que $0\notin\mathbb{N}$ (porque creo que así es un poco más fácil escribir la biyección). Por supuesto, ajustando por $0\in N$ es trivial.

Paso 1: Definir una biyección desde $\mathbb{R}$ al intervalo $(0,1)$ . Esto es fácil, por ejemplo $$ f(x) = \mathrm{e}^{-\mathrm e^x} $$

Paso 2: Definir una biyección desde $(0,1)$ a $(0,1]$ mediante la función $$F(x) = \begin{cases} \frac{1}{n-1} & x=\frac1n, n\in\mathbb{N}, n>1\\ x & \text{otherwise} \end{cases}$$

Paso 3: Para cada número $y\in(0,1]$ , toma la expansión ternaria. Elija siempre la expansión que termine en " $222\ldots$ " en lugar de " $000\ldots$ ". Ahora defina $$g(y) = (\mathcal{X}, \mathcal{Y})$$ donde $$\begin{align} \mathcal{X} &= \{n\in\mathbb{N}: \text{The $ n $-th digit of the ternary representation of $ y $ is $ 2 $}\}\\ \mathcal{Y} &= \{n\in\mathbb{N}: \text{The $ n $-th digit of the ternary representation of $ y $ is not $ 0 $}\} \end{align}$$ Obviamente $\mathcal{X}\subset\mathcal{Y}\subset{N}$ . Sin embargo, por construcción, sólo obtenemos infinitos $\mathcal{Y}$ (porque el finito $\mathcal{Y}$ correspondería a una expansión ternaria que termina en el periodo $0$ ). Por otro lado, todos los pares de $\mathcal{X}$ e infinito $\mathcal{Y}$ con $\mathcal{X}\subset\mathcal{Y}$ definen de forma única un $y\in(0,1]$ .

Prueba de que $g$ es biyectiva:

Para cualquier $y\in (0,1]$ hay (gracias a la regla de desambiguación de no tomar nunca la representación periódica 0) exactamente una representación ternaria, y en cada una de esas representaciones hay exactamente una $y$ .

Los conjuntos $\mathcal{X}$ y $\mathcal{Y}$ codificar exactamente la secuencia de dígitos (dígito $n$ es $0$ si $n\notin\mathcal{Y}$ , dígito $n$ es $1$ si $n\in\mathcal{Y}\setminus\mathcal{X}$ , dígito $n$ es $2$ si $n\in\mathcal{X}$ ). Mientras $\mathcal{Y}$ es infinita, la representación ternaria correspondiente no será finita (final en periodo $0$ ), y viceversa. Por lo tanto, tenemos un mapeo uno a uno entre los pares de conjuntos con infinito $\mathcal{Y}$ y las representaciones ternarias infinitas, y por tanto los números reales en el intervalo $(0,1]$ .

Paso 4: Ahora sólo queda mapear los pares de conjuntos con la propiedad de subconjunto donde $\mathcal{Y}$ es infinito al conjunto de pares de conjuntos posiblemente finitos con la propiedad de inclusión.

Esta biyección del conjunto de todos los pares al conjunto de infinitos pares (nota: es la dirección opuesta que necesitamos, pero creo que es más fácil de escribir que la inversa) viene dada por $$h(X,Y) = \begin{cases} (X,Y) & \text{neither $ Y $ nor $\mathbb {N} \setminus X $ is finite}\\ (X+1,Y+1) & \text{$\mathbb {N} \setminus X $ is finite}\\ \left(\{1\}\cup\left((\mathbb{N}\setminus Y)+1\right),\{1\}\cup\left((\mathbb{N}\setminus X)+1\right)\right) & \text{Y is finite} \end{cases}$$ Aquí $X+1 = \{n+1: n\in X\}$ .

Por lo tanto, la biyección completa es $h^{-1}\circ g\circ F\circ f$ .

Answer 2

No, no se puede dar una biyección "explícita". Lo que puedes hacer es mostrar que tu conjunto $S=\{(X,Y):X\subset Y\subset \mathbb{N}\}$ tiene la misma cardinalidad que $\mathcal{P}(\mathbb{N})$ (el conjunto de subconjuntos de $\mathbb{N}$ que se sabe que es equipotente a $\mathbb{R}$ .

Usted tiene una inyección obvia $S\to \mathcal{P}(\mathbb{N})\times \mathcal{P}(\mathbb{N})$ para que $|S|\le|\mathcal{P}(\mathbb{N})\times\mathcal{P}(\mathbb{N})|=|\mathcal{P}(\mathbb{N})|$ .

También tiene una inyección $\mathcal{P}(\mathbb{N})\to S$ definido por $Y\mapsto(\emptyset,Y)$ Así que $|\mathcal{P}(\mathbb{N})|\le|S|$ .

Mostrar una biyección explícita $S\to\mathcal{P}(\mathbb{N})\times\mathcal{P}(\mathbb{N})$ ya sería bastante complicado, pero el teorema de Cantor-Schröder-Bernstein da la conclusión.

Son necesarias algunas ligeras modificaciones si con $\subset$ quieres decir "inclusión estricta".