Question

How many different relations are there from a set with $\mathbf{m}$elements to a set with $\mathit{n}$elements?

Short answer

There are $2^{mn}$ different relations from a set with $m$ elements to a set with $n$ elements.

Step-by-step solution

Given data

A set with $m$ elements to a set with $n$ elements

Concept used of relation

A relation $\mathbf{\text{R}}$ on a set $\mathbf{\text{A}}$ is called reflexive if role="math" localid="1668684995506" $\mathbf{(}\mathit{a}\mathbf{,}\mathit{a}\mathbf{)}\mathbf{\in }\mathit{R}$ for every element $\mathit{a}\mathbf{\in }\mathit{A}$.

A relation $\mathbf{\text{R}}$ on a set $\mathbf{\text{A}}$ is called symmetric if$\mathbf{(}\mathit{b}\mathbf{,}\mathit{a}\mathbf{)}\mathbf{\in }\mathit{R}$ whenever$\mathbf{(}\mathit{a}\mathbf{,}\mathit{b}\mathbf{)}\mathbf{\in }\mathit{R}$, for all $\mathit{a}\mathbf{,}\mathit{b}\mathbf{\in }\mathit{A}$

A relation $\mathbf{\text{R}}$on a set $\mathbf{\text{A}}$such that for all $\mathit{a}\mathbf{,}\mathit{b}\mathbf{\in }\mathit{A}$, if$\mathbf{(}\mathit{a}\mathbf{,}\mathit{b}\mathbf{)}\mathbf{\in }\mathit{R}$and $\mathbf{(}\mathit{b}\mathbf{,}\mathit{a}\mathbf{)}\mathbf{\in }\mathit{R}$then $\mathit{a}\mathbf{=}\mathit{b}$is called anti symmetric.

A relation$\mathbf{\text{R}}$on a set$\mathbf{\text{A}}$is called transitive if whenever $\mathbf{(}\mathit{a}\mathbf{,}\mathit{b}\mathbf{)}\mathbf{\in }\mathit{R}$ and $\mathbf{(}\mathit{b}\mathbf{,}\mathit{c}\mathbf{)}\mathbf{\in }\mathit{R}$ then $\mathbf{(}\mathit{a}\mathbf{,}\mathit{c}\mathbf{)}\mathbf{\in }\mathit{R}$ for all$\mathit{a}\mathbf{,}\mathit{b}\mathbf{,}\mathit{c}\mathbf{\in }\mathit{A}$

 Step 3: Solve for relation

If $\left|A\right|=m$ and $\left|B\right|=n$, then $|A\times B|=mn$ is the size of their Cartesian product.

As any relation from set $A$ to a set $B$is a subset of$A\times B$, the number of relations from $\text{A}$ to $B$ is simply the number of subsets of $A\times B$, i.e., $2^{mn}$.

In other words There are $mn$elements of the set $A\times B$, if $A$ is a set with $m$ elements and $B$ is a set with $n$ elements.

A relation from $A$ to $B$ is a subset of $A\times B$.

Thus the question asks for the number of subsets of the set $A\times B$, which has $mn$elements. By the product rule, it is$2^{mn}$.

Therefore, there are $2^{mn}$ different relations from a set with $m$ elements to a set with $n$ elements.