¿Qué es la prueba de que el número total de subconjuntos de un conjunto es $2^n$?

Question

¿Qué es la prueba de que, dado un conjunto de $n$ elementos hay $2^n$ posibles subconjuntos (incluyendo el vacío y el conjunto original).

Answer 1

Supongamos que usted quiere elegir un subconjunto. Para cada elemento, usted tiene dos opciones: o bien colocarla en el subconjunto, o no; y estas opciones son todos independientes.

Comentario: esto funciona también para el conjunto vacío. Un conjunto vacío tiene exactamente un subconjunto, es decir, el conjunto vacío. Y el hecho de que $2^0=1$ refleja el hecho de que sólo hay una forma de selección de los elementos a todos!!!!

Answer 2

Aquí está una prueba por inducción sobre $n$. Esta prueba se supone que hemos definido $2^n$ por recursión como $2^0 = 1$$2^{n+1} = 2^n \cdot 2$.

Esto es cierto para $n=0$ porque $\emptyset$ tiene exactamente un subconjunto, es decir, $\emptyset$ sí.

Ahora, supongamos que la afirmación es verdadera para conjuntos con $n$ muchos elementos. Dado un conjunto $Y$ $n+1$ muchos elementos, podemos escribir $Y = X \cup \{p\}$ donde $X$ es un conjunto con $n$ muchos elementos y $p \notin X$. Hay $2^n$ muchos subconjuntos $A \subset X$, y cada subconjunto $A \subset X$ da lugar a dos subconjuntos de a $Y$, es decir, $A \cup \{p\}$ $A$ sí. Por otra parte, cada subconjunto de $Y$ surge de esta manera. Por lo tanto, el número de subconjuntos de a $Y$ es igual a $2^n \cdot 2$, que a su vez es igual a $2^{n+1}$.

Answer 3

Debemos mostrar que $${n\choose 0}+{n\choose 1}+{n\choose 2}+\cdots +{n\choose n}=2^n$$ is the number of subsets of an $n$-element set $S$ where $n\geq0$.

Cada subconjunto de $S$ $k$- subconjunto de $S$ donde $k=0,1,2,...,n$. Sabemos que ${n\choose k}$ es igual al número de $k$-subconjuntos de S. por Lo tanto, por el Principio de Adición $${n\choose 0}+{n\choose 1}+{n\choose 2}+\cdots +{n\choose n}$$ equals the number of subsets to the set $S$. We can count the same thing by observing that each element of the set $S$ has two choices, either they are in a subset or they are not in a subset. Let $S=\{x_1,x_2,x_3,...,x_n\}$. So, $x_1$ is either in a subset or it is not in a subset, $x_2$ is either in a subset or it is not in a subset,..., $x_n$ is either in a subset or it is not in a subset. Thus by the Multiplication Principle there are $2^n$ ways we can form a subset of the set $S$. Hence ${n\elegir 0}+{n\elegir 1}+{n\elegir 2}+\cdots +{n\elegir n}=2^n$.

Otro enfoque es considerar el Teorema del Binomio $$(x+y)^n=\sum_{k=0}^n {n\choose k}x^{n-k}y^k.$$ Letting $x=1$ and $y=1$ we obtain$$2^n=\sum_{k=0}^n{n\choose k}.$$

Answer 4

Aquí está la prueba mediante números binarios. Un conjunto de N elementos se puede representar como un vector de dígitos binarios. Cuando el dígito es 1, indica que el elemento correspondiente está presente. 0 significa que está ausente.

De hecho, esta representación se utiliza en la programación de computadoras como una manera de representar los conjuntos que tiene bueno peor de los casos eficiencia de memoria, así como otros atributos tales como la simplicidad de implementación.

Así, por ejemplo, un conjunto de 32 elementos, puede ser representado como una cadena de 32 1. Y, a continuación, podemos representar los subconjuntos de estos elementos, volteando algunas de estas 1 a 0 en diversas combinaciones.

Todos los posibles subconjuntos son, por tanto, simplemente, de todos los posibles números de 32 bits, y no se $2^{32}$ a dichos números.

En otras palabras, el número de subconjuntos está relacionado con el hecho de que la pertenencia es un binario de la proposición: algo es o no es un elemento de un conjunto. Sí o no, verdadero o falso, uno o cero.

Answer 5

He aquí una prueba combinatoral $$\sum_{k=0}^n{n \choose k}=2^n$$ Ambas contar el número de subconjuntos en un $n$ elemento del conjunto. El lado derecho cuenta con ellos directamente (relativa a Marie de la respuesta) y el lado izquierdo cuenta el número de $k$-elemento subconjuntos y, a continuación, suma más de $k$. Esta ecuación también puede ser verificado por el teorema binomial con $x=y=1$.