[GaToMi]

Hola, hace tiempo que no publico :p
Tengo una pregunta:
Si tenemos dos conjuntos X e Y numerables, ¿es numerable Biy(X,Y)? (Definimos Biy(A,B) como el conjunto de las funciones biyectivas de A a B).

[Masacroso]

Hola, hace tiempo que no publico :p
Tengo una pregunta:
Si tenemos dos conjuntos X e Y numerables, ¿es numerable Biy(X,Y)? (Definimos Biy(A,B) como el conjunto de las funciones biyectivas de A a B).

Si los conjuntos son finitos entonces el número de biyecciones entre ambos corresponde al número de permutaciones de uno de ellos, es decir si \( |X|=n \) entonces el número de biyecciones es \( n! \).

Si los conjuntos son infinito contables entonces el número de permutaciones de cualquiera de los conjuntos sería \( \aleph_0^{\aleph_0} \), ya que por cada posición de una permutación puedes hacer una elección entre infinitos elementos. Y tendríamos que \( \aleph_0< 2^{\aleph_0}\le\aleph_0^{\aleph_0} \).

[geómetracat]

Si los conjuntos son infinito contables entonces el número de permutaciones de cualquiera de los conjuntos sería \( \aleph_0^{\aleph_0} \), ya que por cada posición de una permutación puedes hacer una elección entre infinitos elementos. Y tendríamos que \( \aleph_0< 2^{\aleph_0}\le\aleph_0^{\aleph_0} \).

Es interesante notar que \( \aleph_0^{\aleph_0} = 2^{\aleph_0} \). En efecto,
\( 2^{\aleph_0} \leq \aleph_0^{\aleph_0} \leq (2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0 \cdot \aleph_0} = 2^{\aleph_0} \).
Por otro lado, también es interesante notar que el cardinal del conjunto de biyecciones coincide con el de todas las funciones. En un sentido informal, "hay tantas biyecciones entre conjuntos infinitos numerables como funciones entre ellos".

[jbgg]

Defino \( A \) como el conjunto de todas las biyecciones entre \( \mathbb{N} \), esto es \( A=\{\sigma:\mathbb{N}\rightarrow\mathbb{N}:\sigma\text{ es biyección}\} \).

Una forma de verlo es definiendo una función inyectiva de un conjunto no numerable en \( A \). Por ejemplo la que defino a continuación.

Voy a asociar a cada número \( x\in[0,1]\setminus\mathbb{Q} \) una biyección \( \sigma_x\in A \). Esta asociación se puede llevar a cabo de la siguiente manera, considero la expresión de \( x\in [0,1]\setminus\mathbb{Q} \) en su expresión binaria como \( x = \sum_{k=1}^\infty x_k 2^{-k} \), y los conjuntos \( X_0 = \{k: x_k = 0\} \) y \( X_1=\{k : x_k = 1\} \), se verifica que \( X_0 \) y \( X_1 \) son conjuntos infinitos (esto es porque si no lo fueran entonces \( x \) sería racional) y además \( X_0\cup X_1 = \mathbb{N} \).

Defino \( \sigma_x(1) = \min X_1 \), y \( \sigma_x(2p+1) = \min X_1\setminus\{\sigma_x(1),\ldots,\sigma_x(2p-2)\} \), para \( p\geq1 \). Para los pares definimos \( \sigma_x(2) = \min X_0 \), y \( \sigma_x(2p) = \min X_0\setminus\{\sigma_x(2),\ldots,\sigma_x(2p-1)\} \), para \( p\geq2 \).

Definimos la función \( f:[0,1]\setminus\mathbb{Q}\rightarrow A \) por \( f(x) = \sigma_x \), donde \( \sigma_x \) está dada anteriormente. Se verifica que \( f \) es inyectiva y por tanto \( A \) es no numerable porque \( [0,1]\setminus\mathbb{Q} \) no es numerable.

[jbgg]

En realidad, ahora que lo pienso, también se puede hacer por un argumento similar al de la diagonal de Cantor. Lo único que hay construir la matriz adecuadamente. Me pongo a ello, ya que me acabo de dar cuenta.

Por contradicción supongamos que el conjunto \( A=\{\sigma:\mathbb{N}\rightarrow\mathbb{N} : \sigma\text{ es una permutación}\} \) es numerable, entonces numerémoslo como

\( A=\{\sigma_1,\ldots,\sigma_k,\ldots\}. \)

Construimos la siguiente matriz

\( \begin{pmatrix} \sigma_1(1) & \sigma_2(1) & \cdots\\ \sigma_1(2) & \sigma_2(2) & \cdots \\ \vdots & \vdots & \ddots \end{pmatrix}, \)

y cada entrada la modificamos poniendo el valor \( 0 \) si es par y el valor \( 1 \) si es impar, esto es queda la matriz

\( M = \begin{pmatrix} \phi(\sigma_1(1)) & \phi(\sigma_2(1)) & \cdots\\ \phi(\sigma_1(2)) & \phi(\sigma_2(2)) & \cdots \\ \vdots & \vdots & \ddots \end{pmatrix}, \)

