Tuesday, November 14, 2017

real analysis - Simple bijection: help please



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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...