What is the cardinality of $\{{(x, y) \in \mathbb{N}\times\mathbb{N} \mid x-y \,\text{ is even}}\}$?

Question

I've been trying to find it by searching for a one-on-one function
$$f:\{(x, y) \in \mathbb{N}\times\mathbb{N} \mid x-y \,\text{ is even}\} \to \mathbb{N} \times \mathbb{N}$$
and an onto function:
$$g:\{(x, y) \in \mathbb{N}\times\mathbb{N} \mid x-y \,\text{ is even}\} \to \mathbb{N} \times \mathbb{N}$$ to prove that $$\bigl|\{(x, y) \in \mathbb{N}\times\mathbb{N} \mid x-y \,\text{ is even}\}\bigr| = |\mathbb{N} \times \mathbb{N}|$$

I found $f((x, y)) = (x, y)$, but can't find a proper $g$. Can a single function have two outputs for a single input?
For example: $g((x, y)) = (x, y),\space(x, y + 1)$?

Thanks!

Answer 1

The smaller infinite cardinal is the cardinality of $\mathbb{N}$ (the countable infinity). It is the same as the cardinality of $\mathbb{N}\times\mathbb{N}$.

As your set is a subset of $\mathbb{N}\times\mathbb{N}$, its cardinal is at most infinite countable. But as it is infinite, it is at least infinite countable. Thus its cardinality is infinite countable.

Another more rigorous proof would use Cantor-Bernstein theorem : find an injective function of $\mathbb{N}\times\mathbb{N}$ to your subset and an injective function from your subset to $\mathbb{N}\times\mathbb{N}$. I propose the following. Say your subset is $A$, and

\begin{align} f : A &\to \mathbb{N}\times\mathbb{N} \\ (x,y) &\mapsto (x,y) \end{align} is the natural injection, and \begin{align} g : \mathbb{N}\times\mathbb{N} & \to A \\ (x,y) & \mapsto (x+y,x-y) \text{ if } x> y \\ (x,y) & \mapsto (y-x, x+y) \text{ if} x \leqslant y \end{align} Show that $g$ is injective (it is easy) and well defined (because$ (x+y)-(x-y) = 2x$ and $(y-x)-(x+y) = -2x$ are even).

Answer 2

Here's a bijection from $A$ to $\Bbb N\times \Bbb N$: $$(x, y) \mapsto \begin{cases}\left(x, \dfrac{y+1}{2}\right) & y \text{ is odd}\\ \left(x, \dfrac{y}{2}\right) & y \text{ is even}\\\end{cases}$$

The verification that this is a bijection is not too hard.
(Keep in mind that if $(x, y) \in A$ and $y$ is odd, then $x$ is odd as well. Same for being even.)