D: S --> Z, the string of all 1's and zeros

[jonroberts74]

Homework Statement

Let S bet the set of all string's of 0's and 1's. define D: S --> Z as follows : for all s in S, D(s) = the numbers of 1's in s minus the number of 0's in s.

a) Is D 1-1? Prove or give counterexample
b) Is D onto? Prove or give counter example

Homework Equations

The Attempt at a Solution

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} \neq 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 \mathbb{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 \mathbb{Z}$$

therefore D(s) is an onto function

 

[PeroK]

Homework Statement

Let S bet the set of all string's of 0's and 1's. define D: S --> Z as follows : for all s in S, D(s) = the numbers of 1's in s minus the number of 0's in s.

a) Is D 1-1? Prove or give counterexample
b) Is D onto? Prove or give counter example


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 \mathbb{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 \mathbb{Z}$$

therefore D(s) is an onto function

This is not correct. You need to show that for any $$k \in \mathbb{Z}$$ there is an s in S such that D(s) = k.

 

[jonroberts74]

This is not correct. You need to show that for any $$k \in \mathbb{Z}$$ there is an s in S such that D(s) = k.

let $$k \in Z$$ such that $$D(s) = k$$

this is where I am stuck now. If I were dealing with a function like f(x) = y = 4x-1. I would solve for x, substitute that in and I'd be able to solve to get back to y.

here I have D(s) = k = [number of ones] - [number of zeros]

 

[Quesadilla]

let $$k \in Z$$ such that $$D(s) = k$$

this is where I am stuck now. If I were dealing with a function like f(x) = y = 4x-1. I would solve for x, substitute that in and I'd be able to solve to get back to y.

here I have D(s) = k = [number of ones] - [number of zeros]

No. You start by taking an arbitrary $k \in \mathbb{Z}$. Then you need to find a string $s$ in $S$ such that $D(s) = k$. Can you find such a string?

 

[jonroberts74]

let k be any integer

let s in S have (k+j) ones and j zeros

now,
D(s) = (k+j) - j = k

 

[Quesadilla]

let s have (k+j) ones and j zeros

D(s) = (k+j) - j = k

You are on the right track, but what is $j$ here? Do you need it? It might also help if you consider the cases $k>0$, $k<0$ and $k=0$ separately.

 

[jonroberts74]

If k > 0 then number of ones > number of zeros

if k = 0 then number of ones = the number zeros

if k < 0 then number of ones < number of zeros

and so j is the value difference between number of ones and number of zeros. I'm not sure How I could show it without using it.

 

[gopher_p]

I don't mean to butt in, but I think you're maybe trying to be a little too general and making this more difficult than it really is. You just need to find, for each $k$, one string $s$ satisfying $D(s)=k$. I would encourage you to write down a few specific examples; find specific strings - i.e. write down strings of $0$s and $1$s - satisfying $D(s)=1$, $D(s)=-1$, $D(s)=2$, $D(s)=-2$ ... Try to find a pattern that works - it's been suggested that the "easiest" patterns may be different for positive and negative numbers - and go with it.

 

[jonroberts74]

I don't mean to butt in, but I think you're maybe trying to be a little too general and making this more difficult than it really is. You just need to find, for each $k$, one string $s$ satisfying $D(s)=k$. I would encourage you to write down a few specific examples; find specific strings - i.e. write down strings of $0$s and $1$s - satisfying $D(s)=1$, $D(s)=-1$, $D(s)=2$, $D(s)=-2$ ... Try to find a pattern that works - it's been suggested that the "easiest" patterns may be different for positive and negative numbers - and go with it.

I'm not sure what you mean by too general. only patterns I see is if there's more zeros then k is negative, if there's an equal amount of ones and zeros then k = 0 and if there are more ones then k is positive which is what I said in my last post.

101010 would yield k = 0

1100110 yields k =1

and 1000101 yields k = -1

 

[jbunniii]

I'm not sure what you mean by too general. only patterns I see is if there's more zeros then k is negative, if there's an equal amount of ones and zeros then k = 0 and if there are more ones then k is positive which is what I said in my last post.

101010 would yield k = 0

1100110 yields k =1

and 1000101 yields k = -1

There are some simpler strings you could try. For example, what are D(1), D(11), D(111), ...?

 

[jonroberts74]

they'd be k =1,2,3 respectively and they contain no zeros. so there's strings that have no ones or no zeros but that's covered

if k < 0 then number of ones < number of zeros and If k > 0 then number of ones > number of zeros

seems to me the best is still to say

let s in S such that s has (k+j) ones and j zeros where k,j in Z

now D(s) = (k+j) - j = k

 

[Quesadilla]

Okay. So the definition of onto is: A function $f : A \rightarrow B$ is said to be onto if, for every $b \in B$ there is an $a \in A$ such that $f(a) = b$.

Your job is then to take an arbitrary $k \in \mathbb{Z}$ which you fix and then find a string $s$ in $S$ such that $D(s) = k$. Since your $k$ was chosen arbitrarily, it must then hold for all $k$ in $\mathbb{Z}$. Given a fixed $k$ you only need to find ONE string. When you introduce $j$ you are introducing a whole family of strings, which is not necessary and thus looks bad.

You also forgot to consider the cases when either $(j + k)$ or $j$ is negative.

 

[jonroberts74]

okay I see the issue with j.

one string could be

11111 and D(11111)=5, 5 in Z

like that? almost like finding a counterexample

 

[Quesadilla]

okay I see the issue with j.

one string could be

11111 and D(11111)=5, 5 in Z

like that? almost like finding a counterexample

No. You need to treat all $k$ at the same time. I will try to outline it for you.

"We take any $k \in \mathbb{Z}$. Now consider the string $s = ?$ in $S$. Then $D(s) = k$."

I suggested that it would be easier to find strings if we consider the cases $k>0$, $k<0$ and $k= 0$ separately. Then the proof could look something like:

"Take any $k$ in $\mathbb{Z}$. Then exactly one of $k>0$, $k<0$ and $k=0$ is true. We will consider each case separately.

First, if $k=0$, we take the string $s = 10.$ Then $D(s) = 0 = k$.

Second, if $k>0$, we take the string $s = ...$

Third, if $k < 0$, ..."

Can you fill in the dots?

 

[Quesadilla]

Actually, let me give a simple example where I prove that a function is onto.

Consider the function $g : \mathbb{Z} \rightarrow \mathbb{Z}$ given by $g(k) = k + 1.$ Show that $g$ is onto.

Solution: Take any $k \in \mathbb{Z}$ (the codomain). We need to find an element $l$ in $\mathbb{Z}$ (the domain) such that $g(l) = k$. Therefore, take $l = k - 1$. Then $g(l) = g(k - 1) = k - 1 + 1 = k$.

Look at the definition of onto that I wrote in an above post. Can you see why the argument I just gave shows that $g$ is onto?

 

[jbunniii]

they'd be k =1,2,3 respectively and they contain no zeros. so there's strings that have no ones or no zeros but that's covered

if k < 0 then number of ones < number of zeros and If k > 0 then number of ones > number of zeros

seems to me the best is still to say

let s in S such that s has (k+j) ones and j zeros where k,j in Z

now D(s) = (k+j) - j = k

Well, to prove surjectivity, you only need one example for each $k$. Seems to me the simplest string that works for a given positive $k$ is simply the string containing $k$ ones and no zeros. What about for negative $k$?

 

[jonroberts74]

Well, to prove surjectivity, you only need one example for each $k$. Seems to me the simplest string that works for a given positive $k$ is simply the string containing $k$ ones and no zeros. What about for negative $k$?

for a negative k, it would be a string containing all zeros and no ones,

for a k = 0, the string would contain equal number of ones and zeros