Question

Let $n\left(A\right)=m$ and $n\left(B\right)=n.$ Then, the total number of non-empty relations that can be defined from $A$ to $B$ is .

• A. $m^n$
• B. $mn-1$
• C. $2^{mn}-1$
• D. $n^m-1$
• E. $2^{mn}$

Answer 1

The correct option is C $2^{mn}-1$

Let $n\left(A\right)=m$ and $n\left(B\right)=n.$
We have $A\times B=\left\{\right(a,b):a\in A,b\in B\}$
$\Rightarrow n(A\times B)=n\left(A\right)\times n\left(B\right)=mn$

A relation from A to B is a subset of $A\times B.$
Since $A\times B$ has $mn$ elements, it has $2^{mn}$ subsets.
Thus, there can be $2^{mn}$ relations that can be defined from A to B.
$\Rightarrow$ The total number of non-empty relations (excluding the subset $\varphi$ of $A\times B$) that can be defined from A to B is $2^{mn}-1.$