Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Discrete mathematics, continuous mathematics, and probability (resit) / 1 / d / ii

First suppose the sets are finite, with cardinalities $a=|A|\ge 2$ and $b=|B|\ge 2$. The power set and Cartesian product counting rules giveSince $ab-a-b=(a-1)(b-1)-1\ge 0$, 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$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 setsEncoding by $S\times T$ alone would fail: all pairs with either factor empty would have the same output.