Autor Tema: Equipotencia entre conjuntos

0 Usuarios y 1 Visitante están viendo este tema.

12 Noviembre, 2018, 05:24 am
Leído 1790 veces

PhysicsKhara

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 5
  • Karma: +0/-0
  • Sexo: Masculino
Buenas, lo que pasa es que no sé como resolver este problema.

Debo demostrar que el conjunto de todas las funciones con dominio A y rango subconjunto de 2 (\(  2^A  \) ) tiene el mismo cardinal que el conjunto de partes de A ( \(  P(A)     \) ) .


          \(   \left |{2^A}\right |=  \left|{P(A)}\right|     \)


¿Alguien me puede ayudar, por favor?
¡Muchas gracias!

12 Noviembre, 2018, 05:49 am
Respuesta #1

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,415
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola PhysicsKhara, bienvenido al foro!!

Recordá leer y seguir las reglas del mismo así como el tutorial del \( \mathrm\LaTeX \) para escribir las fórmulas matemáticas correctamente.



Con respecto al ejercicio:

Debo demostrar que el conjunto de todas las funciones con dominio A y rango subconjunto de 2 (\(  2^A  \) ) tiene el mismo cardinal que el conjunto de partes de A ( \(  P(A)     \) ) .


          \(   \left |{2^A}\right |=  \left|{P(A)}\right|     \)

Pienso que del lado izquierdo debería decir \( 2^{|A|} \). Quizás sea algo mío pero nunca había visto algo como por ejemplo \( A=\{0,1\} \), \( |2^{\{0,1\}}| \). ¿Qué representa un número elevado a un conjunto sino decir que \( 2^{|\{0,1\}|}=2^2=4 \)?

Una vez aclarado esto, podría servirte de ayuda este enlace sobre Álgebras de Boole que reúne más o menos la prueba que buscás: Probar: En un Álgebra de Boole se verifica que \( \lvert A\rvert=2^n \).

Dentro de esa misma pregunta podés encontrarte con De donde sale la fórmula 2^n para determinar el número de subconjuntos..., muy interesante.



De todas maneras, no creo esos enlaces respondan concretamente tu duda. Yo lo haría por inducción, siendo el primer paso (caso base) tomar \[A=\varnothing\implies\begin{cases}|A|=0\\P(A)=\{\varnothing\}\implies|P(A)|=1\end{cases}\implies2^{|A|}\overset?=|P(A)|\implies2^0\overset?=1\implies1=1.\] Para el paso inductivo, será tomar \( A\neq\emptyset \) y \( |A|=n \) ???.

Esperá la ayuda de alguien más.

Saludos

P.D. Este tipo de preguntas me encantan, ¡gracias!

EDIT. Lo encontré en el foro de "guiris" ;). Prove that the power set of an \( n \)-element set contains \( 2^n \) elements. Cualquier duda preguntanos y te ayudamos.

12 Noviembre, 2018, 07:29 am
Respuesta #2

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 49,877
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Pienso que del lado izquierdo debería decir \( 2^{|A|} \). Quizás sea algo mío pero nunca había visto algo como por ejemplo \( A=\{0,1\} \), \( |2^{\{0,1\}}| \). ¿Qué representa un número elevado a un conjunto sino decir que \( 2^{|\{0,1\}|}=2^2=4 \)?

En general la notación \( A^B \) con \( A,B \) conjuntos significa el conjunto de aplicaciones de \( B \) en \( A \). En ese contexto "2" se refiere al conjunto \( \{1,2\} \).

El ejercicio entonces pide construir una biyección entre el conjunto \( X \) de aplicaciones \( A\to \{0,1\} \) y el conjunto de partes \( P(A) \).

Basta definir:

\( \phi:X\to P(A) \)

de la siguiente forma: dada \( f:A\to \{0,1\} \), \( \phi(f)=f^{-1}(\{1\}) \).

La inversa lleva \( B\subset A \) en la función:

\( f:A\to\{0,1\},\quad f(x)=\begin{cases} 1 & \text{si}& x\in B\\0 & \text{si}& x\not\in B\end{cases} \)

Saludos.

12 Noviembre, 2018, 10:54 pm
Respuesta #3

PhysicsKhara

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 5
  • Karma: +0/-0
  • Sexo: Masculino
Muchas gracias manooooh y Luis Fuentes, ahora entiendo.

manooooh, me refería el conjunto de todas las funciones con dominio A y rango subconjunto de 2.

¿manooooh, disculpa, he infringido alguna regla del foro? Perdón  ??? .

12 Noviembre, 2018, 11:06 pm
Respuesta #4

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,415
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

manooooh, me refería el conjunto de todas las funciones con dominio A y rango subconjunto de 2.

Te pido perdón. Me confié y fui directamente a ver \( |2^A|=|P(A)| \) sin mirar el texto anterior. Hacele caso a Luis.

¿manooooh, disculpa, he infringido alguna regla del foro? Perdón  ??? .

