Encontrar la Cardinalidad de un Producto Cartesiano

Question

Problema: $$A=\{ 1,2,3, \dots, n \}$$ $$\text{ Find the Cardinality of ... }$$ $$\{(a,S) | a \in S, S \P(A)\}$$

Así que la manera en la que he abordado este problema hasta ahora era encontrar la cardinalidad de a $S$ y luego se multiplica por la cardinalidad de a $a$. Si no me equivoco, la cardinalidad de a $S$ debe $2^n-1$ $S$ no puede ser un elemento de sí mismo y la cardinalidad de a$P(A)$$2^n$. Sin embargo, estoy teniendo dificultades para encontrar la cardinalidad de a $a$. Es simplemente n? Y si es así, ¿por qué?

Answer 1

Como $S$ es un subconjunto de $A$, $a\in S$ es un elemento de $A$, y, en consecuencia, hablar acerca de su cardinalidad no tiene mucho sentido. Voy a ofrecer algunos consejos sólo desde esta podría ser una tarea cuestión. Deje $T$ el conjunto cuya cardinalidad a preguntarle.

---

Ejemplo: Vamos a arreglar $n:=3$ por ahora. Entonces

$$\mathcal{P}(A)=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},A\}.$$

En este caso tenemos

$$T=\{(1,\{1\}),(2,\{2\}),(3,\{3\}),(1,\{1,2\}),(2,\{1,2\}),(1,\{1,3\}),(3,\{1,3\}),(2,\{2,3\}),(3,\{2,3\}),(1,A),(2,A),(3,A)\}$$

y, en consecuencia,$\operatorname{card}(T)={3\choose 1}+2{3\choose 2}+3{3\choose 3}=12$.

---

Sugerencia: Observe que en el ejemplo anterior, hice una lista de los elementos de $T$ utilizando un algo natural orden de sus elementos. Primero pedí los subconjuntos no vacíos de a $A$ (que son los triviales elementos del juego de poder de $A$) de acuerdo a su cardinalidad, y luego he utilizado el natural orden de los números naturales a la orden de los pares de $(a,S)$ (fija $S$). En términos de cardinalidades, a continuación, calcular la cardinalidad de a $T$ no es nada pero contando la cardinalidad de el juego de poder de $A$, excepto uno debe usar la cardinalidad de cada subconjunto de peso, por lo que un subconjunto de a $A$ $k$ elementos deben contribuir no $1$ pero $k$ para el total de la cuenta.

---

Sugerencia 2: Continuando a partir de la anterior sugerencia, hay (al menos) dos formas de dar una respuesta. Ya sea que usted puede generalizar la fórmula para $n=3$ y mostrar lo que es correcto para arbitrario $n$ el uso de la inducción, o usted puede intentar escribir $T$ como distinto de la unión de conjuntos cuyos cardinalidades son mucho más fáciles de calcular. Siguiendo el orden utilizado anteriormente, un subconjunto distinto de cero de a $A$ puede tener al menos $1$ elemento y en la mayoría de las $n$ elementos. Pero, ¿cuántos subconjuntos de a $A$ hay que contenga $k$ elementos, para $1\leq k\leq n$?

---

Como ejercicio adicional, podría ser de utilidad también para pensar en lo que sucede cuando $A:=\Bbb{N}$.