# Find a bijection between the Cartesian Product $[m] \times [n]$ and $[m n]$

Let $[n]$ denote $\{1,2,\dots n\}$.

Show there is a bijection between $[m]\times[n]$ and $[mn]$.

I was thinking about doing something related to induction to prove that there is some value $b$ for every $f(a)$. Then probably settle for the definition of a product to say that in $\{(a,b)\mid a\in A ; b\in B\}$ so there can only be values corresponding from $A$ and $B$ in $(a,b)$. If this seems correct, let me know.

If there's anyone with a more rigorous proof, I would be delighted.

-
The first step would be a more rigorous statement of what you're actually trying to prove. e.g. what function from what domain to what codomain are you trying to prove is bijective? – Hurkyl Sep 14 '12 at 12:27
Guessing: are you finding a bijection between $[m]\times[n]$ and $[mn]$? – rschwieb Sep 14 '12 at 12:30
Apparently, this question is about showing $|A\times B| = |A|\cdot|B|$ in the finite case. – Hagen von Eitzen Sep 14 '12 at 12:30
@rschwieb Yes, I just seem to be inefficient in parsing it correctly. – Casquibaldo Sep 14 '12 at 12:32
I'm not exactly sure what you're allowing yourself to use. If you are defining the product of natural numbers as the cardinality of the cross product, then this pretty much follows by definition. I'll type up what I mean, and you can tell me if it's useful or not. – rschwieb Sep 14 '12 at 12:35

## 3 Answers

If you are defining the product of natural numbers this way, I'll supply a solution.

$mn=|A\times B|$ where $|A|=n$ and $|B|=m$

In particular you could use $A=[n]$ and $B=[m]$.

But now the statement that $mn=|[n]\times[m]|$ says exactly that $[mn]$ is bijective to $[n]\times[m]$, since $[mn]$ is a set of cardinality $mn$.

To find a concrete bijection between the two sets, imagine $[n]\times[m]$ written out as a grid. Enumerate the entries of the grid from $1\dots mn$ any way you like. That's a bijection from $[mn]$ to $[n]\times[m]$.

-
I think this is what I wanted to know. Thanks for clearing it up. – Casquibaldo Sep 14 '12 at 12:46

For each two finite sets $A$ and $B$ with the same number of elements, you can find a bijection $A\rightarrow B$. Simply enumerate the items: $A=\{ a_1,\dots,a_n \}, B=\{ b_1,\dots,b_n \}$ and define a mapping $\phi:A\rightarrow B$ by $a_j \mapsto b_j$. This is one possible bijection.

Apply this for your case.

-

For any positive integer $k$, let $S_k$ be the set $\{0,1, \dots, k-1$. There is an obvious bijection between $S_k$ and $[k]$. So it is enough to show that there is a bijection between $S_m\times S_n$ and $S_{mn}$. We describe a bijection that is natural from a number-theoretic point of view.

Recall that for any positive integer $x$, and any positive integer $n$, there exist uniquely determined integers $q$ and $r$ such that $0\le r\le n-1$ and $$x=qn+r.\tag{1}$$ This result is often called the Division Algorithm.

In Equation $(1)$, we have $0\le q\le m-1$ iff $0\le x\le mn-1$. So the mapping that takes the ordered pair $(q,r)$ to $x=qn+r$ is a bijection from $S_m\times S_n$ to $S_{mn}$.

-