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
    "As easy as it looks" is in the eye of the beholder. Good analysis.2011-12-03
  • 0
    yeah... that's also true...2011-12-03
  • 0
    @Srivatsan: Thanks for the edit. Will keep the points in mind in the future! :)2011-12-04
  • 0
    @Jayesh I should've left a comment after editing. It's not to say that the notation $C(n,r)$ is not in use. However $\binom{n}{k}$ is much more common and standard these days. And it was designed with just the binomial coefficients in mind. :=)2011-12-04
  • 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
    ohh.. thats new!! thanks!!2011-12-03
  • 0
    Nice. Generalizes, too: there are $(k+1)^n$ true statements of the form $A_1\subseteq\dots\subseteq A_k$.2011-12-03