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

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

17 Julio, 2024, 05:42 pm
Respuesta #10

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:
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| \).
:aplauso:   :aplauso:
Entiendo que si \( |X|=|X\times\{0,1\}| \) es porque hay una biyección entre \( X \) y \( X\times \{0,1\} \) y, por tanto, una biyección \( \delta \) entre \( X \) y \( (X\times\{0\})\cup (X\times \{1\}) \); ¿bastaría entonces tomar \( A=\delta^{-1}(X\times\{0\}) \) y \( B=\delta^{-1}(X\times\{1\}) \)? Por otra parte ¿cuál es el problema que intentas eludir al excluir la definición de \( \Phi(\emptyset) \)? ¿Es porque no existe ninguna aplicación sobreyectiva del tipo \( g_{\emptyset}:A\longrightarrow \emptyset \)?
Saludos

17 Julio, 2024, 06:16 pm
Respuesta #11

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:
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.
Sí, entiendo, pero que \( 2^{card(X)}\leq card(X)^{card(X)} \) ¿no se deduce directamente de que es posible dar una inyección de \( \{0,1\}^X \) a \(  X^X \)?
Citar
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.
Tienes razón, ese paso no es nada intuitivo; había recurrido a un resultado teórico. Me parece bastante claro cómo lo ha detallado geómetracat: \( card(X)\leq 2^{card(X)}\Longrightarrow card\left(X^X\right)=card(X)^{card(X)}\leq \left(2^{card(X)}\right)^{card(X)}=2^{card(X)\cdot card(X)}=2^{card(X)} \)
Por cierto, he visto que en el caso \( X=\mathbb{R} \), una inyección que se define para probar que
\( card\left(\mathbb{R}^{\mathbb{R}}\right)\leq 2^{card(\mathbb{R})} \) es la siguiente:
\( \begin{array}[t]{rcl}\mathbb{R}^{\mathbb{R}}&\longrightarrow &\{0,1\}^{\mathbb{R}}\\f&\mapsto &\tilde{f}\end{array} \) con \( \begin{array}[t]{rcl}\tilde{f}:\mathbb{R}&\longrightarrow &\{0,1\}\\x&\mapsto & \tilde{f}(x)=\left\{\begin{array}{lr}0&\mbox{ si }x\notin \mathbb{N}\\f(x)(x)&\mbox{ si }x\in \mathbb{N}\end{array}\right.  \end{array} \) donde se interpreta el número real \( f(x) \) como una aplicación de \( \mathbb{N} \) en \( \{0,1\} \) debido a que existe una biyección entre \( \mathbb{R} \) y \( \{0,1\}^{\mathbb{N}} \). ¿Cómo se podría dar una inyección de \( X^X \) a \( \{0,1\}^X \) en el caso general con \( X \) de cardinalidad infinita?
Citar
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 \).
Sí, llevas razón, veo el problema y que, por tanto, la aplicación \( \varphi \) así definida no es válida. Gracias
Saludos

17 Julio, 2024, 10:23 pm
Respuesta #12

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Entiendo que si \( |X|=|X\times\{0,1\}| \) es porque hay una biyección entre \( X \) y \( X\times \{0,1\} \) y, por tanto, una biyección \( \delta \) entre \( X \) y \( (X\times\{0\})\cup (X\times \{1\}) \); ¿bastaría entonces tomar \( A=\delta^{-1}(X\times\{0\}) \) y \( B=\delta^{-1}(X\times\{1\}) \)?

Exacto.

Por otra parte ¿cuál es el problema que intentas eludir al excluir la definición de \( \Phi(\emptyset) \)? ¿Es porque no existe ninguna aplicación sobreyectiva del tipo \( g_{\emptyset}:A\longrightarrow \emptyset \)?

Claro. Si \( f: A\longrightarrow C \) es una aplicación cualquiera (no hace falta que sea suprayectiva) y \( A \) no es vacío (en nuestro caso es un conjunto infinito) basta tomar \( a\in A \), lo que nos da que \( f(a)\in C \), luego \( C \) no puede ser vacío.

La única aplicación con imagen en el conjunto vacío es \( \emptyset: \emptyset\longrightarrow \emptyset \), que es, de hecho, biyectiva.

17 Julio, 2024, 11:11 pm
Respuesta #13

Luis Fuentes

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

