1
$\begingroup$

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.

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

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.

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

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.

$\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.