Demuestra Que Todo Conjunto Finito Con

Demuestra que todo conjunto finito con $n$ elementos tiene $2^n$ subconjuntos.

Sea $S(n) := (\mid A \mid = n \rightarrow \mid \wp (A) \mid = 2^n)$.

Base de inducción:
$n=0$. Si $A=\emptyset, \wp (A) = \{\emptyset\}$ y así, $\mid \wp (A) \mid = 1 = 2^0$.

Paso inductivo:
Supongamos que es verdad $S(n)$.
Si $A=\{a_{1}, \dots, a_{n+1}\}$ tiene $n+1$ elementos, $A=\{a_{1}, \dots, a_{n}\} \cup \{a_{n+1}\}$ y así,

(1)
\begin{align} \wp (A)= \wp (\{a_{1}, \dots, a_{n}\}) \cup \{x\cup \{a_{n+1}\} \mid x \in \wp (\{a_{1}, \dots, a_{n}\})\} \end{align}

Como $\wp(\{a_{1}, \dots, a_{n}\})$ y $\{x\cup \{a_{n+1}\} \mid x \in \wp (\{a_{1}, \dots, a_{n}\})\}$ son ajenos, se tiene que:

(2)
\begin{align} \mid\wp(A)\mid =\mid \wp (\{a_{1}, \dots, a_{n}\}) \cup \{x\cup \{a_{n+1}\} \mid x \in \wp (\{a_{1}, \dots, a_{n}\})\} \mid =\\ \mid \wp (\{a_{1}, \dots, a_{n}\}) \mid + \mid \{x \cup a_{n+1}\} \mid x \in \wp (\{a_{1}, \dots, a_{n}\})\} \mid = 2^n+2^n=2^n 2 = 2^{n+1} \end{align}

$\mid \{x \cup a_{n+1}\} \mid x \in \wp (\{a_{1}, \dots, a_{n}\})\} \mid=2^n$ pues $\mid \{x \cup a_{n+1}\} \mid x \in \wp (\{a_{1}, \dots, a_{n}\})\} \mid = \mid \wp (\{a_{1}, \dots, a_{n}\}) \mid$ ya que $x$ y $\{a_{n+1}\}$ son ajenos al ser $x\subseteq \{a_{1}, \dots, a_{n}\}$.

Es como si tuviéramos un elementos por cada elemento de $\wp(\{a_{1}, \dots, a_{n}\})$ sólo que "pintado" de "color" $a_{n+1}$.
Esto completa la prueba.

Si no se indica lo contrario, el contenido de esta página se ofrece bajo Creative Commons Attribution-ShareAlike 3.0 License