# 13. Let f : P ({1,2,3,4}) → {0,1,2,3,4} be the function that maps each subset S ⊆ {1,2,3,4} to its cardinality, f (S)= |S|. Is f onto or 1-1?

After working through this, I was sure that function f was one-to-one and not onto, but according to my answer key its onto but not one-to-one. I don't exactly understand how though. Here's my thought process:

Function f maps elements of P{(1, 2, 3, 4)} to the set {0, 1, 2, 3, 4}

Possible subsets of P({1,2,3,4)} are: {∅,{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4} = 16 total subsets, each denoted as set S.

Every subset set has elements that can ALL be uniquely mapped to elements in the set {0,1,2,3,4}, but 0 in this set can never be mapped to any elements of S.

So, I would think the function is one-to-one, but not onto.

Can someone explain where I'm going wrong? Thanks! :D

• It's not the elements that are being mapped. It's the sets themself. The function is is so that $f({1,3,4})=3$ because $\{1,3,4\}$ has three elements. And the function is so that $f(\{1,2,4\})=3$ because $\{1,2,4\}$ has three elements. And $f(\{1,3\}) =2$ and $f(\{2,4\}) =2$. ... If $f$ were one-to-one that would mean every subset will have a different cardinality. Is that true? And if $f$ were not onto that would mean there is some number that represents a cardinality that no subset has.... Dec 3, 2022 at 6:14
• "Every subset set has elements that can ALL be uniquely mapped to elements in the set {0,1,2,3,4}, " That doesn't matter. What if we had $g: P(\{apple,banana,currant, date\})\to \{0,1,2,3,4\}$ via $f(S)=|S|$. Then none of the elements of $apple, banana, etc$ mapp to any of the elements $0,1,2,3,4$ but as $|\{apple, date\}| = 2$ we have $f(\{apple, date\}) = |\{apple, date\}| = 2$..... and $f(\emptyset) = |\emptyset| = 0$. Dec 3, 2022 at 6:33

## 2 Answers

It's not the elements that are being mapped. It's the sets themself.

The function is is so that $$f({1,3,4})=3$$ because $$\{1,3,4\}$$ has three elements. And the function is so that $$f(\{1,2,4\})=3$$ because $$\{1,2,4\}$$ has three elements. And $$f(\{1,3\}) =2$$ and $$f(\{2,4\}) =2$$.

And $$f(\emptyset) = 0$$ because $$\emptyset$$ has $$0$$ elements.

If $$f$$ were one-to-one that would mean every subset will have a different cardinality. Is that true? And if $$f$$ were not onto that would mean there is some number that represents a cardinality that no subset has....

So is it one-to-one? Is it onto?

One-to one:
$$f(A) =f(B) \iff |A| = |B|$$. As there are MANY cases of $$|A| =|B|$$ without $$A = B$$ (for example $$|\{1\}| = |\{3\}| = 1$$ and $$|\{1,3\}| = |\{1,2\}| = 2$$ etc. $$f$$ is not one to one:

Onto:
$$f(A) = k\iff |A|=k \iff A$$ has $$k$$ elements.
$$f(A) = 0$$ if $$|A|$$ has $$0$$ element. $$\emptyset$$ has $$0$$ elements so $$f(\emptyset) = 0$$.
$$f(A) = 1$$ if $$|A|$$ has $$1$$ element. $$\{1\}, \{2\}, ...$$ etc. all have one element so $$f(\{1\} = f(\{2\}=.... = 1$$ and $$f(A) =1$$ does happen.
Similarly $$f(A) =2$$ or $$f(A) = 3$$ or $$f(A) =4$$ if $$A$$ has two, three or four elements. I'll leave it as "obvious" that, indeed, there are sets with $$2,3$$ or $$4$$ elements. (Ex. $$\{1,2\}$$ or $$\{1,2,3\}$$ or $$\{1,2,3,4\}$$.
So... for every value $$0,1,2,3,4$$ there are sets with those number of elements and so $$f$$ of those sets will be equal to $$0,1,2,3,4$$ and so every value is mapped to, so it is onto.

$$f(\emptyset)=0$$, the function is onto. And definitely is not 1-1, because $$|P(\{1,2,3,4\})|>5$$.

• Oh my, I completely forgot about that! Thank you! Dec 3, 2022 at 3:20