Autor Tema: Numero de subconjuntos de un conjunto con n elementos

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

24 Noviembre, 2022, 02:26 am
Leído 47 veces

zorropardo

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 120
  • País: br
  • Karma: +0/-0
Pruebe por inducción, que in conjunto con $$n$$ elementos  tiene $$2^n$$ subconjuntos.
 Intente de la siguiente forma:
Sea  $$X=\{ x_1, x_2, ..., x_n \} $$ un conjunto con $$n$$ elementos.

Se $$X=\{ x_1 \}$$ entonces los unicos subconjuntos de $$X$$ son: $$\emptyset$$ y $$\{ x_1 \}$$ luego tiene 2 subconjuntos , osea vale para $$n=1.$$

Si $$X=\{ x_1, x_2, ..., x_n \} $$ un conjunto con $$n$$ elementos entonces tiene $$2^n$$ subconjuntos  (H.I.)

Si $$X=\{ x_1, x_2, ..., x_n,x_{n+1} \} $$ un conjunto con $$n+1$$ elementos. Como puedo concluir que tiene $$2^{n+1}$$ elementos  :-\ :-\ :-\




24 Noviembre, 2022, 02:38 am
Respuesta #1

manooooh

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

Pruebe por inducción, que in conjunto con $$n$$ elementos  tiene $$2^n$$ subconjuntos.

Tienes mucha literatura al respecto:

https://www.quora.com/How-do-you-prove-by-induction-a-set-of-n-elements-has-2-n-subsets-discrete-mathematics-math

https://math.stackexchange.com/q/931117

Revisa los enlaces y pregunta las dudas que surjan.

Saludos

24 Noviembre, 2022, 03:17 am
Respuesta #2

delmar

  • Moderador Global
  • Mensajes: 2,987
  • País: pe
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Para n=1 ya lo has demostrado

Para n+1 suponiendo verdadero el teorema para n

Sea \( X=\left\{{x_1,x_2,...,x_n,x_{n+1}}\right\} \) se tiene que los subconjuntos de X los podemos clasificar en tipo "a" subconjuntos constitudos por \( x_{n+1} \) y tipo "b" subconjuntos no constituidos por \( x_{n+1} \). Los subconjuntos tipo "a" resultan de unir el conjunto \( \left\{{x_{n+1}}\right\} \) y un subconjunto del conjunto \( X'=\left\{{x_1,x_2,...,x_n}\right\} \), por tener este último conjunto n elementos, el número de subconjuntos (supuesto verdadero el teorema para n) es \( 2^n \) en consecuencia habrán \( 2^n \) subconjuntos tipo "a". El número de subconjuntos tipo "b"  es el número de subconjuntos de X' y también es igual a \( 2^n \) en consecuencia el total será \( 2^n+2^n \) y de ahí se concluye ....

Saludos

25 Noviembre, 2022, 12:32 pm
Respuesta #3

zorropardo

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 120
  • País: br
  • Karma: +0/-0