# Number of true relations of the form $A\subseteq B$ where $A,B\in\mathcal{P}(\{1,2,\ldots,n\})$

I just started "Introduction to Topology and Modern Analysis" by G.F. Simmons and came across this problem in the exercises.

Q. Let $U=\{1,2,\ldots,n\}$ for an arbitrary positive integer $n$. If $A$ and $B$ are arbitrary subsets of $U$, how many relations of the form $A\subseteq B$ are there? How many of them are true?

Some previous problems for the cases $n=1,2,3$ suggested that by "relations of the form $A\subseteq B$", they mean even the ones where $A\subseteq B$ isn't true.

It would be obvious that there are $2^{2n}=4^n$ such relations since $U$ has $2^n$ subsets, $A,B$ can each be chosen in $2^n$ ways, so there are $2^n\times 2^n=4^n$ such relations.

Now, I think $3^n$ of these relations are true. Here's my idea/proof:

Let us consider $x,y\in\mathcal{P}(U)$ where $\mathcal{P}(U)$ denotes the power set of $U$. Let $x$ have $k$ elements from $U$ (where $0\leq k\leq n$) with $k=0$ corresponding to $x=\emptyset$.

For $x\subseteq y$ to be true, $y$ must have all the elements of $x$ and may/may not have elements from $U\setminus x$. We can construct $y$ by taking $m$ additional elements from $U\setminus x$ where $0\leq m\leq n-k$ which can be done in $\binom{n-k}m$ ways for each value of $m$.

So, for each $x$, we can construct $y$ in $\sum\limits_{m=0}^{n-k}\binom{n-k}m=2^{n-k}$ ways.

Now, we can take $x$ in $\binom nk$ ways for each value of $k$ and hence the number of true relations is $\sum\limits_{k=0}^n\binom nk 2^{n-k}=3^n$.

Is the above correct/rigorous enough?

Also, if the above solution is correct, doesn't it work for any arbitrary set $U$ of cardinality $n$ ?

• what do you mean? You want to know with how many relations you can endow the set $\mathcal P\{1,2,3\dots n\}$ ?? And then how many of these are subsets of the relation $\subseteq$ ? – Jorge Fernández Hidalgo Jul 24 '16 at 18:18
• @CarryonSmiling, it's a problem in the book by Simmons that how many of the set inclusion relations $A\subseteq B$ where $A,B\in\mathcal{P}(\{1,2,\ldots,n\})$ are true? I'm looking for proofreading by the community on my work. – analysis123 Jul 24 '16 at 18:28
• Yeah, your solution looks good. In fact your solution was clearer to me that the actual question. – Jorge Fernández Hidalgo Jul 24 '16 at 18:29

I finally got it.

The question seems to be: How many pairs $(A,B)$ of subsets of $\{1,2\dots n\}$ exist so that $A\subseteq B$.

For each element $x\in \{1,2\dots n\}$ we have three choices:

• $x$ is only in $B$
• $x$ is in $A$ and $B$
• $x$ is not in $A$ and not in $B$.

Therefore there are $3^n$ possible pairs.

Yes, this is correct, and yes, only the cardinality of $U$ matters.

You could slightly simplify the proof by noting that there are $2^{n-k}$ subsets of $U\setminus x$, so you don't have to sum over binomial coefficients.

I find the combinatorial proof in Carry on Smiling's answer simpler and more elegant.