Cardinality of a set defined on the Cartesian product of a power set. $2^A$ is the power set of some finite set A. 
Let $R:= \{(B, C) \in 2^A \times 2^A | B \subseteq C\}$. Show that $\lvert R\rvert = 3^{\lvert A\rvert}$.
It is the $B \subseteq C$ part in the definition of $R$ that I cannot understand nor its implications. $2^A \times 2^A$ would just be the Cartesian product. However, with the condition $B \subseteq C$ not all elements of the product would be included. I cannot visualize/articulate which would be, though.
 A: Label all $n$ points of $A$ with a $0,1$ or $2$. 
Discard all points with label $0$, put all points with label $1$ in set $B$ and all the ones with label $1$ or $2$ in set $C$. That way we make a pair $(B,C)$ with $B \subseteq C$, that lies in $R$.
Convince yourself that this makes for a bijection between all such labellings of $A$ and all pairs in $R$.
As a bonus: if we just put the label $2$ in $B$ we’d have a bijection with set of disjoint pairs $(A,B)$. So there are the same number of such pairs too. 
A: Henno Brandsma has already given the best proof for this; here's what I consider the second best. For any fixed $C$, say of cardinality $k$ (so $0\leq k\leq|A|$), the number of pairs $(B,C)\in R$ with this fixed $C$ as the second component is just the number of subsets $B$ of $C$, namely $2^k$. 
Now consider what happens when you let $C$ vary, so now you're looking at all of $R$. There are $\binom{|A|}k$ subsets $C$ of size $k$ in $A$, so the total number of pairs $(B,C)\in R$ is 
$$
\sum_{k=0}^{|A|}\binom{|A|}k2^k=\sum_{k=0}^{|A|}\binom{|A|}k2^k1^{|A|-k}=
3^{|A|}
$$
by the= binomial theorem.
A: First, we takt $A$ to be the empty set. In this case $\vert A \vert = 0$, and 
$$ 2^A = \{ \ \emptyset \ \} $$
so that $$\left\vert 2^A \right\vert = 1. $$
And, in this case 
$$ R = \big\{ \ ( \emptyset, \emptyset ) \ \big\} $$
so that 
$$ \left\vert R \right\vert = 1 = 3^0 = 3^{\vert A \vert}. \tag{0} $$
Now let us suppose that $A$ has just one element; without any loss of generality we can take 
$$ A \colon= \{ \ 1 \}. $$
Then 
$$ 2^A = \big\{ \ \emptyset, \{ 1 \} \ \big\}. $$
So 
$$ R = \big\{ \ (\emptyset, \emptyset ), \big( \emptyset, \{ 1 \} \big), \big( \{ 1 \}, \{ 1 \} \big) \ \big\} $$
so that 
$$ \vert R \vert = 3 = 3^1 = 3^{\vert A \vert }. \tag{1} $$
You can similarly deal with the case when $A$ has $2$ elements, $3$, elements, $4$ elements, and so on. 
Suppose that for any set $S$ having $n$ elements, where $n$ is a natural number, the set $R$ has cardinality equal to $3^n$. Let us suppose that our set $A$ has $n+1$ elements. Without any loss of generality, we can take 
$$ A \colon= \{ \ 1, \ldots, n, n+1 \ \}. \tag{Def. 1}$$
Let us take 
$$ A^\prime \colon= \{\ 1, \ldots, n \ \}, \tag{Def. 1'} $$
and let us take 
$$ R^\prime \colon= \left\{ \ (B, C) \in 2^{A^\prime} \times 2^{A^\prime} \ \colon \ B \subset C \ \right\}. $$
Then by our hypothesis
$$ \left\lvert R^\prime \right\vert = 3^n. $$
Now we construct $R$ from $R^\prime$ as follows: 
$$ 
\begin{align}
 R &\supseteqq  \left\{ \ (B, C) \in 2^{A^\prime} \times 2^{A^\prime} \ \colon \ B \subset C \ \right\} \bigcup \left\{ \ \big(B, C \cup \{ n+1 \} \big) \in 2^{A^\prime} \times 2^{A^\prime} \ \colon \ B \subset C \ \right\} \\
&\qquad  \bigcup \left\{ \ \big(B \cup \{ n+1 \} , C \cup \{ n+1 \} \big) \in 2^{A^\prime} \times 2^{A^\prime} \ \colon \ B \subset C \ \right\}
\end{align}
$$
So
$$ \vert R \vert \geq 3 \times \left\vert R^\prime \right\vert = 3 \times 3^n = 3^{n+1}. $$
In the above calculation, we have used the following reasoning:


*

*Given a subset $B^\prime$ of $A^\prime$, the set $B^\prime \cup \{ n+1 \} \subset A$.

*Given two subsets $B^\prime$ and $C^\prime$ of set $A^\prime$ such that $B^\prime \subset C^\prime$, we find that (i) $B^\prime \subset C^\prime$, (ii) $B^\prime \subset C^\prime \cup \{ n+1 \}$, and (iii) $B^\prime \cup \{ n+1 \} \subset C^\prime \cup \{ n+1 \}$. 

*Finally, we note that the techniques in the last two points enable us to exhaust all possible ordered pairs of sets in $R$ so that the desired equality does indeed hold. 
Hence by induction our proof is complete.   
