Proving One-to-One Function I have been reading Daniel Cunningham's Set Theory: A First Course, and I am stuck at this problem which is cited by a proof in the next chapter, so I can't skip this problem without also getting stuck at the next chapter.
Let $f: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N} $ be defined by $f (i, j) = 2^i \cdot 3^j$, for all $(i,j) \in \mathbb{N} \times \mathbb{N}$.
$a)$ Prove that $f$ is one-to-one.
$b)$ Prove that if $i < m$ and $j < n$, then $f (i, j) < f (m, n)$.
I would really appreciate some hints to solve the problem!
 A: First, to solve a problem of this nature, we must know the function that we are dealing with. And for that, one of the things that we should know about the function is the domain and the codomain. I went searching for the problem on the book that you mentioned and it turns out that $\omega = \mathbb{N}$. Now, let’s solve this.
Let $f \colon \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ be a function defined by $f(m,n) = 2^m3^n$, for all $(m,n) \in \mathbb{N} \times \mathbb{N}$.
(a) Recall that, $f$ is one-to-one or injective if
$$\forall (m,n),(m’,n’) \in \mathbb{N} \times \mathbb{N}, \quad f(m,n) = f(m’,n’) \implies (m,n) = (m’,n’).$$
Also, note that $(m,n) = (m’,n’)$ if and only if $m = m’$ and $n = n’$. Let $(a,b), (c,d) \in \mathbb{N}^2$ and suppose that $f(a,b) = f(c,d)$. By definition of $f$, one has that $2^a3^b = 2^c3^d$.
Further, suppose that $(a,b) \neq (c,d)$. This means, of course, that $a \neq c$ or $b \neq d$.
First, suppose that $a \neq c$. Then it must be $a < c$ or $c < a$. Without loss of generality, assume that it is $a < c$. Note that $0 < c-a \in \mathbb{N}$. So, we have that $3^b = 2^{c-a}3^d$. Now, what does this mean? The $LHS$ of this expression is clearly an odd number. Since $LHS = RHS$, then the expression in the $RHS$ must also be an odd number. But for that, one must have $c-a = 0$, i.e., $a = c$. Which is a contradiction, because we have supposed that $a \neq c$. Then, $a = c$.
But this means that $3^b = 3^d$ which implies that $b = d$. Since $a=c$ and $b=d$, then $(a,b) = (c,d)$ which is a contradiction, because we have assumed that $(a,b) \neq (c,d)$. Therefore, we have that $(a,b) = (c,d)$, which proves that $f$ is onte-to-one. $\square$
(b) Let $(a,b),(c,d) \in \mathbb{N}^2$ and suppose that $a < c$ and $b < d$. Note that the functions $g,h \colon \mathbb{R} \to \mathbb{R}$ defined by $g(x) = 2^x$ and $h(x) = 3^x$, for all $x \in \mathbb{R}$, are increasing functions (you can check the proof of this fact in any calculus book). This is also true, when we consider the functions $g|_{\mathbb{N}}$ and $h|_{\mathbb{N}}$. Then,
$$a < c \implies 2^a < 2^c \quad \text{and} \quad b < d \implies 3^b < 3^d.$$
Clearly, one has that $2^a3^b < 2^c3^d$ which means that $f(a,b) < f(c,d)$. $\square$
Note. The Fundamental Theorem of Arithmetic states that

If $n$ is a natural number such that $1 < n$, then $n$ can be uniquely expressed, up to the order, as a finite product of prime numbers.

We can also use this Theorem to prove that $f$ is one-to-one and the proof is quite straightforward.
Let $(a,b),(c,d) \in \mathbb{N}^2$ such that $f(a,b) = f(c,d)$. Hence, by definition, $2^a3^b = 2^c3^d$. Note that $2^a3^b$ and $2^c3^d$ are the prime factorisation of two natural numbers such that $2$ and $3$ are the only prime numbers that divides them. By the Fundamental Theorem of Arithmetic, the prime factorisation of a natural number greater than $1$ is unique up to the order. Hence, since $2^a3^b = 2^c3^d$, we conclude that $a = c$ and $b = d$, i.e., $(a,b) = (c,d)$ (because they are the same natural number). Therefore, $f$ is one-to-one.
