How do I prove sets are injective or surjective?

Question

Let be the set of all lists (of any length) whose entries are only 0’s and 1’s, and let be the set of nonnegative integers. Define a function : → as follows: for any list in , () = the number of 1’s in .

(a) Is one-to-one? Prove or give a counterexample.

(b) Is onto? Prove or give a counterexample.

I'm mostly confused as to what set would actually look like. I see it as being something like = {1,0,1,0,1,0...}. In which case is it true that can't be one-to-one because any 0 or a 1 from would map directly to only a 0 or 1 in ? Also could it be onto even both of these are infinite sets?

Answer 1

$S$ is a set of lists. So if one list is something like $(0,0,1,1,0)$, (I'll write list between parenthesis for notation), then $S$ is the set of all of these.

$S=\{(0),(0,0), (0,1),(1,0),(1,1),(0,0,0),(0,0,1),.... \}$

$T$ meanwhile is just $\mathbb N\cup \{0\}$.

And $F:S\to T$ by "counting the $1$". So $F((0,0,1,1,0)) = 2$ and $F((1,0,1,1,1,1,1,0)) = 6$ for example.

In which case is it true that can't be one-to-one because any 0 or a 1 from would map directly to only a 0 or 1 in ?

It's not the $0$s and the $1$s that are being mapped from. It is the lists of $0$s and $1$s that are being mapped from.

And a function from a set $A$ to a different set $B$ don't have to map the same type of elements. Consider $A = \{\text{animals}\}$ and $B=\{\text{food\}}$ and $f:A\to B$ via $f(x)=$ what $x$ eats. Then $f(\text{horse})=\text{hay}$ even though hay is not an animal. So $f((1,1,0)) = 2$ which is neither $0$ nor $1$.

Also could it be onto even both of these are infinite sets?

The sets are infinite and you can have onto functions to infinite sets.

....

Now is $F$ one-to-one and is it onto.

Below are HUGE hints if you just put that question into simple words that make the answer UTTERLY obvious. Don't read it unless you are absolutely stuck:

One-to-one:

$F$ is one-to-one means the only time two lists $j,k$ have $F(j)=F(k)$ is if $j=k$. In other words, the only time two lists have the same number of $1$s is when they are the lists are the same. Is that true? If two lists have the same number of $1$s, do that mean the two lists are the same?

Onto:

$F$ is onto if for ever non-negative number there is a list with that many $1$s. Is there? Can you think of a number for which there is not a list with that many $1$s?

Answer 2

The set of lists is the set $\lbrace(0),(1),(0,1),(1,0),(0,0,1),...\rbrace$. Because $(1)$ and $(1,0)$ have the same number of $1$s the function is not 1-1 (injective). Because the set contains the list $(1,1,...,1,0)$ with $n$ $1$s (noting $n$ may be zero), there is at least one list for each number, so the function is onto (surjective).