Does ${(x,y)\in\mathbb{R}\times\mathbb{R}:x,y\in\mathbb{Z}}$ have cardinality $\aleph_0$ or $c$?

Question

So here's my intuition. Letting $S=\{(x,y)\in\mathbb{R}\times\mathbb{R}:x,y\in\mathbb{Z}\}$, $\bar S=\aleph_0$ because $(x,y)\in\mathbb{Z}\times\mathbb{Z}$, which can be shown to be equivalent to $\mathbb{N}\times\mathbb{N}$, which in turn can be shown to be equivalent to $\mathbb{N}$ and thus is denumerable.

I don't have to prove it, but I think I need to show a little more rigor in my explanation. Also, what would a function that constructs this set (i.e., f onto S) look like? This isn't part of the question I need to answer, just curious because my classmates and I couldn't picture it.

Answer 1

You are correct: $\Bbb Z\times\Bbb Z$ is countably infinite, and your argument is fine. If you want an explicit bijection, start with one from $\Bbb Z$ to $\Bbb N$. Here’s one possibility:

$$f:\Bbb Z\to\Bbb N:n\mapsto\begin{cases} 2n,&\text{if }n\ge 0\\ -2n-1,&\text{if }n<0\;. \end{cases}$$

You can picture the map like this:

$$\begin{array}{r\ccc} \text{In }\Bbb Z:&-4&-3&-2&-1&0&1&2&3&4\\ \text{In }\Bbb N:&7&5&3&1&0&2&4&6&8 \end{array}$$

This map $f$ immediately gives you a bijection $$F:\Bbb Z\times\Bbb Z\to\Bbb N\times\Bbb N:\langle m,n\rangle\mapsto\langle f(m),f(n)\rangle\;.$$

Now compose $F$ with the pairing function, which is a bijection $\pi:\Bbb N\times\Bbb N\to\Bbb N$: $\pi\circ F$ is a bijection from $\Bbb Z\times\Bbb Z$ to $\Bbb N$.

Answer 2

You asked for an example of an onto function $f : \mathbb{N} \to \mathbb{Z} \times \mathbb{Z}$. A function from $\mathbb{N}$ to a set $T$ is also called a sequence of elements in $T$, so you really want a sequence in $\mathbb{Z}\times \mathbb{Z}$ that hits all elements of $\mathbb{Z} \times \mathbb{Z}$.

One example would be a "spiral" function: the first element is $(0, 0)$. Next, you make your sequence move through the "box" $(1, 0)$, $(1, 1)$, $(0, 1)$, $(-1, 1)$, $(-1, 0)$, $(-1, -1)$, $(0, -1)$, $(1, -1)$. You might want to trace out this path on graph paper if you can't see it in your head.

Now, keep going around boxes that are centered at the origin, making larger and larger boxes. In this way, you can make a sequence that will eventually hit any given pair $(x, y) \in \mathbb{Z}\times\mathbb{Z}$, thus giving you the desired onto function.