Let $S$ be the set of all strings in 0's and 1's, and define a function $F : S \rightarrow \mathbf { Z } ^ { \text {nonneg } }$ as follows: for all strings $s$ in $S$,
$$F ( s ) = \text { the number of } 1 \text { '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 }$.

Question

Quizplus · Accepted Answer

The Answer is a.

F (001000) = 1 \quad F (111001) = 4 \quad F (10101) = 3 \quad F ( 0100 ) = 1

b.

F

is not one-to-one.
$a. F (001000) = 1 \quad F (111001) = 4 \quad F (10101) = 3 \quad F ( 0100 ) = 1 b. F is not one-to-one. F ( 001000 ) = 1 and F ( 0100 ) = 001000 but 0 eq 0100 . [This is one counterexample among many.] c. F is onto. Let n be any nonnegative integer. [We must show that there is a string whose image \underline { u n d e r } F is n.J If n is positive, let s be the string with n 1 's and no 0's. Then F ( s ) = n . If n = 0 , let s be the string with one 0 . Then F ( s ) = 0 = n . Thus regardless of whether n is positive, negative, or zero, it is possible to find a string s such that g ( s ) = n [ a s was to be shown]. d. F is not a one-to-one correspondence because it is not one-to-one.$

F ( 001000 ) = 1

and

F ( 0100 ) = 001000

but

0 eq 0100

.
[This is one counterexample among many.]
c.

F

is onto.
$a. F (001000) = 1 \quad F (111001) = 4 \quad F (10101) = 3 \quad F ( 0100 ) = 1 b. F is not one-to-one. F ( 001000 ) = 1 and F ( 0100 ) = 001000 but 0 eq 0100 . [This is one counterexample among many.] c. F is onto. Let n be any nonnegative integer. [We must show that there is a string whose image \underline { u n d e r } F is n.J If n is positive, let s be the string with n 1 's and no 0's. Then F ( s ) = n . If n = 0 , let s be the string with one 0 . Then F ( s ) = 0 = n . Thus regardless of whether n is positive, negative, or zero, it is possible to find a string s such that g ( s ) = n [ a s was to be shown]. d. F is not a one-to-one correspondence because it is not one-to-one.$ Let

n

be any nonnegative integer. [We must show that there is a string whose image

\underline { u n d e r } F

is n.J If

n

is positive, let

s

be the string with

n 1

's and no 0's. Then

F ( s ) = n

. If

n = 0

, let

s

be the string with one 0 . Then

F ( s ) = 0 = n

. Thus regardless of whether

n

is positive, negative, or zero, it is possible to find a string

s

such that

g ( s ) = n [ a s

was to be shown].
d.

F

is not a one-to-one correspondence because it is not one-to-one.

Let SSS Be the Set of All Strings in 0's and 1's

Let $S$ Be the Set of All Strings in 0's and 1's