Biyección simple entre reales y conjuntos de números naturales

Question

Utilizando el teorema de Cantor-Bernstein-Schröder, es fácil demostrar que existe una biyección entre el conjunto de los reales y el conjunto de potencias de los números naturales. Sin embargo, resulta difícil enunciar explícitamente dicha biyección, especialmente si el objetivo es encontrar una biyección que sea lo más sencilla posible de enunciar.

La biyección explícita más sencilla que se me ha ocurrido puede definirse como sigue:

En realidad, defino una biyección de los reales a las secuencias binarias (es decir, secuencias de 0s y 1s). Dado que existe una bijección canónica trivial entre las secuencias binarias y el conjunto de potencias de los números naturales, esto puede ser fácilmente modificado a una bijección de los reales al conjunto de potencias de los números naturales.

Decimos que una secuencia binaria tiene una cola infinita si a partir de algún término todos los términos de la secuencia son 0s o todos son 1s.

Para cada real x entre 0 y 1 hay una o dos secuencias binarias que se califican como representaciones binarias de x. Si hay dos representaciones binarias de x, entonces ambas tienen una cola infinita, una en 0s y la otra en 1s.

Sea [x] la parte entera de un real x.

Ahora la biyección f se define sobre un real x distinguiendo cuatro casos:

1. x-[x] tiene dos representaciones binarias y [x] es no negativo: Entonces se establece que f(x) es la secuencia que comienza con [x] muchos 1s seguidos de un 0 y la representación binaria de x-[x] que tiene una cola infinita en 0s.

2. x-[x] tiene dos representaciones binarias y [x] es negativo: Entonces f(x) es la secuencia que comienza con -[x]-1 muchos 1s seguidos de un 0 y la representación binaria de x-[x] que tiene una cola infinita en 1s.

3. x-[x] tiene una representación binaria y [x] es no negativo: Entonces f(x) se establece como la secuencia que comienza con 1 seguido de [x] muchos 1s, un 0 y la representación binaria de x-[x].

4. x-[x] tiene una representación binaria y [x] es negativa: Entonces f(x) se establece como la secuencia que comienza con 0 seguido de -[x]-1 muchos 1s, un 0 y la representación binaria de x-[x].

La idea es que para los reales con dos representaciones binarias, se utiliza la elección entre las dos como indicación del signo, mientras que para los reales con una sola representación binaria, el signo debe mencionarse en un bit separado.

¿Existe una biyección de los reales al conjunto de potencias de los números naturales que sea más fácil de definir explícitamente que la que acabamos de presentar?

Answer 1

Creo que esta cuestión es más interesante de lo que parece a primera vista.

La respuesta depende en parte de cómo se defina un número real. Por ejemplo, una forma estándar de definir los números reales es mediante cortes Dedekind. Entonces, suponiendo que se da por supuesta la biyección estándar en zigzag entre los racionales y los enteros, el problema se reduce a encontrar una biyección explícita entre cierta conjuntos de números enteros (los correspondientes a los cortes Dedekind) y todo conjuntos de números enteros. No he visto a nadie intentar hacer esto directamente.

Tal y como has planteado el problema, parece que das por hecho las representaciones binarias de los reales. Entonces la dificultad básica es la molesta dicotomía entre conjuntos finitos y conjuntos infinitos. (El uso de fracciones continuas, como otros han sugerido, no ayuda mucho aquí, porque sigues atascado con el molesto problema de finito/infinito). Los reales entre 0 y 1 se ponen fácilmente en biyección con infinito conjuntos de números enteros, desestimando las representaciones binarias que terminan con 0 repetidos. Dejando que $\cal I$ denota la familia de todos los conjuntos infinitos de números enteros, ahora queremos encontrar una biyección $\phi$ entre $\cal I$ y $2^{\mathbb N}$ . Una forma sencilla de hacerlo es dejar que $\phi(x) = x$ a menos que $x$ es cofinito ya que sólo hay un número contable de conjuntos cofinitos de números enteros, y luego elija su biyección favorita entre una copia de $\mathbb N$ y dos copias de $\mathbb N$ para biyectar conjuntos cofinitos con conjuntos finitos/cofinitos.

Si quieres todos los reales, en lugar de sólo los reales entre 0 y 1, entonces tendrás que modificar la construcción anterior, pero creo que el principal punto de fricción finito/infinito seguirá siendo el mismo independientemente de lo que intentes hacer. En particular, si entiendo bien tu construcción, el uso de un $\pm$ puede considerarse como la implementación de la biyección necesaria entre una copia de $\mathbb N$ y dos copias de $\mathbb N$ .

