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|\le \left|S\right|$ for all subsets S of A.

Short answer

$\left|f\right(S\left)\right|\le \left|S\right|$for all subsets S of A.

Step-by-step solution

Step: 1

Given a function from A to B where A and B are finite sets.

We have cardinality of A$\ge$ cardinality of f(A)

Thus, S is the subset of A. Let, it has k elements.

$\left|f\right(S\left)\right|\le k$

Step: 2

Now, by definition of a function, two different elements of S may have the same image in f(S).

But two different images cannot have the same pre image.

Thus, the maximum number of elements of f(S)= the number of elements of S.

Hence we get $\left|f\right(S\left)\right|\le \left|S\right|$.