Show that given two bijections:
$$f: A \rightarrow \{ 1,…,m \}$$
$$g: B \rightarrow \{ 1,…,n \}$$
there exists a bijection:
$$A \times B\rightarrow \{ 1,…,mn \}$$
What have I tried so far?
So, I know that for there to be a bijection the function must be both injective and surjective. I figured to prove this, I must show both. So I thought I may need to construct the bijection using a table and showing these but I'm not sure if this would be best?
Bijection of sets with cartesian product
elementary-set-theoryfunctions
Best Answer
HINT: Let us denote $[k] = \{1, 2, \cdots, k\}$. Note that $\alpha: A \times B \to [m] \times [n]$ defined by $\alpha(a, b) = (f(a), g(b))$ is a bijection (why?). Thus, we only need to find a bijection from $[m] \times [n]$ to $[mn]$.
To do this, let us order elements of $[m] \times [n]$ with the rule that $$(a, b) < (a', b) \iff a < a' \text{ or } (a = a' \text{ and } b < b')$$ in other words, we first compare the first elements, and if they are equal, we compare the second elements. Let us write the elements of $[m] \times [n]$ in order according this rule: $$(1, 1) \\ (1, 2) \\ \vdots \\ (1, n) \\ (2, 1) \\ \vdots \\ (m, n)$$ ...and now we simply can simply map the first element in our list to $1$, the second element to $2$, and so on: $$(1, 1) \iff 1 \\ (1, 2) \iff 2 \\ \vdots \\ (1, n) \iff n \\ (2, 1) \iff n + 1 \\ \vdots \\ (m, n) \iff mn $$ And in fact you can find a closed form for this bijection (call it $\beta$). To do this, you can note that $\beta(a, b)$ is always $b$ greater than a multiple of $n$, and that $\beta(a + 1, b)$ and $\beta(a, b)$ always differ by $n$, for any $a$ and $b$. Can you proceed from here?
In summary: We first found a bijection from $\alpha: A \times B$ to $[m] \times [n]$. Then, we found a bijection from $[m] \times [n]$ to $[mn]$. It follows that $\beta \circ \alpha$ is a bijection from $A \times B$ to $[mn]$.
Addendum: Why must $\alpha$ be a bijection?
Answer: Suppose it weren't injective. Then we could find $(a, b), (a', b') \in A \times B$ such that $\alpha(a,b) = \alpha(a', b')$. This means that $f(a) = f(a')$ and $g(b) = g(b')$, but this contradicts the fact that $f$ and $g$ are bijections (and are hence injections).
Suppose it weren't surjective. Then we could find $(x, y) \in [m] \times [n]$ such that no element of $A \times B$ mapped to $(x, y)$. For this to be the case, it would have to be that either there existed no element $a \in A$ such that $f(a) = x$, or that there existed no element $b \in B$ such that $g(b) = y$. But this contradicts either $f$ or $g$'s surjectivity (and thus bijectivity).