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!

Proving a piece-wise defined function is bijective.

  1. Mar 12, 2015 #1
    1. The problem statement, all variables and given/known data
    ##f:\mathbb{Z} \to \mathbb{N}##
    ## f(x) = \begin{cases} 2x+2 & \text{if } x \geq 0 \\ -2x-1 & \text{if } x < 0 \end{cases} ##
    Prove that f is a bijection from ##\mathbb{Z}## to ##\mathbb{N}##
    2. Relevant equations


    3. The attempt at a solution
    Proving that it is an injection if quite simple. Proving it is a surjection is where i get confused.

    Let ##y\in\mathbb{N} \text{ and } x \in \mathbb{Z}##

    If ##x \geq 0 \text{ then } y=2x+2 ~~\Rightarrow~~ x=\frac{y-2}{2} ##
    if ##y\geq 2 \text{ then } f(\frac{y-2}{2})=2(\frac{y-2}{2})+2=y##
    if ##y<2 \text{ then } f(\frac{y-2}{2})=-2(\frac{y-2}{2})-1=1-y##

    If ##x<0 \text{ then } y=-2x-1 ~~\Rightarrow~~ x=\frac{-(y+1)}{2}##
    if ## y \geq -1 \text{ then } f(\frac{-(y+1)}{2})=2(\frac{-(y+1)}{2})+2=1-y##
    if ## y<-1 \text{ then } f(\frac{-(y+1)}{2}) = -2(\frac{-(y+1)}{2})-1=y##

    I'm pretty sure there should only be 2 or at most 4 cases that i need to investigate but i have 6. So im clearly doing something wrong... Could someone help me out please?
     
    Last edited: Mar 12, 2015
  2. jcsd
  3. Mar 12, 2015 #2

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    For the surjection, why not consider the cases where y is even and odd.
     
  4. Mar 12, 2015 #3
    Ahhh thank you PeroK! I'm certain i was thinking that on the bus home, and then i lost the thought and couldn't find it again. Thank you for reminding me!

    Just an aside; Is my method even valid? i dont know what to make of the 1-y results.. does this matter?
     
  5. Mar 12, 2015 #4

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    If I could follow your method, I'd tell you.

    Normally, if you're trying to show something is a surjection onto a set Y, you would start with:

    Let ##y \in Y##

    Then find the relevant ##x \in X##
     
  6. Mar 12, 2015 #5
    So if I split the problem into whether y is odd or even will I end up dealing with four cases?

    1. y is odd and y is less than or equal to 1
    2. y is odd and y is greater than 1
    3. y is even and y is greater than or equal to 2
    4. y is even and y is less than 2

    This is how im thinking about it; The first two cases arise because y being odd leads to ##x=\frac{1-y}{2}## and if y <= 1 then x would be positive so i use 2x+2 but if y>1 then x is negative so i would use -2x-1. The same argument goes for the last two.

    I feel somewhere in that argument i am contradicting myself and in general don't have a whole lot of confidence in the way i have done things. Could you show me how the "y is odd" argument would look?
     
  7. Mar 12, 2015 #6

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You don't need four cases, only two. To get you started:

    Let ##y \in \mathbb{N}## be even. Then ##y = 2n## for some ##n \in \mathbb{N}##

    Can you take it from there?
     
  8. Mar 12, 2015 #7
    How does this look?

    Let ##y \in \mathbb{N}## be even. Then ##y=2n## for some ##n \in \mathbb{N}##
    ##y=2x+2 ~~\Rightarrow~~ x=\frac{y-2}{2}=\frac{2n-2}{2}=n-1##

    Let ##y \in \mathbb{N}## be odd. Then ##y=2n+1## for some ##n \in \mathbb{N}##
    ##y=-2x-1 ~~\Rightarrow~~ x=\frac{-(y+1)}{2}=\frac{-(2n+2)}{2}=-n-1##
     
  9. Mar 12, 2015 #8
    Thanks for all your help PeroK.
     
  10. Mar 12, 2015 #9

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    A couple of things.

    First, note that ##\mathbb{N} = {1, 2, 3 ...}##. So, you need to check your definition of an odd natural number for n = 1.

    Second, you're writing what I would call rough notes. These do not form a logical argument.

    Third, you haven't finished the proof. You've stopped half-way through.

    To take the even case a step further:

    Let ##y \in \mathbb{N}## be even. Then ##y = 2n## for some ##n \in \mathbb{N}##

    (Now, do your rough notes off to one side, then come back with:

    Let ##x = n - 1##

    ##x \in \mathbb{Z}## and ##f(x) = 2n = y##

    That is a formal proof (of the even case). Do you see the difference?
     
  11. Mar 12, 2015 #10
    I really appreciate the tips you are giving me! I'm just starting pure maths in uni and i need to become familiar with the procedures and formalism.

    So is this a little better?

    Let ##y \in \mathbb{N}## be even. Then ##y=2n## for some ##n \in \mathbb{N}##
    And let ##x=n-1~~\text{with}~~x\in\mathbb{Z}##
    ##f(x)=2(n-1)+2=2n=y##

    Let ##y \in \mathbb{N}## be odd. Then ##y=2n+1## for some ##n \in \mathbb{N}##
    And let ##x=-n-1~~\text{with}~~x\in\mathbb{Z}##
    ##f(x)=-2(-n-1)-1=2n+1=y##

    This shows that for every element of ##\mathbb{N}## there is a corresponding element of ##\mathbb{Z}## which f maps to it. Therefore f is a surjection of N onto Z.

    Is the conclusion sufficient or must it be altered? Also is it a good idea to make the "rough notes" part of the proof or at least visible?
     
  12. Mar 12, 2015 #11
    And regarding my definition of an odd number i would change it to;

    Let ##y \in \mathbb{N}## be odd. Then ##y=2n-1## for some ##n \in \mathbb{N}##
    And let ##x=-n~~\text{with}~~x\in\mathbb{Z}##
    ##f(x)=-2(-n)-1=2n-1=y##
     
  13. Mar 12, 2015 #12

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes, much better.

    A minor detail (I missed this too.) It's better to mention whether x is < 0 or not, so you know you're using the correct formula for f.

    Let ##x = -n##

    ##x \in \mathbb{Z}, x < 0 \ \ and \ \ f(x) = -2(-n) -1 = 2n - 1 = y##

    Re notes and proofs in general. You should ask your lecturers what they expect in an exam. What I do is work out the notes to one side then decide how much (if any) needs to be mentioned in the proof for clarity and justification.

    A brief recap at the end of exactly what you've shown is often worthwhile.
     
  14. Mar 12, 2015 #13
    If it is necessary to state the parity of x then does this mean there will be more cases I need to consider (i.e. if x<0 or x##\geq 0##)?

    Also I could tighten up the conclusion by writing instead: "this shows that##~~\forall~ y~\in\mathbb{N}\exists x~\in~\mathbb{Z}:f(x)=y## which if anyone else typeset would look more aesthetically pleasing to the eye...
     
  15. Mar 12, 2015 #14

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    No. But the sign of x tells you which formula to use. So, this justifies why you used the formula in each case.
     
  16. Mar 12, 2015 #15
    Ahh yes of course, I forgot that ##n\in\mathbb{N}## and not ##n\in\mathbb{Z}##.
    Thanks again for all your help PeroK.
     
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: Proving a piece-wise defined function is bijective.
Loading...