# Prove that f is a bijection

Deﬁne the function $$f : \{n \mid n = 3m − 1 \text{ for some } m \in \mathbb{Z}\} \rightarrow \{k \mid k = 4m + 2 \text{ for some } m \in \mathbb{Z}\}$$ by $$f(n)=\frac{4(n+1)}{3}-2$$ Prove that $f$ is a bijection.

I am aware that I need to prove $f$ is injective and surjective and therefore, a bijection. How should I approach this? (The lecturer has written "Backwards proof" on my script and marked my answer as incorrect)

Edit2 (switched incorrectly labelled domain and codomain)

if $$f(x) = f(y)$$ then $$\frac{4(x+1)}{3}-2 = \frac{4(y+1)}{3}-2$$ $$x = y \text{ }$$ Therefore the function is injective.

Let $$m \in \mathbb{Z} \text{, } 3m-1 \in \mathbb{D} \text{ (domain)}$$ $$m+1 \in \mathbb{Z} \text{, } 3(m+1)-1 \text{, } 3m+2 \in \mathbb{D}$$ $$f(3m+2) = \frac{4((3m+2)+1)}{3}-2$$ $$f(3m+2) = \frac{4(3m+3)}{3}-2$$ $$f(3m+2) = \frac{12m+12)}{3}-2$$ $$f(3m+2) = 4m+4-2$$ $$f(3m+2) = 4m+2$$ $$4m+2 \in \mathbb{C} \text{ (codomain)}$$ Therefore the function is surjective.

Since the function is injective and surjective, it is a bijection.

-
Could you show us your approach? – Alex Becker May 3 '12 at 5:15
The function maps the integer $3m-1$ to $4m-2$, which certainly is of the shape $4k+2$. The function $\frac{4(x+1)}{3}-2$ is strictly increasing, even on the reals, so injectivity is easy. Now pick a number of the shape $4k+2$. Who is taken there? – André Nicolas May 3 '12 at 5:19
Probably the simplest thing to do is to find the inverse of this function. Once you know it has an inverse function, it must be a bijection. – user22805 May 3 '12 at 5:21
@AlexBecker I have added my approach, perhaps you could tell me where I went wrong? Thank you. – Danny Rancher May 3 '12 at 5:58
@DannyRancher The first part is fine, if sparse on details. But the second shows simply that the function in fact maps its domain into its codomain (note on the first line where you say codomain you should say domain, and on the last line you should say codomain), not that it is surjective. – Alex Becker May 3 '12 at 6:05

Hint $\rm\:f\:$ is linear so $1\!-\!1.\:$ $\rm\:f(3\:\!\mathbb Z\!-\!1) = 4(3\:\!\mathbb Z\!-\!1\!+\!1)/3-2 = 4\:\!\mathbb Z\!-\!2 = 4\:\!\mathbb Z\!+\!2\:$ so $\rm\:f\:$ is onto.

-

First, note that the function is indeed well-defined: if $n=3m-1$, then $$f(n) = \frac{4(n+1)}{3}-2 = \frac{4(3m-1+1)}{3}-2 = \frac{4(3m)}{3} -2= 4m-2 = 4(m-1)+2$$ which is in the (alleged) codomain.

There are now two ways of showing this: either prove that $f$ is injective and onto; or prove that $f$ has an inverse.

The computation above might help to show the function is onto: if you take $4k+2$ in the image, what value of $n$ will give you $f(n) = 4k+2$?

It might also help with one-to-one: if $f(a)=f(b)$, with $a=3m-1$ and $b=3n-1$, then by the computations above we get $4m-2 = f(a) = f(b) = 4n-2$. What does that tell us about $a$ and $b$?

Alternatively: define $$g\colon \{k\mid k=4m+2\text{ for some }m\in\mathbb{Z}\}\to \{n\mid n=3m-1\text{ for some }m\in\mathbb{Z}\}$$ by letting $$g(4m+2) = 3(m+1)-1.$$ Verify that $f(g(4m+2)) = 4m+2$ and $g(f(3m-1)) = 3m-1$, proving that $g=f^{-1}$, so $f$ is bijective.

-