Demostrar que todos los conjuntos de tamaño n tienen $2^n$ subconjuntos

Question

He intentado construir una prueba para esto usando recursividad. Mi conocimiento de la recursividad y de la teoría de conjuntos en general es bastante limitado, ¡así que agradecería cualquier comentario!

La reivindicación en lógica simbólica: $\forall n \in \mathbb N, \exists u \in U, S(u) \wedge |u| = n \Rightarrow \mathcal |P(u)| = 2^n$ donde:

$U:$ el conjunto de todo

$S(x):$ x es un conjunto

Valor inicial

Supongamos que $n = 0$

Entonces $\exists u \in U, |u| = 0$

Entonces $u = \varnothing$

Entonces $|\mathcal P(u)| = | \{ \varnothing \} | = 1 = 2^0$

Demuéstralo: $\forall n \in \mathbb N, \exists u, x \in U, [S(u) \wedge (x \notin u) \wedge (|u| = n) \wedge \mathcal |P(u)| = 2^n] \Rightarrow [(|u \cup \{x\}| = n + 1) \wedge (|\mathcal P(u \cup \{x\})| = 2^{n + 1})]$

Supongamos que $|u| = n$

Entonces $|\mathcal P(u)| = 2^n$

Entonces $|u \cup \{x\} | = n + 1$ porque $|\{x\}| = 1$

Entonces $\mathcal |P(u \cup \{x\})| = |\mathcal P(u)| * |\mathcal P(\{x\})| = 2^n * 2 = 2^{n+1}$

¿Es lo bastante convincente o tengo que añadir algo más?

EDIT: Notación corregida

Answer 1

Sea $h_n$ ser un $n$ -Es decir, una cadena formada por 0 y 1. Ahora $S$ sea su suelo fijado con $n$ elementos y $H \subseteq S$ . Si etiqueta los elementos de $S$ de 1 a $n$ dado un $H$ puede construir un $n$ -cadena de bits, digamos $h_n$ como sigue, si $H$ tiene el 1er elemento, tiene 1 en la primera posición y 0 en caso contrario. Si $H$ tiene el segundo elemento, tiene 1 en la 2ª posición y 0 en caso contrario y así sucesivamente...

Por ejemplo, si $S$ = {1,2,3,4,5,6} y $H$ = {2,4,6}, entonces $h_n$ es "010101".

Está claro que dado cualquier subconjunto, se puede construir un $n$ -cadena de bits. A la inversa, dado un $n$ -se puede construir el subconjunto correspondiente. En otras palabras, existe una biyección desde el conjunto de $n$ -al conjunto de todos los subconjuntos de $S$ . Por tanto, el número de subconjuntos de $S$ es igual al número de $n$ -cadenas de bits que es $2^n$ .

Prueba alternativa por inducción:

Que la afirmación sea válida para todos $n$ es decir, si $\vert S \vert = n$ entonces $S$ tiene $2^n$ subconjuntos. Supongamos ahora que se añade un elemento más $x_{n+1}$ a $S$ y llamar a ese conjunto $S'$ . Entonces todos los subconjuntos de $S'$ serán subconjuntos de $S$ con o sin el nuevo elemento $x_{n+1}$ . En otras palabras, para cada $H \subseteq S$ habrá dos subconjuntos $H'$ y $H''$ de $S'$ dado por $H' = H$ y $H'' = H \cup \{x_{n+1}\}$ . Así que si $S$ tiene $2^n$ subconjuntos, $S'$ tendrá $2 \times 2^n = 2^{n+1}$ subconjuntos.

Answer 2

La recursión no es necesaria aquí. Si tenemos un conjunto de tamaño $n$ entonces podemos hacer subconjuntos de tamaño $0,1,2,3...n$ . Como el orden de los elementos en el conjunto no es importante, el número de formas en que podemos elegir subconjuntos de tamaño 0 es $\binom{n}{0}$ . Existen $\binom{n}{1}$ combinaciones para elegir subconjuntos de tamaño 1.

Así que el número total de subconjuntos será:

$$\sum_{k=0}^n \binom{n}{k} = 2^n$$

Si quieres una prueba para esta expresión, aquí tienes una. No es que la suma represente realmente la suma de los números en $n^{th}$ fila del triángulo de Pascal, donde la primera fila se cuenta como 0. Sabemos cómo generar este triángulo y sabemos que cada número del $n^{th}$ fila se calcula dos veces en la suma de la fila siguiente. Por tanto, la relación entre filas vecinas es $2$ . Esto conduce a la progresión geométrica: $ar^{n-1}$ . Sabemos que $a=1$ y $r=2$ así que si dejamos que nuestra primera fila se denote como $n=0$ y, a continuación, la fórmula adquiere su aspecto definitivo:

$$\sum_{k=0}^n \binom{n}{k} = 2^n$$

Answer 3

En primer lugar, no utilice el concepto de "conjunto de todos los conjuntos". Tal conjunto no puede existir. Por favor, lea este artículo para más información.

En segundo lugar, empiece por dejar que $u_0 = \varnothing$ y $u_{i+1}=u_i \cup \{u_i\}$ . En concreto, esto significa que $u_2=\{\varnothing,\{\varnothing\}\}$ . Entonces tiene garantizados elementos únicos en $u_i$ para todos $i$ y puedes construir una inducción en él. El conjunto de potencias de $u_i$ y $u_{i+1}$ será muy fácil construir y confirmar que tiene $2^i$ y $2^{i+1}$ elementos (respectivamente).

Por último, creo que $|\mathcal P(u \cup \{x\})| = |\mathcal P(u)| * |\mathcal P(\{x\})|$ tendrían que probarse por separado.

Answer 4

Puede representar cada subconjunto de un conjunto con $n$ elementos por una secuencia de $a_1...a_n$ donde $a_i$ es $0$ o $1$ . $a_i=0$ significa que el $i$ ésimo elemento del conjunto no está presente en el subconjunto. Ahora el número de todas estas secuencias es $2\times 2\times ...\times 2=2^n$ .

Answer 5

Lo has demostrado para conjuntos de tamaño 0 ahora tienes que demostrar:

si un conjunto de tamaño n tiene $2^n$ diferentes subconjuntos entonces un conjunto de tamaño n+1 tiene $2^{n+1}$ diferentes subconjuntos

y, a continuación, puede utilizar la inducción