# Cardinality of set containing true order relations from a power set

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.

-
"As easy as it looks" is in the eye of the beholder. Good analysis. – André Nicolas Dec 3 '11 at 17:39
yeah... that's also true... – Jayesh Badwaik Dec 3 '11 at 17:42
@Srivatsan: Thanks for the edit. Will keep the points in mind in the future! :) – Jayesh Badwaik Dec 4 '11 at 15:07
@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. :=) – Srivatsan Dec 4 '11 at 16:44
:)... No problems.. You took out time to edit it.. That's enough! :) – Jayesh Badwaik Dec 4 '11 at 18:59

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$.
Nice. Generalizes, too: there are $(k+1)^n$ true statements of the form $A_1\subseteq\dots\subseteq A_k$. – Brian M. Scott Dec 3 '11 at 17:50