Demostrar que un conjunto de tamaño $n$ contiene $2^n$ subconjuntos sin la expansión binomial. (Supongamos que se empieza sólo con conocimientos de teoría de conjuntos). Esto me ha estado molestando por un tiempo así que se agradece la ayuda.
Respuestas
¿Demasiados anuncios?
Considere las tuplas en $2^n$ para representar subconjuntos del conjunto $X$ de $n$ objetos de la siguiente manera.
Interpretar un 1 en el $n$ posición como "número de objeto $n$ está en este conjunto", y un 0 en el $n$ posición como "número de objeto $n$ no está en el conjunto".
Claramente esto forma una biyección entre $\mathcal{P}(X)$ y $2^n$ .
ubergoober
Puntos
41
El conjunto vacío sólo se tiene a sí mismo como subconjunto. Obviamente un conjunto con 1 elemento tiene $2^1$ subconjuntos, él mismo y el conjunto vacío.
Supongamos que un conjunto $A$ con $n$ elementos tiene $2^n$ subconjuntos. Sea $A'=A\cup\{x\}$ (con $x\not\in A$ ). Este nuevo conjunto tiene $n+1$ elementos. Todos los subconjuntos de $A$ también son subconjuntos de $A'$ . Además, cada subconjunto de $A$ con $x$ añadido es también un subconjunto. En otras palabras, para cada $B\subseteq A$ ambos $B\subseteq A'$ y $B\cup\{x\} \subseteq A'$ . Por lo tanto, $A'$ tiene $2\cdot 2^n = 2^{n+1}$ subconjuntos.
Loves Probability
Puntos
21
Jake
Puntos
118
La prueba resulta evidente si se considera un "conjunto" de $n$ dígitos binarios.
El caso trivial es el conjunto vacío (sin bits); hay un conjunto de este tipo que es su propio subconjunto. Con un máximo de un único bit, ese bit puede estar presente o no, por lo que hay dos subconjuntos posibles del conjunto de un bit (el conjunto de ese único bit y el conjunto vacío). Para un número creciente de bits, cada uno de ellos puede estar presente o no. Podemos (y es lo más habitual) identificar estos bits por su "lugar" en el conjunto de todos los bits; $1,2,3... n$ . Podemos entonces (y es lo más común) asignar una potencia de dos basada en cero a cada bit: el bit en el lugar 1 representa $2^0$ el bit en el lugar 2 $2^1$ y así sucesivamente, de manera que el $n$ El segundo bit tiene el valor de la potencia $2^{n-1}$ .
Ahora, cada subconjunto único de bits se puede sumar en términos de sus potencias. Si no hay bits, tenemos el conjunto vacío. Si tenemos un solo bit, no importa cuál, el "valor" del conjunto es el valor de la potencia de dos asignada a ese bit. si tenemos varios bits únicos, sumamos esos valores para producir un valor único. El máximo valor posible del conjunto, es decir, la suma de los valores de cada bit en el conjunto de todos los bits, es $2^0 + 2^1 + 2^2+...+2^{n-1} = 2^n-1$ . Añadiendo el conjunto vacío (valor 0), la cardinalidad del conjunto de todos los conjuntos de $n$ elementos es $2^n$ .
s.b
Puntos
258
Bien, piensa que los elementos de tu conjunto son los números 1,2,...,n.
Para definir un subconjunto tienes que decir qué elementos (si los hay) vas a incluir en tu subconjunto. Ahora, una forma refinada de señalar con el dedo es marcar los elementos elegidos como 1 y marcar los descartados como 0. Así, nuestro problema es contar cuántas secuencias diferentes, de longitud n, de ceros y unos se pueden construir.
Empezando por la izquierda, tienes dos opciones independientes en cada lugar (elige cero o uno) por lo que tienes $2^{n}$ tales secuencias.
