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.

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.
