Relations On Sets - Discrete

[flakine]

Suppose A is a set with m elements and B is a set with n elements.
a) How many binary relations are there from A to B? Explain.
b) How many functions are there from A to B? Explain.

I have the anwsers to both a) and b), but could someone please exlpain?

a) 2^(mn)
b) n^(m)

 

[pka]

Suppose A is a set with m elements and B is a set with n elements.
a) How many binary relations are there from A to B? Explain.
b) How many functions are there from A to B? Explain.
I have the anwsers to both a) and b), but could someone please exlpain?
a) 2^(mn) b) n^(m)

Any binary relation is a subset of \(\displaystyle A \times B\), that is the cross product.
There are \(\displaystyle {m \times n}\) pairs in \(\displaystyle A \times B\), so there are \(\displaystyle 2^{m \times n}\) possible subsets of \(\displaystyle A \times B\).
That answers part (a).

The set \(\displaystyle B^A\) is the set of all functions from \(\displaystyle A \to B\).
Each \(\displaystyle x \in A\) can be assigned to n possible values in \(\displaystyle B\), so \(\displaystyle n^m\).
That answers part (b).