# Count number of binary relations between sets

He, I have following questions:

We have sets $A$ and $B$, $\left | A \right | = m,\left | B \right | = n$.

1) How many binary relations are there from $A$ to $B$?

2) How many binary relations are there from $A$ to $B$ but with property $\forall x\in A, \;\exists y \in B: \;\left(x, y \right) \in R$

3) How many binary relations are there from $A$ to $B$ but with property $\forall y\in B, \;\exists x \in A: \;\left(x, y \right) \in R$

I have managed to solve first one, and i got $2^{mn}$, which I assume is correct. I suspect that third one is a surjection property. Can you help me with $2$) and $3$), please?

-
I expect you're going to have to do more work than that to get help here. – kevin cline Jan 31 '14 at 11:59

1) Your solution is correct. Every subset of $A\times B$ is a binary relation and $A\times B$ has $mn$ elements hence $2^{mn}$ subsets.

As a prelude on 2) and 3) now a less direct route:

1') For every $x\in A$ there is a subset of $B_x\subset B$ s.t. $R\cap\left(\{ x\right\} \times B)=\left\{ x\right\} \times B_x$.

There are $2^{n}$ choices (all subsets of $B$) leading to to $\left(2^{n}\right)^{m}=2^{mn}$ possibilities. Here $R=\cup_{x\in A}(\{x\}\times B_x)$.

2) For every $x\in A$ there is a non-empty subset of $B_x\subset B$ s.t. $R\cap\left(\{ x\right\} \times B)=\left\{ x\right\} \times B_x$.

There are $2^{n}-1$ choices (all subsets of $B$ except the empty one) leading to $\left(2^{n}-1\right)^{m}$ possibilities.

3) The same reasoning works here and leads to $\left(2^{m}-1\right)^{n}$ possibilities.

-