let $E$ be a finite set with $|E|=n$ elements.

  • what is the cardinality of set $\mathcal{E}=\{(A,B)\in \mathcal{P}(E)^{2} \mid A\cup B=E \}$

My proof:

note that $A\cup B=E \iff A^{c}\subset B $ $$|\mathcal{E}|= | \{ (A,B)\in\mathcal{P}(E)^{2} \ / \ A^{c} \subset B \} |$$

Let for every $(A^{c},B)$ the function $f: E \to \{0,1,2\}$ be defined via : $$f(x)= \begin{cases} 0 & \mbox{ if } \quad x\in A^{c} \\ & \\ 1 & \mbox{ if } \quad x\in B\backslash A^{c} \\ & \\ 2 & \mbox{ if } \quad x\in E\backslash B \end{cases} $$

This construction induces a bijection between $\mathcal{E}$ and $\{0,1,2\}^E$ via : $$\begin{array}{ccccc} \mathcal{T} & : & \mathcal{E} & \to & \{0,1,2\}^E \\ & & (A^{c},B) & \mapsto & f \\ \end{array}$$

and therefore yields $|\mathcal{E}| = |\{0,1,2\}^E| = (2 + 1)^n=3^n$

  • Is my proof correct. I'm interested in more ways of prove it
  • 1
    $\begingroup$ Your proof contains no mistakes, but I think you need to explain in more detail why your function is a bijection. $\endgroup$ – Ben Millwood Jan 9 '16 at 16:09
  • $\begingroup$ we can't say that is by construction it's bijecticion ? $\endgroup$ – Educ Jan 9 '16 at 16:11

Your proof looks basically correct, but it has some weaknesses.

You use the "complement" notation $A^c$ but never state your universal set. (You seem to imply that it is $E$.) For that and other reasons you should avoid the complement and stick to set difference.

Your notation for the value $f(x)=1$ is unnecessarily complicated. Why not just use $A\cap B$? That would go well with $E\setminus B$ for $0$ and $E\setminus A$ for $2$.

I agree with @BenMillwood's comment that you should show more detail that your construction makes a bijection.


Pick $A$ first. If $A$ has $k$ elements (there are $\binom{n}{k}$ ways to choose these), then we must pick all $n-k$ elements in $B$, so there are $2^k$ many choices of complementary sets (namely all subsets of $A$ can be added to the compulsory elements of $B$). So we have $\sum_{k=0}^n \binom{n}{k} 2^k$ many choices, which amounts to $3^n$ by Newton's binomial formula (expand $(1+x)^n$ with $x=2$).


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.