How can we prove that $\mathbb{N^2}$ has the same cardinality as $2\mathbb{N} + 1$

Question

How can we prove that $\mathbb{N^2}$ has the same cardinality as $2 \mathbb{N} + 1$?

I've thought about using Cantor's theorem and mapping every element in a coordinative system, am I going to the right direction or am I wrong?

Answer 1

Here is an alternative way if you don't want to explicit a bijection : you can use Cantor-Bernstein Theorem by proving that the two following maps are injective :

• $\varphi : 2\mathbb{N}+1 \rightarrow \mathbb{N}^2$ defined by $\varphi(n)=(n,0)$

• $\psi : \mathbb{N}^2 \rightarrow 2\mathbb{N}+1 $ defined by $\psi(n,m)=2^{n+1}3^m+1$.

Answer 2

One classical bijection from $\mathbb{N}^2$ to $\mathbb{N}$ is $$(x,y)\mapsto \frac{(x+y)(x+y+1)}{2}+y.$$ You can thus here try $$(x,y)\mapsto 2\left(\frac{(x+y)(x+y+1)}{2}+y \right)+1.$$

Answer 3

Simple bijection is given by $f(a,b)=2^a(2b-1)+1$ (assuming $0 \not\in \mathbb{N}$).

(bijectivity: use fundamental theorem of arithmetic to show every even integer can be uniquely written as $n=2^s d$ with $s\geq 1$, $d\geq 1$ odd)