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