= Power-set product cardinality inequality
{title2=$|\mathcal P(A\times B)|\geq|\mathcal P(A)\times\mathcal P(B)|$}
For arbitrary <sets> $A,B$ each containing at least two elements, the displayed inequality follows by explicitly encoding two <subsets> in disjoint parts of a <Cartesian product>. Choose $a_0\ne a_1$ and $b_0\ne b_1$, put $S$ along the row $A\times\{b_0\}$, put $T\setminus\{b_0\}$ along the column $\{a_0\}\times(B\setminus\{b_0\})$, and add the extra point $(a_1,b_1)$ precisely when $b_0\in T$. These regions are disjoint, so the encoding recovers both $S$ and $T$ and is an <injection> from $\mathcal P(A)\times\mathcal P(B)$ into $\mathcal P(A\times B)$. This proves the <cardinality> inequality even for infinite <sets>. For finite sizes $a,b\geq2$, the same result is $2^{ab}\geq2^{a+b}$, since $ab-a-b=(a-1)(b-1)-1\geq0$. Mapping $(S,T)$ to $S\times T$ is insufficient because all pairs with an empty factor collapse.
Back to article page
