Can we prove the same cardinality of the sets $\mathbb{N}$ and $\mathbb{N^2}$ this way?

Question

I tried to prove that the sets $\mathbb{N}$ and $\mathbb{N^2}$ have the same cardinality and I concluded the following:

Consider the function $f:\mathbb{N}\rightarrow \mathbb{N^2}$ that achieves the mapping:

$ \begin{cases} 1 \rightarrow (0,0) \end{cases} \\ \begin{cases} 2 \rightarrow (1,0) \\ 3 \rightarrow (1,1) \\ 4 \rightarrow (0,1) \end{cases} \\ \begin{cases} 5 \rightarrow (2,0) \\ 6 \rightarrow (2,1) \\ 7 \rightarrow (2,2) \\ 8 \rightarrow (1,2) \\ 9 \rightarrow (0,2) \end{cases} \\ \quad \vdots$

This way $\forall k \in \mathbb{N}\cup\{0\}$ we construct the function:

$f(n) = \begin{cases} \begin{aligned} &(\sqrt{n-1},0) \\ &(\sqrt{n-1},1) \\ \vdots \\ &(\sqrt{n-1},\sqrt{n-1}-1) \\ &(\sqrt{n-1},\sqrt{n-1}) \\ &(\sqrt{n-1}-1,\sqrt{n-1}) \\ \vdots \\ &(1,\sqrt{n-1}) \\ &(0,\sqrt{n-1}) \end{aligned} && \begin{aligned} &, n=k^2+1 \\ &, n=k^2+2 \\ \\ &, n=k^2+k \\ &, n=k^2+k+1 \\ &, n=k^2+(k+1)+1 \\ \\ &, n=k^2+(2k-1)+1 \\ &, n=k^2+2k+1=(k+1)^2 \end{aligned} \end{cases}$

Is the above mapping correct? If not then why? If yes then how can I prove rigorously that this function is bijective?

Answer 1

First, you need to define whether $0 \in \Bbb N.$ On the left of your correspondence you do not allow it, but on the right you do. Either way works fine for this purpose, but it makes changes in your bijection. There are many bijections that prove what you are trying to prove. Yours is a fine example. You need a floor function to make your square roots be natural numbers. The point is that the $n$s from $k^2+1$ to $(k+1)^2$ cover the $2k+1$ points on two sides of the square of side $k$ that haven't been covered before. The $n$s from $1$ to $k^2$ cover the square $[0,k-1] \times [0,k-1]$ If you write $n=k^2+p$ where $k$ is the maximal value to make $p$ nonnegative you can define $f(n)$ in a couple lines, one for each side of the square. Then for any ordered pair you can find the $n$ that maps to it.

Answer 2

Your proof is missing steps. Your last equation needs the ceiling function, $\lceil x \rceil$. You could indirectly use your function, which is actually $f:\mathbb{N} \to \mathbb{W}^2$, to prove that $|\mathbb{N}| = |\mathbb{N}^2|$, that is to say $\mathbb{N}$ and $\mathbb{N}^2$ have the same cardinality. But you will need the theorem that the range of any function has cardinality less than or equal to the cardinality of its domain. You may see this in text books as, "Given $f:A \to B$ is surjective, then $|A| \geq |B|$."

Mapping $\mathbb{N}^2 \to \mathbb{N}$ given by $(m,n) \to m$ is surjective. Thus $|\mathbb{N}^2| \geq |\mathbb{N}|$. With a little work your $f$ mapping is from $\mathbb{N}$ to $\mathbb{W}^2$ ($\mathbb{W}=\mathbb{N}\cup\{0\}$), and is surjective. Thus $|\mathbb{N}| \geq |\mathbb{W}^2|$. Define function $g:\mathbb{W}^2\to \mathbb{N}^2$ by $g((m,n))=(m+1,n+1)$. This function is surjective. So $|\mathbb{W}^2| \geq |\mathbb{N}^2|$. Thus $|\mathbb{N}| \geq |\mathbb{N}^2|$. Together $|\mathbb{N}| \geq |\mathbb{N}^2|$ and $|\mathbb{N}^2| \geq |\mathbb{N}|$ imply $|\mathbb{N}^2| = |\mathbb{N}|.$

If you want a more straightforward proof with a bijection, I will define your squarish mapping in a different way.

For convenience, define $\hat{n} = \lceil\sqrt{n}\rceil$, $n_x=1+\hat{n}^2-n$, and $n_y=n-(\hat{n}-1)^2$. Now let $f:\mathbb{N}\to \mathbb{N}^2$ be defined as $f(n)=\left( \min\{ \hat{n},n_x \} , \min\{ \hat{n},n_y \} \right)$. On your own try to show this function is bijective. Below is most of my proof.

First $f$ is well defined.

Claim 1: $\hat{n} \leq n_x \implies \hat{n} \geq n_y$. Suppose $\hat{n} \leq n_x$ and $\hat{n} < n_y$. Then $2\hat{n} < n_x + n_y = 1+\hat{n}^2-n +n-(\hat{n}-1)^2 = 2\hat{n}$. A contradiction. Thus claim 1. For the same reasons $\hat{n} \leq n_y \implies \hat{n} \geq n_x$. Thus $\max \left( \min\{ \hat{n},n_x \} , \min\{ \hat{n},n_y \} \right) =\hat{n}$.

Second $f$ is surjective: Let $(a,b)\in\mathbb{N}^2$. If $a\geq b$, then $a=\hat{n}$ and $b=n_y$. Thus $n=b+(a-1)^2$. If $a<b$, then $b=\hat{n}$ and $a=n_x$. Thus $n=1+b^2-a$. In either case $f(n)=(a,b)$.

Third $f$ is injective: Let $m$ and $n$ be natural numbers. Assume $f(m)=(a,b)=f(n)$. Then the larger of the two coordinates is $\hat{m}=\hat{n}$, the other coordinate is either $m_x=n_x$ or $m_y=n_y$. Using the same process for proving $f$ is surjective, $m=n$.

Answer 3

With $0 \in \mathbb N$ we trace out a path:

$(0,0) \to$
$(1,0) \to (1,1) \to (0,1) \to $
$(2,0) \to (2,1) \to (2,2) \to (1,2) \to (0,2) \to $
$(3,0) \to (3,1) \to (3,2) \to (3,3) \to (2,3) \to (1,3) \to (0,3) \to $
$\text{etc.} \qquad \text{Figure 1}$

Here is the corresponding mapping:

$$ \pi(m,n) = \left\{\begin{array}{lr} n^2+2n-m, & \text{for } m \le n\\ m^2+n, & \text{for } m \gt n \end{array}\right\} $$

As a check, apply $\pi$ to Figure 1:

$\pi(0,0) = 0$
$\pi(1,0)=1 \; \pi (1,1)=2 \; \pi (0,1)=3$
$\pi(2,0)=4 \; \pi (2,1)=5 \; \pi (2,2)=6 \; \pi (1,2)=7 \; \pi (0,2)=8 $
$\pi(3,0)=9 \; \pi (3,1)=10 \; \pi (3,2)=11 \; \pi (3,3)=12 \; \pi (2,3) =13 \; \pi (1,3) =14 \; \pi (0,3)=15 $
$\text{etc.} \qquad \pi\text{(Figure 1)}$

Proposition: If $k \in \mathbb N$ then the mapping $\pi$ restricted to

$\quad \{(m,n) \, | \, max(m,n) \le k$}

is $\text{1:1}$ and onto the initial segment $[0,\,{(k+1)}^2-1]$.
Proof
Hint: Use induction on $k$.