Let S be the set of all strings of 0’s and 1’s, and define D:S -> Z as follows: For all S in S, D(s)= the number of 1’s in s minus the number of 0’s in s.

a. Is D one-to-one? Prove or give a counterexample.

b. Is D onto? Prove or give a counterexample.

Step 1

DEFINITIONS

A function F from A to B satisfied the following two properties:

- For every element x in A, there exists an element y in B such that (x,y) in F.

- If (x,y) in F and (x,z) in F, then y=z (thus an element in A cannot have two different images).

A is called the domain, while B is called the codomain.

The function f is one-to-one if and only if f(a)=f(b) implies that a=b for all a and b in the domain.

The function f is onto if and only if for every element B in B there exist an element a in A such that f(a)=b.

Step 2

SOLUTION

D:S rightarrow z

S= Set of all strings

D(s)= Number of 1's in s minus the number of 0's in s

a) Not one-to-one

D is not one-to-one, which we will justify with a counterexample.

COUNTEREXAMPLE

Let us consider the strings 10 and 01.

Both strings contain one 1 and one 0, thus their image is 0 (as 1-1=0).

D(10)=0=D(01)

However, the strings 10 and 01 are not the same, while their images are the same. By the definition of one-to-one, D is then not one-to-one.

Step 3

b) Onto

D is onto, which we will justify with a proof.

To proof: D is onto

PROOF

Let x in Z. We will need to find an element in the domain S that has x as its image. If such an element exists (for any x in the codomain), then D is onto.

First case x=0

The string 01 has one 1 and one 0, thus the image of the string is 1-1=0

D(01)=1-1=0

Second case x>0

NSK

Let us consider the string 0^-x which is the string consisting of no ones and -x zeros. Thus the image of the string 0^x is then 0-(-x)=x

D(0^x)=0-(-x)=x

Thus 01 or 1^x or 0^x (choice dependent on value of x) is some element in the domain which has x as its image and this then implies that D is onto.

Step 1

The objective is to determine whether D is one-one or not and D is on-to or not.

Where, S bet the set of all strings of 0's and 1's, and define D:S -> Z for all s belongs S and D(s)= the number of 1's in s - the number of 0's in S.

Step 2

No, D is not 1-1,

Since, if number of 1's is 5 and number is 0's is 2 then D=5-2=3.

If number of 1's is 8 and number of 0's is 5 then D=5-2=3

Hence, D is not one-one.

Yes, D is onto because for every element of D(s) there exist pre-image of the element. That means for every D= the number of 1's in s - the number of 0's in S

There exists element in S.

Hence, D is on-to.

a) seems easy enough.

D(s_i)=5[ones]-5[zeros]=0; s_i in S

D(s_j)=6[ones]-6[zeros]=0; s_j in S

s_i ne s_s

thus not 1-1

b) It seems to be true.

only proof I could think up would to be

let s_k in S

such that the numbers of ones is and zeros in

s_k

is k_1, k_0 in Z respectively.

now, D(s_k)=k_1-k_0

and because integers have closure under subtraction

k_1-k_0=k_z

such that k_z in Z

therefore D(s) is an onto function.