0
$\begingroup$

How can the following be calculated?

Given the sets $X = \{1, 2, \dots, 10\}$ and $Y = \{1, 2, \dots, 12\}$, compute $| \mathcal P (Y) \setminus \mathcal P (X) |$, where $\mathcal P (X) = \{ A \mid A \subseteq X \}$ and $|X|$ is the cardinal of $X$.

$\endgroup$

2 Answers 2

1
$\begingroup$

The principle of inclusion-exclusion says that $|A\cup B|=|A|+|B|-|A\cap B|$ for any sets $A,B$. Taking $A=X \setminus Y$ and $B=Y$, \begin{align*} |(X\setminus Y)\cup Y|&=|X\setminus Y|+|Y|-|(X\setminus Y)\cap Y|\\ |X\cup Y|&=|X\setminus Y|+|Y|-0. \end{align*} So $|X\setminus Y|=|X\cup Y|-|Y|=(|X|+|Y|-|X\cap Y|)-|Y|=|X|-|X\cap Y|$. Can you find $|P(Y)\cap P(X)|$? Hint: try to write $P(Y)\cap P(X)$ as $P(Z)$ for some set $Z$.

$\endgroup$
0
$\begingroup$

As $x\subset y$, $P(x)\subset P(y)$ and: $$|P(y)\setminus P(x)| = |P(y)| - |P(x)| = \cdots$$

$\endgroup$
2
  • $\begingroup$ The solution would simply be: 2^12 - 2^10 = 3072 ? $\endgroup$ Commented Jan 6, 2016 at 15:19
  • $\begingroup$ @AdamHodgson, right. $\endgroup$ Commented Jan 6, 2016 at 15:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .