Question

Suppose that f is a function from A to B where A and B are finite sets. Explain why$\left|f\right(S\left)\right|=\left|S\right|$ for all subsets S of A if and only if f is one-to-one.

Short answer

Let $S=\left\{x,y\right\}$.

Then$\left|S\right|=2$ but$\left|f\right(S\left)\right|=1$

Step-by-step solution

Step: 1

If f is one-to-one, then f provides a bijection between S and $f\left(S\right)$. so they have the same cardinality. If f is not one-to-one, then there exist elements x and y in S such that$f\left(x\right)=f\left(y\right)$

Let $S=\left\{x,y\right\}$.

Then$\left|S\right|=2$ but$\left|f\right(S\left)\right|=1$