# How do I show that the set of natural number N has the same size as NxN? [duplicate]

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, RohanFeb 12 '17 at 11:20

• 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? – Noah Schweber Feb 3 '17 at 17:45
• 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)$. – kmeis Feb 3 '17 at 17:51
• $f(m,n) = 2^m (2n + 1) − 1$ – 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. • is that n= (2 to the power of n1 ) times n2 ? – JJ Ab Feb 3 '17 at 17:50 • yes. Essentially you are extracting the even part(some power of 2) by the n_1 – 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.: 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. 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)