1. Not finding help here? Sign up for a free 30min 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!

1:1 and onto proof of Z+ and Q+

  1. Apr 29, 2014 #1
    1. The problem statement, all variables and given/known data
    After exploring this problem a bit out of curiosity I decided to attempt to write a full fledged proof of it for my final exam.
    I will try my best to explain what I am doing. i am pretty frustrated with it but I've put so much time into it I don't want to give up and do something else now.

    For this theorem Equality in Q+: [itex]\frac{a}{b}[/itex]=[itex]\frac{c}{d}[/itex] [itex]\Leftrightarrow[/itex] a=c, and b=d

    now I'm using the grid system, i.e.
    1/1 1/2 1/3 1/4 1/5 1/6..
    2/1 2/2 2/3 2/4 2/5 2/6..
    3/1 3/2 3/3 3/4 3/5 3/6..
    .
    .
    but adjusting it to represent the diagonals and defining it as follows
    1/1 [itex]\Rightarrow[/itex] p+q=2 (1 element)
    1/2 2/1 [itex]\Rightarrow[/itex] p+q=3 (2 elements)
    1/3 2/2 3/1 [itex]\Rightarrow[/itex] p+q=4 (3 elements)
    etc
    as you can see each list represent one diagonal of the grid

    next I went to the integers by observing the following number line and looking at the sums that represent the integers

    (-----|](--|-----|](---|-----|-----|](---|-----|-----|-----|]-----|-----|
    0 1 2 3 4 5 6 7 8 9 10 11 12

    Representing each section with a summation we get
    (0,1]
    [itex]\sum^{1}_{k=1}[/itex]k
    (1,3]
    [itex]\sum^{2}_{k=1}[/itex]k
    (3,6]
    [itex]\sum^{3}_{k=1}[/itex]k
    (6,10]
    [itex]\sum^{4}_{k=1}[/itex]k

    now I'm trying to show f:Z[itex]^{+}[/itex][itex]\rightarrow[/itex] Q[itex]^{+}[/itex]
    f(1) = 1/1

    let n[itex]\geq[/itex]2[itex]\in[/itex]Z[itex]^{+}[/itex]
    let S[itex]_{n}[/itex]={s[itex]\in[/itex]Z[itex]^{+}[/itex][itex]\leq[/itex][itex]\sum^{j}_{k=1}[/itex]k}

    then consider 2n [itex]\sum^{2n}_{k=1}[/itex]k= 1+2+...+n+n+1+...+2n
    thus n[itex]\leq[/itex][itex]\sum^{2n}_{k=1}[/itex]k
    therefore 2n[itex]\in[/itex]S[itex]_{n}[/itex] therefore S[itex]_{n}[/itex][itex]\neq[/itex][itex]\oslash[/itex]
    Then by the well ordering principle [itex]\exists[/itex] m[itex]\in[/itex]S[itex]_{n}[/itex] [itex]\exists[/itex] m[itex]\leq[/itex]j [itex]\forall[/itex]j[itex]\in[/itex]S[itex]_{n}[/itex]

    i.e exists a "least" element
    Call the least element M

    therefore
    [itex]\sum^{m-1}_{k=1}[/itex]k<n[itex]\leq[/itex][itex]\sum^{m}_{k=1}[/itex]k
    or in other words m[itex]\in[/itex] ([itex]\sum^{m-1}_{k=1}[/itex]k, [itex]\sum^{m}_{k=1}[/itex]k]

    so let p= n-[itex]\sum^{m-1}_{k=1}[/itex]k
    1[itex]\leq[/itex]p[itex]\leq[/itex]m

    then choose a q such that p+q = m+1
    q= m+1-p

    now f(n) = p/q
    That ends the mapping

    Now show f:Q[itex]^{+}[/itex][itex]\rightarrow[/itex]Z[itex]^{+}[/itex] is 1:1 and onto.
    This is where I can't finish the proof but this is what I have of an attempt on both

    One to one:
    x[itex]_{1}[/itex][itex]\neq[/itex]x[itex]_{2}[/itex] [itex]\Rightarrow[/itex] f(x[itex]_{1}[/itex])[itex]\neq[/itex]f(x[itex]_{2}[/itex])
    or
    f(x[itex]_{1}[/itex])=f(x[itex]_{2}[/itex])[itex]\Rightarrow[/itex] x[itex]_{1}[/itex]=x[itex]_{2}[/itex]

    suppose f(n[itex]_{1}[/itex])=f(n[itex]_{2}[/itex])

    then [itex]\frac{p_{1}}{q_{1}}[/itex]=[itex]\frac{p_{2}}{q_{2}}[/itex]
    I have no idea how to get from here to n[itex]_{1}[/itex]=n[itex]_{2}[/itex]

    Onto:
    consider p+q
    the diagonals the p/q is in has the property that the # of elements in that diagonal is p+q-1 (referring way back to the beginning)
    or in other words ([itex]\sum^{p+q-2}_{k=1}[/itex]k, [itex]\sum^{p+q-1}_{k=1}[/itex]k]
    then let n= p+[itex]\sum^{p+q-2}_{k=1}[/itex]k

    and then I get hung up again
     
  2. jcsd
  3. May 1, 2014 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    You seem to prove some unnecessary or trivial stuff while other parts are wrong.

    So ##\frac{1}{2}=\frac{2}{4} \Leftrightarrow## 1=2 and 2=4? That is wrong.

    What does that mean?

    I guess the sum is supposed to run up to n instead of j?
    Okay, so as an example:
    S3 = {1,2,3,4,5,6}
    It is obvious that Sn is not empty (as an example, it always contains 1) and that it has a smallest element (it always contains 1 and 1 is the smallest number in Z+).

    Why should ##n \leq \sum^{1}_{k=1} k = 1## be true?

    This plus the wrong way to start make it impossible to finish your mapping or show that it has the desired properties.
     
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: 1:1 and onto proof of Z+ and Q+
  1. 1-1 and onto functions (Replies: 6)

Loading...