# Bijection construction

• Mar 16th 2009, 11:09 PM
namelessguy
Bijection construction
I always have trouble with constructing bijective function from one set to another set. I am asking for some advices so that I can somehow do this type of problem better
Say, I want to construct a bijection $\displaystyle f:N \rightarrow Z$.
I would define my function $\displaystyle f(x)=0$ if $\displaystyle x=1$,$\displaystyle \frac{x}{2}$ if $\displaystyle x$ is even, and $\displaystyle -\frac{x-1}{2}$ if $\displaystyle x$ is odd and greater than 1.
I can see clearly that this function maps the set of natural numbers to the set of integers. I can also check that this function is one-to-one and onto.
However, I have trouble with coming up with bijective constructions like those below:
1) $\displaystyle f:R \rightarrow (0,1)$ by $\displaystyle f(x)=\frac{tan^{-1}(x)}{\pi}+1/2$
2) $\displaystyle f: (0,1) \rightarrow R$ by $\displaystyle f(x)=1/x$ if $\displaystyle 0 < x \leq 1/2$, and $\displaystyle 4-\frac{2}{2x-1}$ if $\displaystyle 1/2 <x <1$.
3) $\displaystyle f: N \times N \rightarrow N$ by $\displaystyle f(x,y)=2^x(2y+1)-1$.
I just don't see the approach to obtain these bijective functions as other people see it. What kind of logical thoughts I need to have so that I can tackle these constructions? Also, how can I verify that the functions above are one-to-one and onto by using the definitions? Do I just do it the usual way, for injective, let f(x)=f(y) then show x=y, and for onto, show there exists x in A such that f(x)=y for every y in B (here I consider f from A to B)? Any suggestion and help is appreciated.
• Mar 17th 2009, 11:06 AM
Showcase_22
Quote:

Originally Posted by namelessguy
What kind of logical thoughts I need to have so that I can tackle these constructions?

I find these a little tricky too. I normally just look at a lot of them and try and understand why they work (or just memorise them).

Quote:

Also, how can I verify that the functions above are one-to-one and onto by using the definitions? Do I just do it the usual way, for injective, let f(x)=f(y) then show x=y, and for onto, show there exists x in A such that f(x)=y for every y in B (here I consider f from A to B)? Any suggestion and help is appreciated.
The easiest way of doing it after you have the "suspected" bijection is just to show it has an inverse. I find it's faster than using the definitions of injectivity and surjectivity.