why the number of relations seem to be smaller than the number of functions

62 Views Asked by At

I may ask a stupid question:

let's say I have 2 sets. A has a number of elements. $B$ has $b$ number of elements. The number of relation from $A$ to $B$ is $|A×B|$ $=$ $|A|×|B|= a × b$. The number of functions from $A$ to $B$ is $|B|^{|A|}$ = $b^a$.

Usually, $b^a$ > $b*a$. like $2^3$ > $2*3$. But functions have stricter rules than relations. Should it have less number of functions than relations? I am a bit confused.

1

There are 1 best solutions below

1
On

Your first calculation counts the number of ordered pairs, not the number of relations. A relation is a subset of the Cartesian product. So the number of relations is the cardinality of the power set of $A\times B$, in your case $2^{ab}$.