Finite sets and cardinality.

Question

Let $$ I_N = \{n \in \mathbb N \mid 1 \leq n \leq N \}=\{1,2,3, \ldots, N \}.$$I want to show that $I_n \times I_m \sim I_{nm}$. For that, I defined $ \psi: I_n \times I_m \to I_ {nm} $ by $$ \psi (i, j) = i + n (j-1) $$ for all $ (i, j) \in I_n \times I_m $. It is trivially apparent that $ \ psi $ is well defined.

Now let's show that $ \psi $ is injective, for that let's suppose that $ \psi (i, j) = \psi (i ', j') \Rightarrow i + n (j-1) = i '+ n (j' -1) \Rightarrow n (j-j ') = i-i' $. Since $ 1 \leq i, i '\leq n \Rightarrow | i-i' | <n \Rightarrow n (j-j ') $ is an element of the set $ \{- n + 1, -n + 2, \ldots, n-2, n-1 \} $. On the other hand, $ n (j-j ') $ is a multiple of $ n $, that is, an element of the set of numbers $ \{0, \pm n, \pm 2n, \ldots \}. $ The only one of these numbers that satisfy that $ | i-i '| <n $ is $ 0 $. Which implies that $ i'-i = n (j-j ') = 0 $ and from there it is easily obtained that $ i = i' $ and $ j = j '$. Therefore $ \psi $ is injective.

To show that it is surjective. Let $ k \in I_{nm} $ and write $ k-1 = r + ns $ with $ r, s \in \mathbb N $ and $ 0 \leq r <n $. So for $ i = r + 1, j = s + 1 $ we have $ k = i + n (j-1) $, and also $ 1 \leq i \leq n \Rightarrow i \in I_n $. Then $ s \geq 0 \Rightarrow j = s + 1 \geq 1 $ and $ i + n (j-1) = k \leq nm \Rightarrow n (j-1) \leq nm-i \leq nm- 1 \Rightarrow j-1 \leq m-1 / n \Rightarrow j-1 \leq m-1 \Rightarrow j \leq m \Rightarrow j \in I_m \Rightarrow (i, j) \in I_n \times I_m $.

That way $ \psi $ is bijective. Knowing that, someone can tell me if that is correct and can explain to me how to get the inverse of said function.

Answer 1

Firstly, you should write your function as $ \psi \left(\ (i, j)\ \right) = i + n (j-1) $, not $ \psi (i, j) = i + n (j-1) $.

Next, I think the first part of your proof is actually quite good. The second part is honestly hard for me to parse, so I'll let someone else have that job. Obviously your function is bijective.

The inverse function then is surely $ \psi^{-1} :\ k \to \left(\ k\ \%\ n, \left(k-1\right)/n\ + 1 \right), $ where $/$ means the quotient (e.g. $7 / 3 = 2$ ), and $\%$ means the remainder under division e.g. $7\ \%\ 3 = 1.$

In fact, it is more natural for me to prove that $\gamma: I_{nm}\to I_n \times I_m$ defined by: $$\gamma(k) = \left(\ k\ \%\ n, \left(k-1\right)/n\ + 1 \right)$$

is bijective [which is fine since you should already know that $I_{nm} \sim I_n \times I_m \iff I_n \times I_m \sim I_{nm}].$

Proof that $\gamma$ is injective: Let $(a,b) \in I_n \times I_m.$ Suppose $\exists k \in I_{n,m},k' \in I_{n,m}$ such that $\gamma(k) = (a,b)$ and $\gamma(k') = (a,b).$ This implies: $$(k\ \%n, (k-1)/n + 1) = (a,b) = (k'\%n, (k'-1)/n + 1) \implies k\ \%n = k'\ \%n$$ $$\implies \exists r \in \mathbb{N} \text{ such that } k = k' + rn \quad (1), \text{ and also}$$ $$\implies (k-1)/n = (k'-1)/n$$ $$ \implies |k-k'| \leq n-1 \quad (2).$$

$(1)$ and $(2)$ together imply that $r = 0,$ and so $(1)$ reduces to $k=k',$ and we have injectivity.

Proof that $\gamma$ is surjective:

Let $(c,d) \in I_n \times I_m,\ $ and define $\ C = \{c + (e-1)n: e \in \mathbb{N} \}.$

Then there are only $n$ consecutive integers $k_i$ such that $(k-1)/n = d-1,\ $ namely

$$k_i \in D = \{ n(d-1) + 1, n(d-1) + 2, ..., n(d-1) + n = nd \}.$$

Clearly $D \cap C$ has only one element, $q\ $ say. Moreover, $q \in I_{nm}$ because $q \in D$ and $\max (D) = nm$, and $\min (D) = 1.$ Finally, $q$ satisfies:

$$\gamma(q) = \left(c,d\right).$$

This shows that $\gamma$ is surjective.