1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Jul 20, 2014 #1
    1. The problem statement, all variables and given/known data

    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

    2. Relevant equations



    3. The attempt at a solution

    a) seems easy enough.

    [tex]D(s_{i}) = 5[ones]-5[zeros]=0; s_{i} \in S[/tex]

    [tex] D(s_{j}) = 6[ones]-6[zeros] = 0; s_{j} \in S[/tex]
    [tex]s_{i} \neq s_{s}[/tex]

    thus not 1-1

    b) It seems to be true.

    only proof I could think up would to be

    let [tex] s_{k} \in S[/tex] such that the numbers of ones is and zeros in [tex]s_{k}[/tex] is [tex]k_{1}, k_{0} \in \mathbb{Z}[/tex] respectively.

    now, [tex] D(s_{k}) = k_{1} - k_{0}[/tex]

    and because integers have closure under subtraction [tex]k_{1} - k_{0} = k_{z}[/tex] such that
    [tex]k_{z} \in \mathbb{Z}[/tex]

    therefore D(s) is an onto function
     
  2. jcsd
  3. Jul 20, 2014 #2

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    This is not correct. You need to show that for any [tex]k \in \mathbb{Z}[/tex] there is an s in S such that D(s) = k.
     
  4. Jul 20, 2014 #3

    let [tex] k \in Z[/tex] such that [tex] D(s) = k[/tex]

    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]
     
  5. Jul 20, 2014 #4
    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?
     
  6. Jul 20, 2014 #5
    let k be any integer

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

    now,
    D(s) = (k+j) - j = k
     
  7. Jul 20, 2014 #6
    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.
     
  8. Jul 20, 2014 #7
    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.
     
  9. Jul 20, 2014 #8
    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.
     
  10. Jul 20, 2014 #9
    I'm not sure what you mean by too general. only patterns I see is if theres more zeros then k is negative, if theres 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
     
  11. Jul 20, 2014 #10

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    There are some simpler strings you could try. For example, what are D(1), D(11), D(111), ...?
     
  12. Jul 20, 2014 #11
    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 thats 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
     
  13. Jul 20, 2014 #12
    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.
     
  14. Jul 20, 2014 #13
    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
     
  15. Jul 20, 2014 #14
    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?
     
  16. Jul 20, 2014 #15
    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?
     
  17. Jul 20, 2014 #16

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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##?
     
  18. Jul 20, 2014 #17
    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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: D: S --> Z, the string of all 1's and zeros
  1. D/ds s/sqrt(60s + 25) (Replies: 1)

Loading...