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.
 A: 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 
!
A: So for your bijection $F$ (here what I wrote is actually your $F^{-1}$) $$\forall x\, x \in F^{-1} \iff x \in \{1,...,mn\} \times (A \times B) $$$$\ \wedge\, \exists a \in \{1,...,m\},\ b \in \{1,...,n\}\ $$$$x = (n * P(a) + b,\, (f(a),\,g(b)).$$
You would want to prove the following lemma:
$$\forall m,n \in N\ \forall x\, x \in \{1,..,mn\}\implies \exists a \in \{1,...m\}\,\exists b \in \{1,...n\}\ x = (n*P(a) + b)$$
and
$$\forall m,n \in N\ \forall x\, x \in \{1,..,mn\}\forall a,c \in \{1,...m\}\,\forall b,d \in \{1,...n\}\ $$$$x = (n*P(a) + b) \wedge x = (n * P(c) + d) \implies (a = c \wedge b = d).$$
This lemma is needed to prove that you have surjectivity (the first part) and injectivity (the second).
To rewrite the notation: We have $$\forall m,n, x\ \,x \in \{m,..,n\} \iff m \leq x \wedge x \leq n$$ where $$\forall a,b\ \, a \leq b \iff a,b \in N \wedge \exists c \in N\, b = a + c$$
also we have $$\forall a \in N\, a \neq 0 \implies S(P(a)) = a$$ where $S$ is effectively $\forall n \in N\,S(n) = n + 1$ and $P(n) = n - 1$ provided that $n \neq 0$
For example to take injectivity Suppose that $a \neq c$ (for example if $a < c$ then we have the following series of inequalities:
$$nP(a) + b <= nP(a) + n = n(P(a) + 1) = n (P(a) + S(0)) = n (S(P(a)+0)) = n(S(P(a)) = n*a < n*a + 1 <= n*P(c) + 1 <= n*P(c) + d$$
Here you should be able to justify all transitions.
A: Some context, perhaps of interest.
Want to find a bijection:
$f:${$ 0,1,2,.....,nm-1$} $\rightarrow X×Y$, 
where  $X=${$0,1,2.....n-1$},  and
$Y=${$0,1,2,....m-1$}.
$X×Y=$ {$(i, k)|$
$0\le i \le n-1, 0 \le k \le m-1$}
In  matrix form 
$(0,0) (0,1) (0,2).....(0,m-1)$
$(1,0) (1,1) (1,2).....(1,m-1)$
$ :$
$(n-1,0) (n-1,1)..(n-1,m-1)$.
Consider the dictionary order on the set $B:=X×Y$.
$A$ and $B$ have the same order type, if 
there exists a bijection $f: A \rightarrow B$ s.t.
$a_1 <_A  a_2 \Rightarrow f(a_1) <f(a_2)$.
Let $k \in {0,1,2,....,mn-1}.$
Euclidean division : 
$k= mq +r$, where $0 \le q$ , $0 \le r \lt m$, 
with unique $q, r$.
$f: A \rightarrow B.$
$f(k) = f(mq+r) =(q, r)$.
$f$ is bijective.
(https://en.m.wikipedia.org/wiki/Euclidean_division)
