Question

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

Answer 1

Let \(n (A) = m\) and \(n (B) = n.\)
We have \(A\times B =\{(a,b):a\in A, b\in B\}\)
\(\Rightarrow n(A\times B)=n (A)\times n (B)=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 \(\phi\) of \(A\times B\)) that can be defined from A to B is \( 2^{mn}-1.\)