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.

  • 2
    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?2012-09-14
  • 0
    Guessing: are you finding a bijection between $[m]\times[n]$ and $[mn]$?2012-09-14
  • 1
    Apparently, this question is about showing $|A\times B| = |A|\cdot|B|$ in the finite case.2012-09-14
  • 0
    @rschwieb Yes, I just seem to be inefficient in parsing it correctly.2012-09-14
  • 0
    Since the previous comments appear to be pointed in that way, I edited the question. If I missed the mark please correct it.2012-09-14
  • 0
    @rschwieb You hit the nail on the head.2012-09-14
  • 1
    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.2012-09-14
  • 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