Sí, entiendo, pero que \( 2^{card(X)}\leq card(X)^{card(X)} \) ¿no se deduce directamente de que es posible dar una inyección de \( \{0,1\}^X \) a \(  X^X \)?

Si, claro. Esa desigualdad es inmediata.

Ahora en esta cadena que haces de desigualdades:

Citar
Por cierto, he visto que en el caso \( X=\mathbb{R} \), una inyección que se define para probar que
\( card\left(\mathbb{R}^{\mathbb{R}}\right)\leq 2^{card(\mathbb{R})} \) es la siguiente:
\( \begin{array}[t]{rcl}\mathbb{R}^{\mathbb{R}}&\longrightarrow &\{0,1\}^{\mathbb{R}}\\f&\mapsto &\tilde{f}\end{array} \) con \( \begin{array}[t]{rcl}\tilde{f}:\mathbb{R}&\longrightarrow &\{0,1\}\\x&\mapsto & \tilde{f}(x)=\left\{\begin{array}{lr}0&\mbox{ si }x\notin \mathbb{N}\\f(x)(x)&\mbox{ si }x\in \mathbb{N}\end{array}\right.  \end{array} \) donde se interpreta el número real \( f(x) \) como una aplicación de \( \mathbb{N} \) en \( \{0,1\} \) debido a que existe una biyección entre \( \mathbb{R} \) y \( \{0,1\}^{\mathbb{N}} \).

Pues ahora mismo no acabo de ver porque esa aplicación es inyectiva. ¿Si dos funciones \( f,g:\Bbb R\to \Bbb R \) actúan igual sobres los naturales no se tendría \( \bar f=\bar g \)?.

Citar
¿Cómo se podría dar una inyección de \( X^X \) a \( \{0,1\}^X \) en el caso general con \( X \) de cardinalidad infinita?

No se cuán fácil puede ser dar una inyección directamente; el camino que yo seguí consistía en encadenar otras desigualdades e igualdades.

Saludos.

P.D. Aquí se prueban los resultados que uso:

https://math-garden.com/wp-content/uploads/2021/01/math_garden_card_cardinal_arithmetic.pdf

18 Julio, 2024, 12:58 am
Respuesta #14

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
¿Cómo se podría dar una inyección de \( X^X \) a \( \{0,1\}^X \) en el caso general con \( X \) de cardinalidad infinita?

Fija \( h: X\times X\longrightarrow X \) biyectiva. Entonces, si \( f\in X^X \), tienes que \( f: X\longrightarrow X \), luego \( f\subset X\times X \), luego \( h[f]\subset X \). Define \( F: X^X\longrightarrow \{0,1\}^X \) mediante \( F(f) = \chi_{h[f]} \), donde \( \chi \) indica la función característica.


18 Julio, 2024, 11:23 am
Respuesta #15

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:


Ahora en esta cadena que haces de desigualdades:

Citar
Por cierto, he visto que en el caso \( X=\mathbb{R} \), una inyección que se define para probar que
\( card\left(\mathbb{R}^{\mathbb{R}}\right)\leq 2^{card(\mathbb{R})} \) es la siguiente:
\( \begin{array}[t]{rcl}\mathbb{R}^{\mathbb{R}}&\longrightarrow &\{0,1\}^{\mathbb{R}}\\f&\mapsto &\tilde{f}\end{array} \) con \( \begin{array}[t]{rcl}\tilde{f}:\mathbb{R}&\longrightarrow &\{0,1\}\\x&\mapsto & \tilde{f}(x)=\left\{\begin{array}{lr}0&\mbox{ si }x\notin \mathbb{N}\\f(x)(x)&\mbox{ si }x\in \mathbb{N}\end{array}\right.  \end{array} \) donde se interpreta el número real \( f(x) \) como una aplicación de \( \mathbb{N} \) en \( \{0,1\} \) debido a que existe una biyección entre \( \mathbb{R} \) y \( \{0,1\}^{\mathbb{N}} \).

Pues ahora mismo no acabo de ver porque esa aplicación es inyectiva. ¿Si dos funciones \( f,g:\Bbb R\to \Bbb R \) actúan igual sobres los naturales no se tendría \( \bar f=\bar g \)?.
Lo que sigue en rojo no prueba la inyectividad sino que verifica una de las condiciones para ser aplicación. Gracias Luis Fuentes por la corrección

Si es \( \tilde{f}\neq \tilde{g}\Longrightarrow \exists\,x\in\mathbb{R} \) tal que \( \tilde{f}(x)\neq \tilde{g}(x) \); ha de ser necesariamente \( x\in\mathbb{N} \) ya que si \( x\notin \mathbb{N} \) entonces \( \tilde{f}(x)=0=\tilde{g}(x) \). Así pues, \( \tilde{f}(x)\neq \tilde{g}(x)\Longrightarrow f(x)(x)\neq g(x)(x)\Longrightarrow f(x)\neq g(x) \) (recordemos que \( f(x),g(x) \) se interpretan como elementos de \( \{0,1\}^{\mathbb{N}} \)), de donde \( f\neq g \) y se tiene ña inyectividad.


Citar
Citar
¿Cómo se podría dar una inyección de \( X^X \) a \( \{0,1\}^X \) en el caso general con \( X \) de cardinalidad infinita?

No se cuán fácil puede ser dar una inyección directamente; el camino que yo seguí consistía en encadenar otras desigualdades e igualdades.
Creo haber entendido la inyección que ha propuesto Carlos Ivorra. Gracias por el enlace.
Editado
Saludos

18 Julio, 2024, 11:28 am
Respuesta #16

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:
¿Cómo se podría dar una inyección de \( X^X \) a \( \{0,1\}^X \) en el caso general con \( X \) de cardinalidad infinita?

Fija \( h: X\times X\longrightarrow X \) biyectiva. Entonces, si \( f\in X^X \), tienes que \( f: X\longrightarrow X \), luego \( f\subset X\times X \), luego \( h[f]\subset X \). Define \( F: X^X\longrightarrow \{0,1\}^X \) mediante \( F(f) = \chi_{h[f]} \), donde \( \chi \) indica la función característica.
Entendido.  :)   Sé que \( card(X\times X)=card^2(X)=card(X) \). ¿Algún detalle de cómo fijar \( h \)? Gracias
Saludos

18 Julio, 2024, 11:30 am
Respuesta #17

Luis Fuentes

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

Si es \( \tilde{f}\neq \tilde{g}\Longrightarrow \exists\,x\in\mathbb{R} \) tal que \( \tilde{f}(x)\neq \tilde{g}(x) \); ha de ser necesariamente \( x\in\mathbb{N} \) ya que si \( x\notin \mathbb{N} \) entonces \( \tilde{f}(x)=0=\tilde{g}(x) \). Así pues, \( \tilde{f}(x)\neq \tilde{g}(x)\Longrightarrow f(x)(x)\neq g(x)(x)\Longrightarrow f(x)\neq g(x) \) (recordemos que \( f(x),g(x) \) se interpretan como elementos de \( \{0,1\}^{\mathbb{N}} \)), de donde \( f\neq g \) y se tiene la inyectividad.

Pero la inyectividad sería probar que:

\( f\neq g\quad \Rightarrow{}\quad \tilde f\neq \tilde g \)

ó en todo caso el contrarecíproco:

\( \tilde f=\tilde g\quad \Rightarrow{}\quad f=g \)

Pero tú lo que has probado ahí es que:

\( \tilde f\neq \tilde g\quad \Rightarrow{}\quad f\neq g \)

Lo cuál tiene que ser cierto para cualquier función (en otro caso no sería función); pero no dice nada sobre la inyectividad.

Saludos.

18 Julio, 2024, 11:33 am
Respuesta #18

Luis Fuentes

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

Entendido.  :)   Sé que \( card(X\times X)=card^2(X)=card(X) \). ¿Algún detalle de cómo fijar \( h \)? Gracias
Saludos

Pues a falta de que responda Carlos, que sabe mucho más del asunto, yo diría que en general no se puede explicitar \( h \), ya que la existencia de esa biyección creo que se basa decisivamente en el axioma de elección.

Saludos.

18 Julio, 2024, 11:55 am
Respuesta #19

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:

Pero la inyectividad sería probar que:

\( f\neq g\quad \Rightarrow{}\quad \tilde f\neq \tilde g \)

ó en todo caso el contrarecíproco:

\( \tilde f=\tilde g\quad \Rightarrow{}\quad f=g \)

Pero tú lo que has probado ahí es que:

\( \tilde f\neq \tilde g\quad \Rightarrow{}\quad f\neq g \)

Lo cuál tiene que ser cierto para cualquier función (en otro caso no sería función); pero no dice nada sobre la inyectividad.
Llevas razón; voy a analizarlo mejor.  ;D
Saludos