Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
I expect you're going to have to do more work than that to get help here. –  kevin cline Jan 31 at 11:59

1 Answer 1

up vote 0 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.