El número total de subconjuntos es$2^n$ para$n$ elementos

Question

En mi probabilidad de libro, se dice que para contar el número total de subconjuntos de n elementos es un proceso de $n$ etapas con la opción binaria de la adición de este elemento del subconjunto o no añadir. Por lo tanto, el número total es de $$2^n$$

Pero, por ejemplo, tenemos 3 elementos, de acuerdo a esta fórmula, hay 2 a la potencia de 3 elementos, a saber, 8, que son $${\emptyset},A,B,C, AB, AC, BC, ABC$$

Sin embargo, tengo un tiempo difícil de imaginar el proceso o N etapas de elección binaria que esta forma muchos de los subconjuntos. ¿Alguien puede explicar/que me ayude a entender? Quiero decir, ABC, si estamos haciendo la elección de Una, poner o no poner, exactamente el subconjunto estamos eligiendo a poner o no? Gracias.

Answer 1

• "¿Incluir un?" es la etapa 1
• "Incluir B?" es la etapa 2
• "Incluir C?" es la etapa 3

Answer 2

Etiqueta de su $n$ elementos, de forma que $X=\{x_{1},...,x_{n}\}$. Vamos a formar un uno-a-uno la correspondencia entre los subconjuntos de a$X$ y el conjunto de la longitud-$n$ cadenas binarias de la siguiente manera. Dada una cadena binaria $$a_{1}\cdots a_{n}$$ imagina que $a_{i}=1$ significa "incluir $x_{i}$ en este subgrupo" e $a_{i}=0$ significa "excluir $x_{i}$ en este subgrupo". Por ejemplo, si $n=4$ entonces el subconjunto $S=\{x_{1},x_{3}\}$ sería representado como $1010$.

Hay exactamente $2^{n}$ cadenas posibles, ya que cada una de las $a_{i}$ tiene dos valores posibles, y hay $n$ de ellos. Y cada cadena que corresponde a uno y sólo un subconjunto de a$X$. Por lo tanto, no se $2^{n}$ subconjuntos.

Answer 3

Escribe todos los números binarios con $3$ dígitos. Cada dígito representa un elemento ( $0$ significa excluir, $1$ significa incluir): $$ \begin{array}{|c|c|} \text{decimal}&\text{binary}&\text{subset}\\\hline 0&000&\{\}\\ 1&001&\{C\}\\ 2&010&\{B\}\\ 3&011&\{B,C\}\\ 4&100&\{A\}\\ 5&101&\{A,C\}\\ 6&110&\{A,B\}\\ 7&111&\{A,B,C\}\\ \end {array} $$ Esto se puede extender fácilmente a un conjunto de elementos $n$ con $n$ dígito números binarios.

Answer 4

Creo que, más directamente, por lo que el libro está diciendo puede ser enunciada como:

Elegir un subconjunto $U$ de un conjunto $S$ es el mismo que, para cada elemento $x\in S$, la elección de si $x$ es de $U$ o no.

En particular, existe, en cualquier momento, sólo un conjunto estamos considerando. Por lo tanto, si $S=\{A,B,C\}$ y queremos elegir un subconjunto $U$, podríamos hacer las siguientes tres opciones: $$A\in U$$ $$B\in U$$ $$C\in U$$ Y tendríamos $U=\{A,B,C\}$. Así, hemos construido un subconjunto haciendo tres opciones binarias. Podríamos intentar este proceso de nuevo para hacer un subconjunto diferente; por ejemplo, podríamos decidir en su lugar $$A\not\in U$$ $$B\not\in U$$ $$C\in U$$ Y a continuación, obtener $U=\{C\}$. Así, hemos hecho un conjunto diferente de opciones y tiene un conjunto diferente. Así, para cada subconjunto, tenemos que hacer tres opciones.

Answer 5

El conjunto de los subconjuntos de a$X$ puede ser visto como el conjunto de todas las funciones de $X$ a $\{0,1\}$, denotado $\{0,1\}^X$.

Para cada función, considerar el subconjunto de $X$ que consta de todos los $x\in X$ tal que $f(x)=1$.

Esto, resulta que es un $1-1$correspondencia.

Como resultado, el fin de el juego de poder es $\mid P(X)\mid=\mid \{0,1\}^X\mid=\mid\{0,1\}\mid^{\mid X\mid}=2^n$.