2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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.... $\endgroup$
    – fleablood
    Dec 3, 2022 at 6:14
  • $\begingroup$ "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$. $\endgroup$
    – fleablood
    Dec 3, 2022 at 6:33

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Oh my, I completely forgot about that! Thank you! $\endgroup$
    – guti995
    Dec 3, 2022 at 3:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .