0
$\begingroup$

Let $A$ and $B$ be finite sets, $|A| = m$ and $|B| = n$. How many binary relations are there from $A$ to $B$?

As far I read from various resources, binary relations is nothing but just a typical (total) function. Then, does it mean that such possibilities are equal to $n^m$, or not?

Improve this question
$\endgroup$
  • 3
    $\begingroup$ No, absolutely not: most relations are not functions. A relation from $A$ to $B$ is simply a subset of $A\times B$; how many of those are there? $\endgroup$ – Brian M. Scott Nov 14 '20 at 0:07
  • 1
    $\begingroup$ There are $2^{mn}$ number of subsets of Cartesian product, but I can not analyze how can we build such binary relations using these Cartesian product subsets $\endgroup$ – Anar Rzayev Nov 14 '20 at 0:07
  • 4
    $\begingroup$ Yes, that’s right, and each of them is a relation from $A$ to $B$. $\endgroup$ – Brian M. Scott Nov 14 '20 at 0:08
  • 4
    $\begingroup$ The question that you’ve written justs asks for the number of binary relations from $A$ to $B$, so it simply wants a number; the point is to find out whether you know that the relations from $A$ to $B$ are just the subsets of $A\times B$ and whether you know how to calculate how many subsets there are. $\endgroup$ – Brian M. Scott Nov 14 '20 at 0:15
  • 1
    $\begingroup$ You’re welcome! $\endgroup$ – Brian M. Scott Nov 14 '20 at 0:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.