Bienvenida

Bienvenidos a mi blog. Aqui les mostrare todo lo que aprendo en mis clases con el profesor Cantoral, y una que otra aportacion mia.

miércoles, 29 de septiembre de 2010

Número de subconjuntos de un conjunto.

En una de las primeras clases que nos impartió el maestro Cantoral, a mi y a mis compañeros, nos enseño como determinar el numero de subconjuntos que conforman un conjunto, concluyendo que el número de subconjunto que conforman un conjunto se define en este termino: 2ⁿ, donde n es el número de elementos del conjunto, lo cual no se demostración en clase y por eso nos lo dejo a nosotros (yo y mis compañeros) como tarea y eh aquí la demostración.

Sea S un conjunto finito con n elmentos (|S|=n) entonces |P(S)|=2ⁿ

DEMOSTRACIÓN:

Caso n=0

Sea S el conjunto vacío, entonces |S|=0 y P(S)={φ}

Supongamos cierto si |S|=m y m es menor o igual que n, entonces |P(S)|=$2^{m}$

Sea |S' |=n+1

S' = {$a_0,a_1,...,a_{n-1},a_n$}

Por tanto

S' = {$a_0,a_1,...,a_{n-1}$} U {$a_n$}

Sea S = {$a_0,a_1,...,a_{n-1}$}

entonces

S' = S $\bigcup$ {$a^n$}

Tenemos que

P(S' ) = P(S $\bigcup${$a_n$}) = P(S) $\bigcup${P' $\bigcup${$a_n$} / P' $\in$P(S)}

Dado que ambos conjuntos son disjuntos tenemos que:

|P(S' )| = |P(S) $\bigcup$ {P' $\bigcup$ {$a_n$} / P' $\in$P(S)}| = |P(S)| + |{P' $\bigcup$ {$a_n$} / P'$\in$P(S)}| =$2^n$+$2^n$ =$2^{n+1}$