Cardinality of a set

**posix_memalign** · April 29th 2010, 12:26 PM

How can I show that the set { $(A, B) \in P(S) \times P(S) | A \subseteq B$ } contains $3^n$ elements, where S is a set of n elements and P(S) is the power set of S.

[SOLVED]

**Plato** · April 29th 2010, 01:30 PM

Originally Posted by posix_memalign

Let S be a set of n elements and consider the power set P(S) of S.
How can I show that the set { $(A, B) \in P(S) \times P(S) | A \subseteq B$ } contains $3^n$ elements?

Here is some notation. $|A|$ is the number of elements is set $A$ .
Thus $|S|=n$ and $|\mathcal{P}(S)|=2^n$ .

For each set $A$ that are $2^{n-|A|}$ subsets of $S$ that are super-sets of $A$
i.e. $|\{X\in \mathcal{P}(S):A\subseteq X\}|=2^{n-|A|}$
Hence that is the number of wanted pairs $(A,B)$ .

To count them find the sum $\sum\limits_{k = 0}^n {\binom{n}{k} \cdot 2^{n - k} }$ . Do you see why?

Now use the binomial expansion theorem on $3^n=(1+2)^n$

**posix_memalign** · April 29th 2010, 03:44 PM

Originally Posted by Plato

To count them find the sum $\sum\limits_{k = 0}^n {\binom{n}{k} \cdot 2^{n - k} }$ . Do you see why?

After you have arrived at this then it is obvious why it is $3^n$ but I don't see how you arrive at this statement unfortunately no.

**Plato** · April 29th 2010, 04:03 PM

Originally Posted by posix_memalign

After you have arrived at this then it is obvious why it is $3^n$ but I don't see how you arrive at this statement unfortunately no.

Then I must ask you if you understand that the number of subsets having
$A$ as a subset is $2^{n-|A|}?$
If you do then there are $\sum\limits_{k = 0}^n {\binom{n}{k}}$ subsets of each ‘size’.

Thread: Cardinality of a set

LinkBack

Thread Tools

Display

Cardinality of a set

Similar Math Help Forum Discussions

Cardinality

Cardinality of R, [0,1], R^2, [0,1] x [0,1]

Cardinality

Cardinality

Cardinality

Search Tags