# Combinatorical proof that the cardinality of the inclusion relation over the powerset is $3^n$

Let $U$ be a finite non-empty set of size $n$. May $E$ be the inclusion relation $\subseteq$ over $P(U)$.

I've seen the proof using Newton's binomial, that $|E| = 3^n$. I'm interested in a more direct combinatorical proof. I've been given a hint: given $A \subseteq B \subseteq U$, $U$ can be represented as a union of 3 disjoint sets. I think this means $A$, $B-A$, and $U-B$. But I couldn't see how that helps.

• To me that looks as a combinatorial proof. In what way do you want it to be more "directly" combinatorial? – skyking Jan 2 '18 at 7:10
• @skyking Maybe "directly" isn't accurate.. I guess I meant simply by not summing up all elements with the binomials (the question used "directly" :/). – Cauthon Jan 2 '18 at 7:23

## 2 Answers

Given $A\subset B \subset U,$ and given any $u\in U,$ there are 3 possibilities for $u.$ Either it is in $A$ (and therefore in $B$), or it is in $B$ but not $A,$ or it is not in $B.$ We can for each $u\in U$ choose one of these three cases, and this describes $A$ and $B$ in a unique way. Now note that there are $3^n$ ways of doing this.

• Awesome, simple, but didn't think of it that way. Thanks! – Cauthon Jan 2 '18 at 7:16

Consider a map $f:U\to\{1,2,3\}$. Define $A=f^{-1}(\{1\})$ and $B=f^{-1}(\{1,2\})$. Prove that $f\mapsto (A,B)$ is a suitable bijection.