Finding the number of different relations and functions

1.1k Views Asked by At

This must be a very stupid question. Let set $A=\lbrace{a,b\rbrace}$ and $B=\lbrace{1,2,3\rbrace}$. The total number of relations from $A$ to $B$ is $6$. We can calculate this as a has $3$ choices and b has $3$ choices to make. So the total is $3+3=6$. When we calculate the number of functions from $A$ to $B$, it is $3^2$. This is because $a$ has $3$ choices and $b$ has $3$ choices to make. So the total number of functions is $3\times3$.

But here is my doubt, why do we use addition in the first case but multiplication in the second. This is a very trivial example and I know we can verify the results by taking examples and counting. But I want to understand how to distinguish between these two situations.

1

There are 1 best solutions below

3
On

Your explanation of the number of functions from $A$ to $B$ is correct: there are 3 elements of $B$ that $a$ could be sent to by a function and (independently) 3 elements of $B$ that $b$ could be sent to by a function. So the total number of functions from $A$ to $B$ is $3^2$.

But the number of relations from $A$ to $B$ is not $3+3$. A quick way to spot that there are not 6 relations from $A$ to $B$ is to observe that there are 9 functions from $A$ to $B$. Remember: every function from $A$ to $B$ is (in particular) a relation from $A$ to $B$, so the number of relations will always be $\geq$ the number of functions, and therefore in this example there must be at least 9 relations from $A$ to $B$.

How many relations are there? A relation from $A$ to $B$ is any subset of the Cartesian product $A\times B$. The set $A\times B$ has $2\times 3$ elements because there are 3 elements of the form $(a,\text{something from $B$})$ and 3 elements of the form $(b,\text{something from $B$})$. So, if you like, the size of $A\times B$ is $3+3$. This is where the addition comes in, but it's not actually the number of relations from $A$ to $B$. To calculate the number of relations you need to now calculate the number of subsets of the 6-element set $A\times B$.