donde \( \phi(n) = \left\{\begin{array}{ll} 0 & \text{ si } n \text{ es par,}\\ 1 & \text{ si } n \text{ es impar.}\\\end{array}\right. \)

Si aplicamos el argumento de diagonal de Cantor a la matriz \( M \), esto es quedarnos con la diagonal \( (\phi(\sigma_1(1)),\phi(\sigma_2(2)),\ldots) \) y cambiarle el valor, si es cero lo transformamos en 1 y si es 1 se transforma en 0, esto es consideramos el elemento \( v=(\overline{\phi(\sigma_1(1))},\overline{\phi(\sigma_2(2))},\ldots) \), donde \( \overline{0} = 1 \) y \( \overline{1}=0 \). Se verifica que \( v \) no puede ser ninguna columna de la matriz \( M \), pero esto contradice que no esté dicha combinación (¿esto se podría demostrar? Creo que no es inmediato...).

Perdón, pensé que funcionaría la idea, pero ahora que lo escribo me es difícil argumentar de que el elemento \( v \) deba ser una combinación válida (¿quién quita que no sea todo cero y por tanto no debería de estar en \( M \)?). El problema es que son biyecciones, con funciones en general el argumento sí es válido, pero al ser biyecciones no es inmediato (y de hecho no estoy seguro de que funciones) el argumento.

Pido disculpas por no completarlo, pensaba borrar este mensaje, pero por si acaso a alguien se le ocurre alguna forma de arreglarlo pues aquí lo dejo.

[geómetracat]

Defino \( A \) como el conjunto de todas las biyecciones entre \( \mathbb{N} \), esto es \( A=\{\sigma:\mathbb{N}\rightarrow\mathbb{N}:\sigma\text{ es biyección}\} \).

Una forma de verlo es definiendo una función inyectiva de un conjunto no numerable en \( A \). Por ejemplo la que defino a continuación.

Voy a asociar a cada número \( x\in[0,1]\setminus\mathbb{Q} \) una biyección \( \sigma_x\in A \). Esta asociación se puede llevar a cabo de la siguiente manera, considero la expresión de \( x\in [0,1]\setminus\mathbb{Q} \) en su expresión binaria como \( x = \sum_{k=1}^\infty x_k 2^{-k} \), y los conjuntos \( X_0 = \{k: x_k = 0\} \) y \( X_1=\{k : x_k = 1\} \), se verifica que \( X_0 \) y \( X_1 \) son conjuntos infinitos (esto es porque si no lo fueran entonces \( x \) sería racional) y además \( X_0\cup X_1 = \mathbb{N} \).

Defino \( \sigma_x(1) = \min X_1 \), y \( \sigma_x(2p+1) = \min X_1\setminus\{\sigma_x(1),\ldots,\sigma_x(2p-2)\} \), para \( p\geq1 \). Para los pares definimos \( \sigma_x(2) = \min X_0 \), y \( \sigma_x(2p) = \min X_0\setminus\{\sigma_x(2),\ldots,\sigma_x(2p-1)\} \), para \( p\geq2 \).

Definimos la función \( f:[0,1]\setminus\mathbb{Q}\rightarrow A \) por \( f(x) = \sigma_x \), donde \( \sigma_x \) está dada anteriormente. Se verifica que \( f \) es inyectiva y por tanto \( A \) es no numerable porque \( [0,1]\setminus\mathbb{Q} \) no es numerable.

Esta muy bien la demostración. Fíjate que en realidad pruebas que el cardinal del conjunto de biyecciones es al menos el de \( [0,1] \setminus \Bbb Q \), que es \( 2^{\aleph_0} \). Combinando esto con lo que puse antes se ve que el cardinal es exactamente \( 2^{\aleph_0} \). Además, lo que haces es establecer una inyección del conjunto de todas las particiones de \( \Bbb N \) en dos conjuntos infinitos en el conjunto de biyecciones de \( \Bbb N \), donde asignas a cada partición la biyección que permuta los dos conjuntos de la partición preservando el orden en cada una.

El argumento diagonal no funciona aquí, al menos de forma sencilla. El problema es que nadie te asegura que el elemento diagonal sea una biyección (o un elemento con infinitos ceros e infinitos unos).

[jbgg]

Esta muy bien la demostración. Fíjate que en realidad pruebas que el cardinal del conjunto de biyecciones es al menos el de \( [0,1] \setminus \Bbb Q \), que es \( 2^{\aleph_0} \). Combinando esto con lo que puse antes se ve que el cardinal es exactamente \( 2^{\aleph_0} \). [...]

Bueno, yo solamente he dado lo que dice en la pregunta, viendo que en algún caso la respuesta no es afirmativa, esto es, el conjunto de las biyecciones entre dos numerables no es en general numerable.

Lo que comentas es cierto con la hipótesis del continuo, lo cual no sabemos si la persona que lo pregunta la está suponiendo o no.

[geómetracat]

Bueno, yo solamente he dado lo que dice en la pregunta, viendo que en algún caso la respuesta no es afirmativa, el conjunto de las biyecciones entre dos numerables no es en general numerable.

Si está muy bien, solamente lo decía porque lo tienes "gratis" con tu demostración.

Lo que comentas es cierto con la hipótesis del continuo, lo cual no sabemos si la persona que lo pregunta la está suponiendo o no.

No, que el cardinal es \( 2^{\aleph_0} \) es verdad en ZFC. Si asumes la hipótesis del continuo, lo que tienes además es que \( 2^{\aleph_0} = \aleph_1 \).

[jbgg]

No, que el cardinal es \( 2^{\aleph_0} \) es verdad en ZFC. Si asumes la hipótesis del continuo, lo que tienes además es que \( 2^{\aleph_0} = \aleph_1 \).

Llevas razón, me he colado.