= Solution
First suppose the <sets> are finite, with <cardinalities> $a=|A|\geq2$ and $b=|B|\geq2$. The <power set> and <Cartesian product> counting rules give
$$
|\mathcal P(A\times B)|=2^{ab},\qquad
|\mathcal P(A)\times\mathcal P(B)|=2^{a+b}.
$$
Since $ab-a-b=(a-1)(b-1)-1\geq0$, the desired inequality follows.
The <power-set product cardinality inequality> also has an <injection> proof that does not assume finiteness. Choose distinct $a_0,a_1\in A$ and distinct $b_0,b_1\in B$. For $S\subseteq A$ and $T\subseteq B$, define the <subset> of $A\times B$
$$
\Phi(S,T)=(S\times\{b_0\})\cup(\{a_0\}\times(T\setminus\{b_0\}))\cup E_T,
\qquad
E_T=\begin{cases}\{(a_1,b_1)\},&b_0\in T,\\\varnothing,&b_0\notin T.\end{cases}
$$
These three encoding regions are disjoint. The row with second coordinate $b_0$ recovers $S$; the column with first coordinate $a_0$ and second coordinate different from $b_0$ recovers $T\setminus\{b_0\}$; the extra position $(a_1,b_1)$ records whether $b_0\in T$. Thus $\Phi$ is <injective>, proving for arbitrary <sets>
$$
\boxed{|\mathcal P(A\times B)|\geq|\mathcal P(A)\times\mathcal P(B)|.}
$$
Encoding by $S\times T$ alone would fail: all pairs with either factor empty would have the same output.
Back to article page
