12 Let S be the set of all strings in 0s and 1s and define a

12. Let S be the set of all strings in 0’s and 1’s, and define a function g: S Z as follows: for each string s in S, g(s) = the number of 0’s in s. (a) What is g(101011)? g(00100)? (b) Is g one-to-one? Prove or give a counterexample. (c) Is g onto? Prove or give a counterexample.

Solution

a)

g(101011)

number of 0’s in s = 2 [simply count them]

g(00100)

number of 0’s in s = 4 [simply count them]

b)

A function f from A to B is called one-to-one (or 1-1) if whenever
f (a) = f (b) then a = b.   No element of B is the image of more than one element in A.

So

Yes, g(10) = 1 = g(01)

c)

A function f from A to B is called onto if for all b in B there is an a in A

such that f (a) = b.   All elements in B are used.

So

no.
g(10) = 1.
g(n 0s in a row) = n
g(n 1s in a row) = n.