To prove that $|\mathbb{N}| = |\mathbb{N} \times \mathbb{N}|$, we must show that there exists a bijective function $f : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$. A bijective function is one that is both injective (one-to-one) and surjective (onto). The proof often uses the Cantor pairing function or a similar pairing mechanism.

---

Construction of $f$

Define $f(n, m)$ as: $f(n, m) = \frac{(n + m)(n + m + 1)}{2} + m$ where $n, m \in \mathbb{N}$.

This formula is derived from enumerating pairs of natural numbers in a diagonal manner. Each diagonal corresponds to $n + m = k$ for some $k \in \mathbb{N}$.

---

Step 1: Prove $f$ is injective

We need to show that if $f(n_1, m_1) = f(n_2, m_2)$, then $n_1 = n_2$ and $m_1 = m_2$.

Assume:

$f(n_1, m_1) = f(n_2, m_2).$

By the definition of $f$: $\frac{(n_1 + m_1)(n_1 + m_1 + 1)}{2} + m_1 = \frac{(n_2 + m_2)(n_2 + m_2 + 1)}{2} + m_2.$

Subtract $m_1$ and $m_2$ from both sides: $\frac{(n_1 + m_1)(n_1 + m_1 + 1)}{2} = \frac{(n_2 + m_2)(n_2 + m_2 + 1)}{2}.$

Let $k_1 = n_1 + m_1$ and $k_2 = n_2 + m_2$: $\frac{k_1(k_1 + 1)}{2} = \frac{k_2(k_2 + 1)}{2}.$

Since the quadratic function $k(k + 1)/2$ is injective, it follows that $k_1 = k_2$, implying: $n_1 + m_1 = n_2 + m_2.$

Returning to the original equation: $m_1 = m_2.$ Thus, $n_1 = n_2$ as well.

Hence, $f$ is injective.

---

Step 2: Prove $f$ is surjective

To show surjectivity, take any $z \in \mathbb{N}$ and find $(n, m) \in \mathbb{N} \times \mathbb{N}$ such that $f(n, m) = z$.

Decomposition:

Given $z$, solve for $k$ such that: $\frac{k(k + 1)}{2} \leq z < \frac{(k + 1)(k + 2)}{2}.$

This $k$ represents the diagonal containing $z$. Then compute: $m = z - \frac{k(k + 1)}{2},$ and: $n = k - m.$

This ensures $(n, m) \in \mathbb{N} \times \mathbb{N}$, and $f(n, m) = z$, proving surjectivity.

---

Conclusion

Since $f$ is both injective and surjective, $f$ is bijective. Therefore, $|\mathbb{N}| = |\mathbb{N} \times \mathbb{N}|$.

---

Would you like further clarification or an example of the pairing function in use?

---

Relative Questions:

1. How does the diagonal enumeration method help in mapping $\mathbb{N} \times \mathbb{N}$ to $\mathbb{N}$?
2. Can the proof be extended to show $|\mathbb{N}| = |\mathbb{N}^k|$ for any $k \in \mathbb{N}$?
3. Why is the quadratic function $\frac{k(k+1)}{2}$ key in this proof?
4. How can we visualize the bijection between $\mathbb{N}$ and $\mathbb{N} \times \mathbb{N}$?
5. What are practical applications of pairing functions in computer science or mathematics?

Tip:

Visualizing the diagonal method with small examples (e.g., $(0, 0), (0, 1), (1, 0)$) can make understanding the pairing function much easier!