Finding a bijection from $\{1,2,...,nm\}$ to $X \times Y$ I'm trying to prove that for two finite sets $X,Y$, where $|X|=n$, $|Y|=m$, $|X||Y|=|X \times Y|$. I know that there exists bijections $f:\{1,2,...,n\} \rightarrow X$ and $g:\{1,2,...,m\} \rightarrow Y$ and I'm trying to find a bijection $h:\{1,2,...,nm\} \rightarrow X \times Y$. I know that this is equivalent to showing there exists a bijection $k: X \times Y \rightarrow \{1,2,...,nm\}$. One such bijection that seemingly works is $k(x_i,y_j) = (i-1)m + j$, where $1 \leq i \leq n$ and $1 \leq j \leq m$. I've tried to prove the injectivity and surjectivity of this function but to no avail:
Injecivity: Suppose $k(x_a,y_b) = k(x_c,y_d)$ for $x_a, x_c \in X$ and $y_b, y_d \in Y$. This gives $(a-1)m + b = (c-1)m + d$ but I've not been able to show that $a = c, b = d$ from here.
Surjectivity: Suppose $z \in \{1,2,...,nm\}$ then $\exists i,j$ s.t. $ z = (i-1)m + j$ for some $i,j$ satisfying $1 \leq i \leq n$ and $1 \leq j \leq m$. Now, since $X, Y$ can be written as $X = \{x_1,x_2,...,x_n\}$, $Y = \{y_1,y_2,...,y_m\}$ and  $X \times Y  = \{(x,y) | x \in X \wedge y \in Y\}$ then we can say $\exists(x_i, y_j) \in X \times Y$ and by the definition of $k$ we have $k((x_i, y_j)) = (i-1)m + j$. But I'm not sure if this all watertight since I've assumed that $z$ can be written in the desired form.

First let me do a little change: instead of $\{1,2,...,n\},\{1,2,...,m\},\{1,2,...,nm\}$ I will use $\{0,1,...,n-1\},\{0,1,...,m-1\},\{0,1,...,nm-1\}$.
Now, to prove $k$ is bijective I will find the inverse of $k$: $k(x_i,y_j)=(i-1)m + j$, to isolate $i$ I will use the fact that $j<m$, first let's divide by $m$: $\frac{(i-1)m + j}m=i-1 + \frac jm$, now notice that $i-1$ is an integer and $\frac jm$ is a fraction, so if I use the floor function on this expression I will get rid from $j$:$\lfloor i-1 + \frac jm\rfloor=i-1$, now adding to this $1$ we get $$\left\lfloor\frac{k(x_i,y_j)}{m}\right\rfloor+1=i\implies f^{-1}\left(\left\lfloor\frac{k(x_i,y_j)}{m}\right\rfloor+1\right)=x_i$$
Now we can easily isolate the $j$: $k(x_i,y_j)=(i-1)m + j=\left(\left\lfloor\frac{k(x_i,y_j)}{m}\right\rfloor+1-1\right)m+j=\left\lfloor\frac{k(x_i,y_j)}{m}\right\rfloor m+j\\\implies j=k(x_i,y_j)-\left\lfloor\frac{k(x_i,y_j)}{m}\right\rfloor m$
With this we only left to do is to use the inverse of $g$:$$j=k(x_i,y_j)-\left\lfloor\frac{k(x_i,y_j)}{m}\right\rfloor m\implies g^{-1}\left(k(x_i,y_j)-\left\lfloor\frac{k(x_i,y_j)}{m}\right\rfloor m\right)=y_j$$
Combining those 2 we get $$k^{-1}(z)=\left(f^{-1}\left(\left\lfloor\frac{z}{m}\right\rfloor+1\right),g^{-1}\left(z-\left\lfloor\frac{z}{m}\right\rfloor m\right)\right)$$
Thus we can conclude that $k$ is bijective

Here is a different proof that use induction.
It is trivial that $X\times \{a\}$ is the same size as $\{0,1,...,n-1\}$
Assuming that $X\times Y$ is the same size $\{0,1,...,nm-1\}$ I'll show that $X\times (Y\cup \{a\})$ where $a\notin Y$ is the same size of $\{0,1,...,n(m+1)-1\}$:
Let's call $h$ the bijective from $X\times Y$ to $\{0,1,...,nm-1\}$, then set $k(x_i,y_j)=h(x_i,y_j)$ if $(x_i,y_j)\in X\times Y$ and $k(x_i,y_j)=nm-1+i$ elsewhere, try to show that $k$ is bijective from $X\times (Y\cup \{a\})$ to $\{0,1,...,n(m+1)-1\}$ and then you are done with the induction 
!
