Let S be the set of all strings in 0’s and 1’s, and define a function F : S →Z nonneg as follows: for all strings s in S, F(s) = the number of 1’s in s.
a. What is F(001000)? F(111001)? F(10101)? F(0100)?
b. Is F one-to-one? Prove or give a counterexample.
c. Is F onto? Prove or give a counterexample.
d. Is F a one-to-one correspondence? If so, find F−1 .

a) To get the values F(s), we see that there's one 1 in s=001000 (F(s)=1) , four 1's in s=111001 (F(s)=4), three 1's in s=10101 (F(s)=3) and one 1 in 0100 (F(s)=1).
b) Counterexample: let p=00110 and q=1100, so p,q ∈ S. p≠q because they differ on their first symbol, but F(p)=2=F(q). Then F is not one-to-one because different elements of S have the same value under F.
c) Proof: let n be a nonnegative integer. We'll construct a string s such that F(s)=n. If n=0, take s=00, since s doesn't have any 1's, F(s)=0=n. If n≠0, then n is a positive integer so we can construct the string s=111...1 which consists of n consecutive 1's. Then F(s)=n. We have shown that for every n∈Z nonneg, there exists s∈S such that F(s)=n, so by definition, F is onto.
d) An one-to-one correspondence is both one to one and onto, but part b) shows that F is not one-to-one. F^-1 only exists if F is a one-to-one correspondence.