Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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? –  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
1  
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
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. –  rschwieb Sep 14 '12 at 12:35

3 Answers 3

up vote 2 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.