how to show a function is bijection I have taken two numbers $p$ and $r$ where $p,r\in A = \{0,1,\ldots,4i + 1\}$ where $i\geq 1$ and $q\in B = \{0,1,\ldots,n-1\}$. Let
$X$ contains all elements obtained by cartesian product of $A$ and $B$. I defined $G = \{(p,q) : p+q ~is~ even\}$ and $H = X\backslash  G$. We defined
a function $f : G \longrightarrow H$ by $f(p,q) = (r,q)$ where
\begin{eqnarray*}
r = \begin{cases}
     p+1 & \text{if $p\leq m-2$}\\
     0 & \text{if $p = m-1$}
     \end{cases}
\end{eqnarray*}
where $m = 4i +2$.
I am trying to show that this $f$ is bijection. To prove one-one, I have to prove
$f(p_1,q) = f(p_2,q)$ $\Leftrightarrow$ $(p_1,q) = (p_2,q)$.
now let $f(p_1,q) = f(p_2,q)$. If $p_1$ and $p_2$ both $\leq m -2 $ then $f(p_1,q) = f(p_2,q)$ $\Rightarrow$ $(p_1 +1,q) = (p_2 +1,q)$ $\Rightarrow$ $p_1 = p_2$ and thus $(p_1,q) = (p_2,q)$. If $p_1$ and $p_2$ both = $m-1$ then $f(p_1,q) = f(p_2,q)$  $\Rightarrow$ $(0,q) = (0,q)$ and this implies that both $p_1$
and $p_2$ are $0$. Thus $(p_1,q) = (p_2,q)$. Again if exactly one of them is equal to $m-1$ (say $p_1$) and other is $\leq m-1$ then
$f(p_1,q) = f(p_2,q)$  $\Rightarrow$ $(0,q) = (p_2 +1,q)$ which implies that $p_2 = -1$. Not possible. So this case wont arise. I am not able to prove onto. Is my proof
to show one-one correct? Please rectify me if am doing wrong somewhere.
 A: Actually, to prove that $f$ is injective, you have to show that $f(p_1,q_1)=f(p_2,q_2)$ implies $(p_1,q_1)=(p_2,q_2)$. But since $f(p,q)=(r,q)$, then this immediately implies $q_1=q_2$. The rest of the argument you gave shows that $p_1=p_2$, thus $(p_1,q_1)=(p_2,q_2)$.
For the surjectivity, let $(r,q)\in H$. Let's find $p$ such that $(p,q)\in G$ and $f(p,q)=(r,q)$. We have two cases:


*

*$r=0$. In this case, let $p=m-1$. Since $(r,q)\in H$, then $r+q=q$ is odd, so $m-1+q=4i+1+q$ is even, that is, $(p,q)\in G$. Clearly, $f(p,q)=(r,q)$.

*$r\neq 0$. In this case, let $p=r-1$. Notice that, since $(r,q)\in H$, then $r+q$ is odd, so $p+q$ is even, that is, $(p,q)\in G$. Also, $p=r-1\leq 4i=m-2$, so $f(p,q)=(p+1,q)=(r,q)$, by definition of $f$.
In any case, $(r,q)$ is in the image of $f$, therefore $f$ is surjective.

To understand what $f$ is doing, notice that, since $f$ fixates the second coordinate, it is sufficient to analyse the "restrictions" $f_q(p)=f(p,q)$, where $f_q$ is defined for $p$ such that $(p,q)\in G$.
Given a fixed $p$, the set $A$ has an even amount of consecutive numbers $0,1,\ldots,4i+1$, so we can divide $A$ in two sets, $A_0=\left\{0,2,\ldots,4i\right\}$ and $A_1=\left\{1,3,\ldots,4i+1\right\}$, one with the elements that when summed to $q$ give an even result and the other consisting of the elements which give odd results. Both $A_0$ and $A_1$ have 2i elements, and a simple bijection from $A_i$ to $A_{1-i}$ is given in the following way: "take the largest element of $A_i$ and send to the least element of $A_{1-i}$. Take the other elements of $A_i$ and add $1$, thus obtaining the other elements of $A_{1-i}$".
That is exactly what $f_q$ does. So each $f_q$ is a bijection, hence $f$ is a bijection.