¡No infringiste nada! Sólo te comentaba que tenemos una sección de reglas y una sección de cómo utilizar \( \mathrm\LaTeX \) :).

Saludos

12 Noviembre, 2018, 11:30 pm
Respuesta #5

PhysicsKhara

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 5
  • Karma: +0/-0
  • Sexo: Masculino
Está bien, manooooh. ¡Muchas gracias!  ;)

14 Junio, 2021, 05:17 am
Respuesta #6

Dark

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 387
  • País: 00
  • Karma: +0/-0
  • Sexo: Masculino

El ejercicio entonces pide construir una biyección entre el conjunto \( X \) de aplicaciones \( A\to \{0,1\} \) y el conjunto de partes \( P(A) \).

Basta definir:

\( \phi:X\to P(A) \)

de la siguiente forma: dada \( f:A\to \{0,1\} \), \( \phi(f)=f^{-1}(\{1\}) \).

La inversa lleva \( B\subset A \) en la función:

\( f:A\to\{0,1\},\quad f(x)=\begin{cases} 1 & \text{si}& x\in B\\0 & \text{si}& x\not\in B\end{cases} \)

Saludos.

Es correcto el siguiente argumento para probar la inyectividad de esa función:

\begin{align*}
F(f)=F(g)&\Longrightarrow f^{-1}(0)=g^{-1}(0)\\ &\Longrightarrow (f^{-1}(0))^{-1}=(g^{-1}(0))^{-1}\\ &\Longrightarrow (f^{-1})^{-1}(0)=(g^{-1})^{-1}(0)\\ &\Longrightarrow f(0)=g(0)\qquad \mbox{me queda la duda, si de aquí puedo concluir que}\\ &\Longrightarrow f=g
\end{align*}

14 Junio, 2021, 11:03 am
Respuesta #7

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 49,877
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Citar
Basta definir:

\( \phi:X\to P(A) \)

de la siguiente forma: dada \( f:A\to \{0,1\} \), \( \phi(f)=f^{-1}(\{1\}) \).

La inversa lleva \( B\subset A \) en la función:

\( f:A\to\{0,1\},\quad f(x)=\begin{cases} 1 & \text{si}& x\in B\\0 & \text{si}& x\not\in B\end{cases} \)

Saludos.

Es correcto el siguiente argumento para probar la inyectividad de esa función:

\begin{align*}
F(f)=F(g)&\Longrightarrow f^{-1}(0)=g^{-1}(0)\\ &\Longrightarrow (f^{-1}(0))^{-1}=(g^{-1}(0))^{-1}\\ &\Longrightarrow (f^{-1})^{-1}(0)=(g^{-1})^{-1}(0)\\ &\Longrightarrow f(0)=g(0)\qquad \mbox{me queda la duda, si de aquí puedo concluir que}\\ &\Longrightarrow f=g
\end{align*}

No está bien.

1) \( F(f)=F(g)\quad\Longrightarrow\quad f^{-1}(0)=g^{-1}(0) \) es correcto; aunque sería más inmediato decir que:  \( F(f)=F(g)\quad\Longrightarrow\quad f^{-1}(\{1\})=g^{-1}(\{1\}) \) (porque es la definición directa de la aplicación).

2) Pero \( (f^{-1}(0))^{-1} \) no tiene sentido. \( f^{-1}(0) \) es un subconjunto de \( A \). Su "inverso" no significa nada.

3) Suponiendo que hubieses probado que \( f(0)=g(0) \) y que eso tuviese sentido (0 debería de ser un elemento de A), no probaría que \( f=g \). Sólo que coinciden en la imagen de un elemento.

Saludos.

14 Junio, 2021, 03:33 pm
Respuesta #8

Dark

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 387
  • País: 00
  • Karma: +0/-0
  • Sexo: Masculino
Solo copié y pegué de mi trabajo,  no corregí la notación, solo que yo había tomado la función de esta manera:
$$f(x)=\begin{cases}{0}&\text{si}& x\in B\\1& \text{si}& x\notin B\end{cases}$$
Si este es el caso, si estaría bien?

14 Junio, 2021, 04:25 pm
Respuesta #9

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 49,877
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Solo copié y pegué de mi trabajo,  no corregí la notación, solo que yo había tomado la función de esta manera:
$$f(x)=\begin{cases}{0}&\text{si}& x\in B\\1& \text{si}& x\notin B\end{cases}$$
Si este es el caso, si estaría bien?

Las otras críticas siguen en pie:

2) Pero \( (f^{-1}(0))^{-1} \) no tiene sentido. \( f^{-1}(0) \) es un subconjunto de \( A \). Su "inverso" no significa nada.

3) Suponiendo que hubieses probado que \( f(0)=g(0) \) y que eso tuviese sentido (0 debería de ser un elemento de A), no probaría que \( f=g \). Sólo que coinciden en la imagen de un elemento.

Saludos.