Bijection proof. Let $A$ and $B$ be finite sets, prove that $|A\times B|=|A||B|$.
Since $A$ and $B$ are finite sets, then it can be represented as follows, $$A=\{a_1,\ldots,a_m\}\quad \text{and}\quad B=\{b_1,\ldots, b_n\}$$ Then i defined a function $$\varphi:A\times B\to \{1,2,3,\ldots,mn\}=I_{mn}$$ given by $$\varphi(a_i,b_j)=(i-1)n+j$$ Who helps me to prove or how to prove that this function is indeed bijective.
 A: I think you should to prove that:

Given natural numbers $m$ and $n$ and let $f: \mathbb{N}_{m} \times \mathbb{N}_{n}\to \mathbb{N}_{mn}$, by $$f(i,j)=(i-1)n+j$$So, $f$ is a bijection.

You can use the division theorem, for example you might have to handle numbers $\mathbb{N}_{mn}$ that are divisible by $n$ as separate case.
Another approach [1]: You can prove that if $A$ and $B$ are finite sets, then $A\times B$ is finite set and $$|A\times B|=|A||B|$$ using the following steps:

*

*If $\{b\}$ is a singleton, then $|A\times \{b\}|=|A|$.

*If $B=\{b_{1},b_{2},\ldots,b_{n}\}$, then $$A\times B=\bigcup_{i=1}^{n}\left(A\times \{b_{i}\}\right)$$

*Finally, you can conclude that $$|A\times B|=mn=|A||B|$$
Another approach [2]: You can use induction on $|B|$. It's to say, prove that $$\forall n \in \mathbb{N}, \forall A,B: |A|,|B|<\infty \wedge |B|=n \implies |A\times B|<\infty \wedge |A\times B|=|A|n$$
A: For any $0\lt k \leq mn~ \exists q, r~(k=qn+r)$ with $0 \leq r \lt n$ and $q \in \Bbb N$.  Note that $q, r$ are unique with those properties.  If $r=0$, map $f: k \mapsto (q-1, r)$.  If $r \neq 0$, map $f: k \mapsto (q, r)$.  This $f$ is the bijection you want.
