Autor Tema: Equipotencia entre el conjunto de las funciones sobreyectivas y el potencia

0 Usuarios y 2 Visitantes están viendo este tema.

15 Julio, 2024, 09:18 pm
Leído 3152 veces

Fernando Dominguez

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 7
  • País: mx
  • Karma: +0/-0
Buenas, he estado intentando resolver un problema de uno de mis exámenes y no he podido encontrar la manera. El problema es el siguiente:
"Sea \( X \) un conjunto infinito. Demuestre que \( \{f\in X^X:\text{f es sobreyectiva}\} \) es equipotente con \( \mathcal{P}(X) \)", donde \( X^X \) es el conjunto de todas las funciones \( f:X\to X \).

Mi idea es definir un conjunto \( F=\{(f,A)\in T\times \mathcal{P}(X): \dots \} \), donde \( T \) es el conjunto de las funciones sobreyectivas, pero no encuentro la regla de correspondencia para que sea biyectiva. ¿Me podrían ayudar? y, si no es molestia, ¿podrían darme consejos para resolver este tipo de demostraciones?, gracias de antemano.

16 Julio, 2024, 10:05 am
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

Buenas, he estado intentando resolver un problema de uno de mis exámenes y no he podido encontrar la manera. El problema es el siguiente:
"Sea \( X \) un conjunto infinito. Demuestre que \( \{f\in X^X:\text{f es sobreyectiva}\} \) es equipotente con \( \mathcal{P}(X) \)", donde \( X^X \) es el conjunto de todas las funciones \( f:X\to X \).

Mi idea es definir un conjunto \( F=\{(f,A)\in T\times \mathcal{P}(X): \dots \} \), donde \( T \) es el conjunto de las funciones sobreyectivas, pero no encuentro la regla de correspondencia para que sea biyectiva. ¿Me podrían ayudar? y, si no es molestia, ¿podrían darme consejos para resolver este tipo de demostraciones?, gracias de antemano.

Pues no se muy bien que resultados previos puedes usar sobre aritmética de cardinales. En todo lo que voy a decir se supone el axioma de elección.

En primer lugar en general se tiene que si  \( X \) es infinito:

\( card(X^X)\leq 2^{card(X)\cdot card(X)})=2^{card(X)}=card(\mathcal{P}(X)) \)

Por tanto:

\(  card(F)\leq card(X^X)\leq card(\mathcal{P}(X)) \)   (*)

Por otra parte vamos a definir una aplicación inyectiva  \( \mathcal{P}(X) \) en  \( F \). Para ello primero notamos que por ser \( X \) infinito existen biyecciones:

\( g:X\to X\times \{0,1\} \)
\( h:X\to X\sqcup \{0,1\} \)