Por cierto, una cuestión relacionada es encontrar una biyección explícita entre $(0,1)$ y $(0,1) \times (0,1)$ . Intercalar representaciones binarias es el enfoque estándar, pero hay que tener cuidado con los reales con dos representaciones binarias diferentes. Para solucionar este problema, hay que descartar las representaciones que terminan con 0 repetidos y dividir una representación binaria en bloques, donde un bloque consiste en un único 1, precedido por una cadena (posiblemente vacía) de 0 consecutivos. A continuación, intercalar bloques de dígitos en lugar de dígitos individuales. Creo que esta construcción se remonta a Dedekind.

Answer 2

• Un conjunto de números naturales puede denotar una secuencia de números naturales como {1,2,3} denota 1,1,1 y {2,4,6,26} denota 2,2,2,20.
• Una secuencia de números naturales denota un número real de forma única utilizando la fracción continua.

Por ejemplo N = {1,2,3,4,5,...} denota la secuencia 1,1,1,1,... que es la proporción áurea.

Answer 3

Aquí hay una biyección usando secuencias binarias, en cuatro casos:

1. Para cada finito $A\subset\mathbb N$ se elige un número entero positivo. Por ejemplo, añadiendo 1 al entero que tiene en su representación binaria los bits de los números de posición contenidos en el subconjunto puestos a 1. (El LSB tiene la posición número 1)

2. $\mathbb N\mapsto0$ .

3. $\mathbb N\setminus\{n\}\mapsto-n$ .

4. El resto de subconjuntos $B\subset\mathbb N$ se representan como una cadena de infinitos símbolos. Un $i$ Este símbolo tiene valor $1$ cuando $i\in B$ , de lo contrario es $0$ . Hay al menos dos $0$ s. Antes de la primera $0$ la cadena tiene $k$ $1$ s. La subcadena detrás de la primera $0$ se utiliza como fracción binaria para un real $x$ . Para los subconjuntos con $k$ el verdadero $\frac{k}{2+x}$ y para los subconjuntos con impar $k$ el verdadero $-\frac{k+1}{2+x}$ es elegido.

( $x < 1$ ya que la fracción tiene al menos un 0 y $x > 0$ tiene único, ya que debido al caso 1 la fracción no tiene cola infinita en 0's)

El caso 4 está tomado de Marcos Cramer y para la separación en subconjuntos finitos e infinitos he seguido a Timothy Chow.

Answer 4

La idea de combinar representaciones unarias y binarias parece interesante pero tengo problemas con la biyección. Por ejemplo, echo de menos un número real para la secuencia binaria que sólo contiene 1s ya que cada secuencia definida en el caso 1 a 4 tiene al menos un 0. O no puedo ver un número real para secuencias como 11101111.... . Esto no coincide con el caso 1 ya que no termina con 0s. Tampoco es el caso 2 o 3 ya que 0.1111...=1 no es posible para x-[x]. No es el caso 4 ya que no empieza por 0. A mí me parece que los casos 1 y 2 son para racionales no enteros y los casos 3 y 4 son para enteros (ya que para los enteros x-[x]=0 sólo tiene una representación binaria) e irracionales. Pero esto no se ajusta a la idea que se menciona a continuación, ya que todos los enteros, excepto el 0, tienen dos representaciones binarias, pero estas dos representaciones no se utilizan para indicarnos el signo.

Me gusta el enfoque de la fracción continua. Pero tenemos que decir cómo tratar con el conjunto vacío en P(N) y cuando se utiliza log para fracciones continuas positivas tenemos que señalar cómo deshacerse de la fracción continua con valor 0.

Se me ocurrió lo siguiente:

Sea z(n) = [n/2] cos(Pi n) siendo [x] la parte entera de x.

Mapea enteros a subconjuntos de N con menos de 2 elementos:

{} <--> 0

{a} <--> z(a+1)

Mapea racionales no enteros a otros subconjuntos finitos de N con al menos 2 elementos:

{a, b, c, ..., u, v, w} <--> CF(z(a), b-a, c-b, ... v-u, w-v+1)

Mapear irracionales a subconjuntos infinitos de N:

{a, b, c, ...} <--> CF(z(a), b-a, c-b, ...)

con CF(.) denotando fracciones continuas regulares con el último coeficiente > 1.