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.
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.
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.
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).
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.
D is onto, which we will justify with a proof.
To proof: D is onto
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
Second case x>0
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
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.
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.
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
is k_1, k_0 in Z respectively.
and because integers have closure under subtraction
such that k_z in Z
therefore D(s) is an onto function.