¿Por qué el número cardinal del conjunto de la potencia $2^n$ ?

Question

¿Por qué el número total de subconjuntos de $n$ elementos iguales $2^n$ ?

Me enseñaron que es porque cada elemento tiene dos opciones, hacer un conjunto o no. Por lo tanto, dando $2×2×2\ldots$ subconjuntos.

Pero no entendí cómo funciona para dar este resultado.

Answer 1

Prueba por inducción.

Cuando $n=0$ entonces $\mathcal P(\emptyset)=\{\emptyset\}$ así que $|\mathcal P(\emptyset)|=1.$

Ahora, supongamos que es cierto para todos $|S|=n,$ y asumir $|T|=n+1.$

Elige un elemento $x\in T.$ Entonces dejemos que $T_0=T\setminus \{x\}.$ Tenemos $|T_0|=n.$

Entonces, para cada $M\subseteq T_0$ hay exactamente dos subconjuntos de $T,$ $M$ y $M\cup\{x\}.$

Así que $$|\mathcal P(T)|=2|\mathcal P(T_0)|=2\cdot 2^{n}=2^{n+1}.$$

---

Podríamos demostrarlo con un poco más de rigor definiendo una función $f:\mathcal P(T)\to \mathcal P(T_0)\times \{1,2\}$ y demostrar que es una biyección.

Definimos, para $M\subseteq T,$ $$f_2(M)=\begin{cases}1&x\in M\\2&x\notin M \end{cases}$$

Entonces $f(M)=(M\cap T_0,f_2(M)).$

Demostrar que esto es una biyección es un trabajo tedioso, pero directo.

Answer 2

Supongamos que se numeran los elementos $1,2,\cdots,n$ . Entonces, cada elemento del conjunto de potencias puede ser representado por una cadena binaria de longitud $n$ : A saber, un subconjunto de los $n$ elementos, digamos $S$ se denotará por el $n$ -cadena de bits $b(S)=(b_1(S),b_2(S),\cdots,b_n(S))$ , donde $b_i(S)=1$ si el $i$ -Los elementos que pertenecen a $S$ o $b_i(S)=0$ en caso contrario. Obsérvese que cada subconjunto corresponde a un único $n$ -y viceversa. Ahora el número de $n$ -cadenas de bits es $2^n$ . Por lo tanto, el número de subconjuntos también es $2^n$ .