Dado \( A\subset Y \) definimos \( f'_A:X\times \{0,1\}\to X\sqcup \{0,1\}\ \) como:

\( \color{red}f'_A\color{black}(x,t)=\begin{cases}{h(x)}&\text{si}& t=0\\0 & \text{si}& \color{red} t=1\text{ y }\color{black}x\not\in A\\1 & \text{si}& \color{red}t=1\text{ y }\color{black}x\in A\end{cases} \)

Comprueba que \( \color{red}f'_A\color{black}(x,t) \) es sobreyectiva.

Y después componiendo con biyecciones \( f_A:X\to X \) como \( f_A=h^{-1}\circ f'_A\circ g \) verifica que \( A\to f_A \) es inyectiva.

De ahí:

\( card(\mathcal{P}(X))\leq card(F)  \)  (*)

y junto con (*) tienes la equipotencia.

No se si hay una forma más directa de hacerlo, pero no se me acaba de ocurrir.

Saludos.

CORREGIDO

16 Julio, 2024, 10:21 am
Respuesta #2

ani_pascual

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,223
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
  • שמע ישראל יהוה אלהינו יהוה אחד
    • Kepler_Ck
Hola:
...
En primer lugar en general se tiene que si  \( X \) es infinito:

\( card(X^X)\leq 2^{card(X)\cdot card(X)})=2^{card(X)}=card(\mathcal{P}(X)) \)
No entiendo bien cómo eso prueba lo que pide Fernando Dominguez ¿Podrías detallarlo un poco más? Gracias.
A mí solo se me ocurre probar la equipotencia  entre \( {\cal P}(X) \) y \(  \{0,1\}^X \); basta con considerar la biyección
\( \begin{array}{rcl}{\cal P}(X):&\stackrel{\varphi}{\longrightarrow}&\{0,1\}^X\\A&\longrightarrow&\varphi (A)=\kappa_A\end{array} \) donde
\( \begin{array}{rcl}\kappa_A:X&\longrightarrow&\{0,1\}\\x&\longrightarrow&\kappa_A(x)=\left\{\begin{array}{lr}0&x\notin A\\1&x\in A\end{array}\right.\end{array} \) es la función característica de \( A \), pero no encuentro una biyección entre \( \{0,1\}^X \) y \( \{f\in X^X\,|\,f \, \mbox{ sobreyectiva }\} \)
Saludos

16 Julio, 2024, 10:49 am
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

Hola:
...
En primer lugar en general se tiene que si  \( X \) es infinito:

\( card(X^X)\leq 2^{card(X)\cdot card(X)})=2^{card(X)}=card(\mathcal{P}(X)) \)
No entiendo bien cómo eso prueba lo que pide Fernando Dominguez ¿Podrías detallarlo un poco más? Gracias.

No había terminado; eso era la primera parte.

Saludos.

16 Julio, 2024, 09:32 pm
Respuesta #4

Fernando Dominguez

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 7
  • País: mx
  • Karma: +0/-0
Hola, gracias por tu respuesta. Solo tengo una duda

...
En primer lugar en general se tiene que si  \( X \) es infinito:

\( card(X^X)\leq 2^{card(X)\cdot card(X)})=2^{card(X)}=card(\mathcal{P}(X)) \)

Por tanto:

\(  card(F)\leq card(X^X)\leq card(\mathcal{P}(X)) \)   (*)

...

¿Por qué \( 2^{card(X)\cdot card(X)})=2^{card(X)} \)? Entiendo que es porque \( X \) es infinito, pero no sé como justificar que eso es cierto ¿se cumple en general para cualquier conjunto infinito?. Gracias por tu tiempo.

16 Julio, 2024, 09:48 pm
Respuesta #5

ani_pascual

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,223
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
  • שמע ישראל יהוה אלהינו יהוה אחד
    • Kepler_Ck
Hola:
...
¿Por qué \( 2^{card(X)\cdot card(X)})=2^{card(X)} \)? Entiendo que es porque \( X \) es infinito, pero no sé como justificar que eso es cierto ¿se cumple en general para cualquier conjunto infinito?. Gracias por tu tiempo.
Diría que es \( card(X^X)=card(X)^{card(X)}=2^{card (X)}=card ({\cal P}(X)) \), pero a ver qué dice Luis Fuentes  ;D
Saludos

17 Julio, 2024, 09:57 am
Respuesta #6

geómetracat

  • Moderador Global
  • Mensajes: 4,065
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Diría que es \( card(X^X)=card(X)^{card(X)}=2^{card (X)}=card ({\cal P}(X)) \), pero a ver qué dice Luis Fuentes  ;D
Saludos
Por un lado, \( card(X^X)=card(X)^{card(X)} \), por definición. Por otro lado, \( card(X)\leq 2^{card(X)} \) (por ejemplo, incluyendo cada elemento de \( X \) como la función que asigna \( 1 \) a ese elemento y \( 0 \) al resto).
Esto nos da: \( card(X^X)=card(X)^{card(X)}\leq \left(2^{card(X)}\right)^{card(X)}=2^{card(X)\cdot card(X)} \).

Finalmente, se usa que para cualquier cardinal infinito \( \kappa \) es un teorema que \( \kappa + \kappa = \kappa \cdot \kappa =\kappa \), luego \( card(X)\cdot card(X)=card(X) \).
La ecuación más bonita de las matemáticas: \( d^2=0 \)

17 Julio, 2024, 11:40 am
Respuesta #7

ani_pascual

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,223
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
  • שמע ישראל יהוה אלהינו יהוה אחד
    • Kepler_Ck
Hola:
Por un lado, \( card(X^X)=card(X)^{card(X)} \), por definición. Por otro lado, \( card(X)\leq 2^{card(X)} \) (por ejemplo, incluyendo cada elemento de \( X \) como la función que asigna \( 1 \) a ese elemento y \( 0 \) al resto).
Esto nos da: \( card(X^X)=card(X)^{card(X)}\leq \left(2^{card(X)}\right)^{card(X)}=2^{card(X)\cdot card(X)} \).

