1
$\begingroup$

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$ ?

$\endgroup$
  • $\begingroup$ 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$ ? $\endgroup$ – Jorge Fernández Hidalgo Jul 24 '16 at 18:18
  • $\begingroup$ @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. $\endgroup$ – analysis123 Jul 24 '16 at 18:28
  • 1
    $\begingroup$ Yeah, your solution looks good. In fact your solution was clearer to me that the actual question. $\endgroup$ – Jorge Fernández Hidalgo Jul 24 '16 at 18:29
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.