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) F (001000) = 1, F (111001) = 4, F (10101) = 3, F (0100) = 1 b) No c) Yes d) No

Step-by-step explanation:

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.