MHB How Can a Bijective Function Demonstrate the Cardinality of a Cartesian Product?

[evinda]

Hello! (Wave)

The set $n \times m$ is equinumerous with the natural number $n \cdot m$ and thus $n \times m \sim n \cdot m$, i.e. $Card(n \times m)=n \cdot m$.
Which bijective function could we pick in order to show the above? (Thinking)

 

[Nono713]

Not really sure what you mean by "the set $n \times m$", generally the cartesian product is defined in terms of two sets, not two natural numbers. But I'm going to interpret your notation as the cartesian product of two sets of cardinality $n$ and $m$ respectively, in which case one suitable bijection from "the set $n \times m$" to a set of $n \cdot m$ natural numbers could be:
$$(i, j) \mapsto mi + j$$
Such that for instance given $n = 2$ and $m = 3$, we have (if your natural numbers start at 1, just adjust the formula accordingly):
$$(0, 0) \mapsto 3 \cdot 0 + 0 = 0$$
$$(0, 1) \mapsto 3 \cdot 0 + 1 = 1$$
$$(0, 2) \mapsto 3 \cdot 0 + 2 = 2$$
$$(1, 0) \mapsto 3 \cdot 1 + 0 = 3$$
$$(1, 1) \mapsto 3 \cdot 1 + 1 = 4$$
$$(1, 2) \mapsto 3 \cdot 1 + 2 = 5$$
And we see that this is indeed a bijection, and "the set $2 \times 3$" has cardinality $2 \cdot 3 = 6$ as expected. You can prove that this mapping is a bijection for any $n$ and $m$ easily by observing that $0 \leq j < m$ and using the notions of quotient and remainder...​

 

[evinda]

How do we know that $m \cdot i+j \in n \cdot m$? (Worried)

 

[Nono713]

How do we know that $m \cdot i+j \in n \cdot m$? (Worried)

Because $0 \leq i \leq n - 1$ and $0 \leq j \leq m - 1$. Doesn't that imply that $0 \leq m \cdot i + j \leq n \cdot m - 1$?

 

[evinda]

Because $0 \leq i \leq n - 1$ and $0 \leq j \leq m - 1$. Doesn't that imply that $0 \leq m \cdot i + j \leq n \cdot m - 1$?

I see... (Nod)

You can prove that this mapping is a bijection for any $n$ and $m$ easily by observing that $0 \leq j < m$ and using the notions of quotient and remainder...

Could you explain me further how we can show that the function is bijective? (Thinking)

 

[Nono713]

We've shown that if $(i, j) \in n \times m$ (to reuse your notation) then $0 \leq m \cdot i + j \leq n \cdot m - 1$, right? So the range of the mapping function $f((i, j)) = m \cdot i + j$ is the set of natural numbers from $0$ to $n \cdot m - 1$ inclusive (which contains $n \cdot m$ natural numbers).

To show that $f$ is surjective, use the properties of Euclidean division - Wikipedia, the free encyclopedia to show that for every $0 \leq x \leq n \cdot m - 1$, there exist natural numbers $i$ and $j$ such that $x = m \cdot i + j$ and $0 \leq i \leq n - 1$, $0 \leq j \leq m - 1$. Then $(i, j) \in n \times m$ and $f$ must be surjective.

To show that $f$ is injective, suppose that there existed two pairs of natural numbers $(i_1, j_1)$ and $(i_2, j_2)$ such that:
$$m \cdot i_i + j_1 = m \cdot i_2 + j_2$$
Suppose without loss of generality that $i_1 \leq i_2$ and $j_1 \leq j_2$, then that would imply that:
$$m \cdot (i_2 - i_1) + (j_2 - j_1) = 0$$
But both $i_2 - i_1$ and $j_2 - j_1$ are $\geq 0$, and $m$ is positive, so the only way this can hold is if $i_1 = i_2$ and $j_1 = j_2$. So $f$ is injective.

$\therefore$ $f$ is bijective, and so the cardinality of $n \times m$ is $n \cdot m$. Does that make it clearer? In fact, the Euclidean division theorem already guarantees that the integers $(i, j)$ are unique, so it technically gives you injectivity for free. But it doesn't hurt to prove it ourselves.​