How do I show that the set of natural numbers $\mathbb{N}$ has the same size as $\mathbb{N}\times\mathbb{N}$? I know that for two sets to have the same size, there must be an injection from the set $\mathbb{N}$ to the set $\mathbb{N}\times\mathbb{N}$ and there must be and injection from the set $\mathbb{N}\times\mathbb{N}$ to the set $\mathbb{N}$.
But I have no idea on how to prove this.
$\endgroup$ 44 Answers
$\begingroup$Take any $n\in\Bbb N$.
One can find $n_1$ and $n_2$ such that $ n = 2^{n_1}n_2$.
Essentially,it extracts the odd and even part of $n$.
So, $n_1$ and $n_2$ are unique.
Hence by this one can find a bijection from $\Bbb N$ to $\Bbb N \times (\Bbb N\setminus 2\Bbb N)$
$\Bbb N\setminus 2\Bbb N$ is the set of all odd integers.
Now, since $\Bbb N$ is equinumerous to $\Bbb N\setminus 2\Bbb N$.(Argue)
So, $\Bbb N$ and $\Bbb N\times\Bbb N$ are equinumerous.
$\endgroup$ 2 $\begingroup$The maps $(m,n)\mapsto 2^m\cdot 3^n$ and $n\mapsto (n,0)$ are injections. Now we may apply the Schröder–Bernstein theorem.
$\endgroup$ $\begingroup$You can do this in many ways. Here is one:
First get all pairs of numbers with sum 0, then with sum 1, then sum 2, etc.:
So:
(0,0), (0,1), (1,0), (0,2), (1,1), (2,0), (0,3), (1,2), (2,1), (3,0), etc.
Notice that for every sum $i$, there are only finitely many ($i+1$ to be exact) pairs $(m,n)$ that have that sum, meaning that for every number $i$, you will get to all the pairs with sum $i$, and since every pair of numbers $(m,n)$ has a finite sum $i$, it is bound to appear somewhere on this list.
And now that you have a list, you have a one to one mapping:
1<->(0,0)
2<->(0,1)
3<->(1,0)
4<->(0,2)
etc.
$\endgroup$ $\begingroup$What you can also do is find a bijection between the two sets.
Consider the function:$$f: \mathbb{N} \rightarrow \mathbb{N} \times \mathbb{N}$$
$$f(x)\begin{cases} (\frac{m+n-1}{2}+n):if\ m+n-1 \ is \ odd\\ ({\frac{m+n-1}{2}}+m) : if\ m+n-1 \ is \ even \\ \end{cases}$$ Try to make a graph, and check that is indeed a bijection. (if you are unsure about the bijection rule, if $f$ is a bijection, then $f^{-1}$ exists, and it is also a bijection, so you have two injections you required)
$\endgroup$
