# Counting binary relations

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?

• 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? – Brian M. Scott Nov 14 '20 at 0:07
• 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 – Anar Rzayev Nov 14 '20 at 0:07
• Yes, that’s right, and each of them is a relation from $A$ to $B$. – Brian M. Scott Nov 14 '20 at 0:08
• 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. – Brian M. Scott Nov 14 '20 at 0:15
• You’re welcome! – Brian M. Scott Nov 14 '20 at 0:21