How to determine the number of equivalence classes on unspecified, finite sets where $|A| = k$ and $|B| = n$

52 Views Asked by At

If $A$ and $B$ are both finite sets with $|A| = k$ and $|B| = n$.

If $f:A \rightarrow B$ and a relation on $A$ is given where $xRy$ if and only $f(x) = f(y).$

So if I've already proved that $xRy$ is an equivalence relation, how can I determine the number of equivalence relation for:

1: $f$ is injective

2: $f$ is surjective

I'm honestly not sure how to find the number of equivalence classes, especially for sets with an unspecified number of elements.

1

There are 1 best solutions below

1
On BEST ANSWER

The equivalence classes are in natural bijection with the range of $f$. Hence for injective $f$, there are $|A|$ equivalence classes, for surjective $f$, there are $|B|$ equivalence classes.