This question already has an answer here:

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.


marked as duplicate by Noah Schweber, user940, mrp, zhoraster, Rohan Feb 12 '17 at 11:20

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ and what is the relation with my question? Can't I show it only using definition of injective function? $\endgroup$ – JJ Ab Feb 3 '17 at 17:43
  • $\begingroup$ It's literally the same question. "Countable" means "has the same size as $\mathbb{N}$", so it's exactly asking how to show that $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$ have the same size. Did you look at Asaf's answer? $\endgroup$ – Noah Schweber Feb 3 '17 at 17:45
  • $\begingroup$ Consider splitting $\mathbb{N}$ into disjoint subsets of primes $p_n$ such that $\mathbf{P}_n = \{ p_n^a | a \in \mathbb{N} \}$. Consider how these sets can map to pairs $(a,b)$. $\endgroup$ – kmeis Feb 3 '17 at 17:51
  • $\begingroup$ $f(m,n) = 2^m (2n + 1) − 1$ $\endgroup$ – mle Feb 4 '17 at 1:13

take any n$\in$ 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 N to N x (N\2N)

N\2N is the set of all odd integers.

Now,Since N is equinumerous to N\2N.(Argue)

So, N and N X N are equinumerous.

  • $\begingroup$ is that n= (2 to the power of n1 ) times n2 ? $\endgroup$ – JJ Ab Feb 3 '17 at 17:50
  • $\begingroup$ yes. Essentially you are extracting the even part(some power of 2) by the $n_1$ $\endgroup$ – Horan Feb 3 '17 at 17:52

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.:


(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:







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.


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)


Not the answer you're looking for? Browse other questions tagged or ask your own question.