I am trying to show that if two sets $A,B$ have $n$ and $m$ distinct elements respectively then $A \times B$ has $nm$ elements. I assumed that there are bijections $f:\{1, ...,n\} \to A, k \mapsto a_k$ and $g: \{1,...,m\} \to B, k \mapsto b_k$.
Which I wanted to use to define a bijection $F: A \times B \to \{1,...,mn\}$ but no matter how I think about it, I can't construct $F$ that is both surjective and injective. My try $F$ that maps $(a_k, b_j) $ to $kj$ fails.
Please help. Is it possible to define $F$ that it is bijective?
Answer
Recall that $mn = \underbrace{n+n+\dots+n}_{m ~\text{times}}$.
So you can count from $1$ to $mn$ like this (I paired up every $n$ numbers): $$(1,\dots,n),(n+1,\dots,2n),\dots,((m-1)n+1,\dots,nm)$$
Can you now see your bijection?
No comments:
Post a Comment