1
$\begingroup$

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.

  • 0
    I don't think I have defined that in such a way, but I think it would be the same. I must have meant that the *cross* product of two sets was {(a,b)∣a∈A;b∈B}2012-09-14

3 Answers 3

1

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}$.

2

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.

2

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]$.

  • 0
    I think this is what I wanted to know. Thanks for clearing it up.2012-09-14