11/12/2019, 04:39:03 pm *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: ¡Atención! Hay que poner la matemática con LaTeX, y se hace así (clic aquí):
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Numerabilidad  (Leído 557 veces)
0 Usuarios y 1 Visitante están viendo este tema.
GaToMi
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Chile Chile

Mensajes: 71


Ver Perfil
« : 06/05/2019, 08:43:36 pm »

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).

En línea
Masacroso
Pleno*
*****

Karma: +2/-0
Desconectado Desconectado

España España

Mensajes: 1.666


Ver Perfil
« Respuesta #1 : 07/05/2019, 03:58:32 am »

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 [texx]|X|=n[/texx] entonces el número de biyecciones es [texx]n![/texx].

Si los conjuntos son infinito contables entonces el número de permutaciones de cualquiera de los conjuntos sería [texx]\aleph_0^{\aleph_0}[/texx], ya que por cada posición de una permutación puedes hacer una elección entre infinitos elementos. Y tendríamos que [texx]\aleph_0< 2^{\aleph_0}\le\aleph_0^{\aleph_0}[/texx].
En línea
geómetracat
Moderador Global
Pleno*
*

Karma: +0/-0
Conectado Conectado

Sexo: Masculino
España España

Mensajes: 818



Ver Perfil
« Respuesta #2 : 07/05/2019, 04:36:35 am »

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

Es interesante notar que [texx]\aleph_0^{\aleph_0} = 2^{\aleph_0}[/texx]. En efecto,
[texx]2^{\aleph_0} \leq \aleph_0^{\aleph_0} \leq (2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0 \cdot \aleph_0} = 2^{\aleph_0}[/texx].
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".
En línea

La ecuación más bonita de las matemáticas: [texx]d^2=0[/texx]
jbgg
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 217


Ver Perfil
« Respuesta #3 : 07/05/2019, 07:03:42 am »

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

Una forma de verlo es definiendo una función inyectiva de un conjunto no numerable en [texx]A[/texx]. Por ejemplo la que defino a continuación.

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

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

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

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 217


Ver Perfil
« Respuesta #4 : 07/05/2019, 07:49:25 am »

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 [texx]A=\{\sigma:\mathbb{N}\rightarrow\mathbb{N} : \sigma\text{ es una permutación}\}[/texx] es numerable, entonces numerémoslo como

[texx]A=\{\sigma_1,\ldots,\sigma_k,\ldots\}.[/texx]

Construimos la siguiente matriz

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

y cada entrada la modificamos poniendo el valor [texx]0[/texx] si es par y el valor [texx]1[/texx] si es impar, esto es queda la matriz

[texx]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},[/texx]

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

Si aplicamos el argumento de diagonal de Cantor a la matriz [texx]M[/texx], esto es quedarnos con la diagonal [texx](\phi(\sigma_1(1)),\phi(\sigma_2(2)),\ldots)[/texx] y cambiarle el valor, si es cero lo transformamos en 1 y si es 1 se transforma en 0, esto es consideramos el elemento [texx]v=(\overline{\phi(\sigma_1(1))},\overline{\phi(\sigma_2(2))},\ldots)[/texx], donde [texx]\overline{0} = 1[/texx] y [texx]\overline{1}=0[/texx]. Se verifica que [texx]v[/texx] no puede ser ninguna columna de la matriz [texx]M[/texx], 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 [texx]v[/texx] deba ser una combinación válida (¿quién quita que no sea todo cero y por tanto no debería de estar en [texx]M[/texx]?). 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.


En línea
geómetracat
Moderador Global
Pleno*
*

Karma: +0/-0
Conectado Conectado

Sexo: Masculino
España España

Mensajes: 818



Ver Perfil
« Respuesta #5 : 07/05/2019, 07:58:18 am »

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

Una forma de verlo es definiendo una función inyectiva de un conjunto no numerable en [texx]A[/texx]. Por ejemplo la que defino a continuación.

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

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

Definimos la función [texx]f:[0,1]\setminus\mathbb{Q}\rightarrow A[/texx] por [texx]f(x) = \sigma_x[/texx], donde [texx]\sigma_x[/texx] está dada anteriormente. Se verifica que [texx]f[/texx] es inyectiva y por tanto [texx]A[/texx] es no numerable porque [texx][0,1]\setminus\mathbb{Q}[/texx] 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 [texx][0,1] \setminus \Bbb Q[/texx], que es [texx]2^{\aleph_0}[/texx]. Combinando esto con lo que puse antes se ve que el cardinal es exactamente [texx]2^{\aleph_0}[/texx]. Además, lo que haces es establecer una inyección del conjunto de todas las particiones de [texx]\Bbb N[/texx] en dos conjuntos infinitos en el conjunto de biyecciones de [texx]\Bbb N[/texx], 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).
En línea

La ecuación más bonita de las matemáticas: [texx]d^2=0[/texx]
jbgg
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 217


Ver Perfil
« Respuesta #6 : 07/05/2019, 08:27:38 am »


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


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.
En línea
geómetracat
Moderador Global
Pleno*
*

Karma: +0/-0
Conectado Conectado

Sexo: Masculino
España España

Mensajes: 818



Ver Perfil
« Respuesta #7 : 07/05/2019, 08:31:56 am »

Cita de: jbgg
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.

Cita
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 [texx]2^{\aleph_0}[/texx] es verdad en ZFC. Si asumes la hipótesis del continuo, lo que tienes además es que [texx]2^{\aleph_0} = \aleph_1[/texx].
En línea

La ecuación más bonita de las matemáticas: [texx]d^2=0[/texx]
jbgg
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 217


Ver Perfil
« Respuesta #8 : 07/05/2019, 08:42:13 am »

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

Llevas razón, me he colado.
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!