Cardinality of two power sets Question

Question

Problem 5 (2 pts) Given two finite sets A and B with the cardinalities A= n and B = m. (a) What is the cardinality of the powerset P(A x B)? (b) How many functions is there from A to B?

Answer 1

(a) In general, if $A$ is a set containing the $n$ elements $a_1,a_2\ldots,a_n$, then the power set of $A$ will contain $2^n$ elements.

Indeed, a subset of $A$ is completely determined by its elements. So, there are as many subsets of $A$ as there are ways to choose elements in $A$. Now, $$ \text{Either you choose }a_1\text{ or you don't choose }a_1\text{: that's $2$ choices}\\ \text{Either you choose }a_2\text{ or you don't choose }a_2\text{: that's $2$ choices}\\ \vdots\\ \text{Either you choose }a_n\text{ or you don't choose }a_n\text{: that's $2$ choices} $$ By the rule of product in combinatorics, you have $$ \underbrace{2\times2\times\cdot\times2}_{n\text{ times}}=2^n $$ ways to choose elements in $A$, that is, there are $2^n$ subsets of $A$.

So all you have to do is find the number of elements in $A\times B$, which you can do via the same rule of product. Elements of $A\times B$ are of the form $(a,b)$ where $a\in A$ and $b\in B$. How many of these couples exist? $$ \text{As a first choice, select $a\in A$: this can be done in $n$ ways}\\ \text{As a second choice, select $b\in B$: this can be done in $m$ ways} $$ By the rule of product, there are $n\times m$ such couples, that is, $|A\times B|=nm$.

Hence the cardinality of the powerset of $A\times B$ is $2^{nm}$.

(b) What choices are you to make in order to completely specify a function from $A$ to $B$? You have $n$ actions to do: for each element of $A$, you have to assign a unique element of $B$. $$ \text{For $a_1$, select a $b\in B$: this can be done in $m$ ways}\\ \text{For $a_2$, select a $b\in B$: this can be done in $m$ ways}\\ \vdots\\ \text{For $a_n$, select a $b\in B$: this can be done in $m$ ways}\\ $$ By the rule of product, there are thus $$ \underbrace{m\times m\times\cdots\times m}_{n\text{ times}}=m^n $$ functions from $A$ to $B$.