I am trying to understand this exercise:
Let S be the set of all strings of 0's and 1's, and define f: S -> $Z^{nonneg}$ by f(s) = the length of s, for all string in S.
a. Is f one-to-one? The answer in the book is simply, no because f(0) = f(1) = 1 but 1 $\neq$ 0. I understand that there is an f(0) and an f(1) because of the strings of 0's and 1's but I don't see why f(0) = f(1). Could some one explain this?
b. Is f onto? According to the book: f is onto. Suppose n is a non-negative integer. It must be shown that there exists a string a in S such that f(s) = n. Let s = "the null string" if n = 0 and let s = 000...0 if n > 0. Then f(s) = the length of s = n, as was to be shown. I don't understand this answer.
It would be great if someone could help me understand one or both of these.
Thanks for any help,
Tony
I try to explain both answer (a) and answer (b). So set of strings of 0's and 1's could look like this 01111100001; the function f by definition maps such a sequence to a (non-negative integer) namely to "(number of 0's in the string) + (number of 1's in the string)". In my example 01111100001 there are five 0's and six 1's, hence f(01111100001)=5+6=11.
Now, in the string 0 there is one "0" and no "1", hence f(0)=1+0=1. On the other hand, in the string 1 there is no "0" and one "1", hence f(1)=0+1=1. Thus f(0)=f(1).
Why is it onto? Consider a positive integer $n$ for this consider the string $\underbrace{(0,0,0\ldots0)}_n$, then we have that f$((0,0,0\ldots0))$=n+0=n. Moreover, usually one considers the zero string " " to be a string as well, and this is mapped by f to 0. Hence the function f is onto the set of all non-negative integers.