2
$\begingroup$

This question is from the book Introduction to Topology and Modern Analysis by GF Simmons, Problem 3(d) at end of Section 1. I'll paraphrase the question here.

Suppose $U$ is a containing $n$ elements. Then, how many subsets are there? How many possible relations of the form $A \subseteq B $ exist where $A,\ B$ is a subset of $U$? Can you make an informed guess as to how many are true?

Solution:

First two are simple. $2^n$ and $2^{2n}$. For the third one, assume $A$ contains $k$ elements. Then, number of different possible $A$ is $\binom{n}{k}$ and the number of possible sets, of which $A$ is a subset, (number of different possible $B$) is $2^{n-k}$. Taking sum while varying $k$ from $0$ to $n$ gives us

$\sum 2^{n-k} \binom{n}{k} $

which is $3^n$. Is this correct? If it is? Then why does the book tells us to make an informed guess? Reading the word informed guess made me suspicious that the question is not as easy as it looks.

  • 0
    :)... No problems.. You took out time to edit it.. That's enough! :)2011-12-04

1 Answers 1

3

If $A \subseteq B$, then each element of $U$ can be

  1. in none of $A$ and $B$,
  2. in $B$ only,
  3. in $A$ and $B$.

The choices for each element are independent, so the answer is $3^n$.

  • 0
    Nice. Generalizes, too: there are $(k+1)^n$ true statements of the form $A_1\subseteq\dots\subseteq A_k$.2011-12-03