Finalmente, se usa que para cualquier cardinal infinito \( \kappa \) es un teorema que \( \kappa + \kappa = \kappa \cdot \kappa =\kappa \), luego \( card(X)\cdot card(X)=card(X) \).
Eso lo entiendo, pero lo que he puesto:
\( card(X^X)=2^{card(X)} \)
me parece también correcto en este caso.
Se tiene que \( 2^{card(X)}=card(\{0,1\}^X)\leq card(X^X)\leq card(\{0,1\}^X)=2^{card(X)} \) luego \( card(X^X)=2^{card(X)}=card({\cal P}(X)) \).
Tengo entendido que, en general, si se acepta la H.C.G., \( \aleph_{\alpha}^{\aleph_{\beta}}=
\left\{\begin{array}{lr}\aleph_{\alpha}& \mbox{ si }\aleph_{\beta}<\aleph_{\alpha}\\\aleph_{\alpha+1}=2^{\aleph_{\alpha}}&\mbox{ si } \aleph_{\beta}\geq \aleph_{\alpha}\end{array}\right. \)
En este caso, \( card(X^X)=card(X)^{card(X)}=2^{card(X)}=card({\cal P}(X)) \) ya que \( card(X)\geq card(X) \).
Lo que se prueba en el ejercicio es que además \( card(F)=card(X^X) \), siendo \( F=\{f\in X^X\,|\,f \mbox{ es sobreyectiva}\}\subset X^X \).
Por cierto, como es \( card(X^X)=card ({\cal P}(X)) \) se tiene que \( card (F)\leq card({\cal P}(X)) \). Así, tal y como sostiene Luis Fuentes, basta con establecer una inyección de \( {\cal P}(X) \) en \( F \); propongo una forma distinta a la propuesta, a ver si la veis correcta, pues tengo alguna duda.

Lo que sigue en rojo es incorrecto. así que mis dudas estaban fundadas   ;D

Sea \( \begin{array}[t]{rcl}\varphi:{\cal P}(X)&\longrightarrow &F\\A&\mapsto & \varphi_A\end{array} \) donde la aplicación \( \varphi_A \) se define como \( \varphi_A=id_X \) si es \( A=X \) y si es \( A\neq X \) entonces\( \begin{array}[t]{rcl}\varphi_A:X&\longrightarrow & X\\x&\mapsto &\varphi_A(x)=\left\{\begin{array}{lr}x&\mbox{ si }x\in A\\y\neq x & \mbox{ si }x\notin A\end{array}\right.\end{array} \)
Es claro que para cada \( A\subset X,\,\varphi_A \) es sobreyectiva; si \( A=X \) \( \varphi_A=id_X \) luego es sobreyectiva y si \( A\neq X \), dado \( x\in X \), si es \( x\in A \) entonces \( \varphi_A(x)=x \) y si es \( x\notin A  \) entonces es \( \varphi_A(y)=x \) donde \( y\neq x \). Así, \( \varphi \) está bien definida; veamos que es inyectiva. Sean  \( A, B\in {\cal P}(X) \) con \( A\neq B \); o bien existe \( a\in A \) tal que \( a\notin B \), o bien existe \( b\in B \) tal que \( b\notin A \); en el primer caso, \( \varphi_A(a)=a\neq \varphi_B(a) \),luego \( \varphi_A\neq \varphi_B \) y en el segundo caso \( \varphi_B(b)=b\neq \varphi_A(b) \) luego \( \varphi_A\neq \varphi_B \);en definitiva, \( \varphi \) es inyectiva

y así
\( card({\cal P}(X))\leq card(F) \) con lo que \( card(F)=card({\cal P}(X)) \).
Editado. Gracias Luis Fuentes por la corrección
Saludos

17 Julio, 2024, 12:33 pm
Respuesta #8

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

Eso lo entiendo, pero lo que he puesto:
\( card(X^X)=2^{card(X)} \)
me parece también correcto en este caso.

Es correcto, claro. Lo que yo había escrito es (en resumen) que \( card(X^X)\leq 2^{card(X)} \). Pero por otra parte dado que \( 2\leq card(X) \), \( 2^{card(X)}\leq card(X)^{card(X)} \) y así se tiene la igualdad.

Ahora en esta cadena que haces de desigualdades:

Citar
Se tiene que \( 2^{card(X)}=card(\{0,1\}^X)\leq \color{red}card(X^X)\leq card(\{0,1\}^X)\color{black}=2^{card(X)} \) luego \( card(X^X)=2^{card(X)}=card({\cal P}(X)) \).

el paso marcado en rojo es correcto, pero lo suficientemente poco intuitivo como para detallar el porqué, que es lo que yo hacía en mi mensaje y ampliaba geómetracat.

Citar
Por cierto, como es \( card(X^X)=card ({\cal P}(X)) \) se tiene que \( card (F)\leq card({\cal P}(X)) \). Así, tal y como sostiene Luis Fuentes, basta con establecer una inyección de \( {\cal P}(X) \) en \( F \); propongo una forma distinta a la propuesta, a ver si la veis correcta, pues tengo alguna duda.
Sea \( \begin{array}[t]{rcl}\varphi:{\cal P}(X)&\longrightarrow &F\\A&\mapsto & \varphi_A\end{array} \) donde la aplicación \( \varphi_A \) se define como \( \varphi_A=id_X \) si es \( A=X \) y si es \( A\neq X \) entonces\( \begin{array}[t]{rcl}\varphi_A:X&\longrightarrow & X\\x&\mapsto &\varphi_A(x)=\left\{\begin{array}{lr}x&\mbox{ si }x\in A\\y\neq x & \mbox{ si }x\notin A\end{array}\right.\end{array} \)
Es claro que para cada \( A\subset X,\,\varphi_A \) es sobreyectiva; si \( A=X \) \( \varphi_A=id_X \) luego es sobreyectiva y si \( A\neq X \), dado \( x\in X \), si es \( x\in A \) entonces \( \varphi_A(x)=x \) y si es \( x\notin A  \) entonces es \( \varphi_A(y)=x \) donde \( y\neq x \). Así, \( \varphi \) está bien definida; veamos que es inyectiva. Sean  \( A, B\in {\cal P}(X) \) con \( A\neq B \); o bien existe \( a\in A \) tal que \( a\notin B \), o bien existe \( b\in B \) tal que \( b\notin A \); en el primer caso, \( \varphi_A(a)=a\neq \varphi_B(a) \),luego \( \varphi_A\neq \varphi_B \) y en el segundo caso \( \varphi_B(b)=b\neq \varphi_A(b) \) luego \( \varphi_A\neq \varphi_B \);en definitiva, \( \varphi \) es inyectiva y así
\( card({\cal P}(X))\leq card(F) \) con lo que \( card(F)=card({\cal P}(X)) \).

Curiosamente esa fue mi primera idea, sobre cada conjunto definir una aplicación dejando fijos sus puntos y moviendo el resto. pero: una precisión y dos problemas.

0) La precisión es que pare que efectivamente  \( \varphi_A \) sea sobreyectiva cuando la defines no basta que tomes  \( \varphi_A(x)=y \) con \( y\neq x \). Por ejemplo si tomas un \( y\in A \) la imagen de \( \varphi_A \) sería sólo el conjunto \( A \).

Para arreglar eso tienes que precisar como escoges esos elementos \( y \). Una opción (la que en principio se me había ocurrido es definir una biyección en el conjunto \( X-A \) que no tenga puntos fijos. 

Pero entonces surgen los problemas:

1) Justificar que dado cualquier conjunto (en nuestro caso \( X-A \)) existe una biyección del mismo sin puntos fijos.

2) Lo más grave: si \( X-A \) está formado por un sólo elemento eso falla. No hay una biyección de un conjunto con un sólo elemento sin puntos fijos. Y de hecho la aplicación que propones es imposible que en ese caso sea sobreyectiva.

Para probar (1) se me ocurrió hacerlo usando una biyección entre \( X \) y \( X\times \{0,1\} \), para conjuntos infinitos eso si.

Para solventar (2) hacer algún requiebro añadiendo elementos auxiliares al conjunto.

Pero al final pensando en eso me salió más barato la aplicación que terminé por proponer.

La clave de la misma en el fondo es que la biyección \( X\Leftrightarrow{}X\times \{0,1\} \) me permite dividir en dos el conjunto original; con una mitad aseguro la sobreyectividad y con la otra juego para distinguir el subconjunto \( A \).

La otra biyección que uso es por comodidad, pero se podría haber evitado fácilmente.

Saludos.

17 Julio, 2024, 12:50 pm
Respuesta #9

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
A mí se me ocurre hacerlo así:

Descompón \( X = A\cup B \) en unión disjunta de conjuntos con \( |A| = |B| = |X| \). Esto es posible precisamente porque \( |X| = |X\times \{0, 1\}| \), pero creo que así la definición de la aplicación inyectiva es más sencilla:

 Fija una biyección \( h: B\longrightarrow X \). Para cada \( C\in \mathcal PX\setminus\{\emptyset\} \), elige una aplicación \( g_C: A\longrightarrow C \) suprayectiva (que existe, porque \( |C|\leq |X|= |A| \)) y define \( \phi(C) = g_C\cup h: X\longrightarrow X \), que es obviamente suprayectiva.

La aplicación \( \phi: \mathcal PX\setminus\{\emptyset\}\longrightarrow F \) es inyectiva, pues \( C = \phi(C)[A] \) permite recuperar \( C \) a partir de su imagen.

Por lo tanto, \( |\mathcal PX| = |\mathcal PX\setminus \{\emptyset\}| \leq |F| \).