# What is the Simplest Explanation for the Countability of the Integers?

What is the simplest (or at least simple to understand) if one wanted to explain why the set of Integers has the same cardinality as the set of natural numbers to students who have a vague idea of why sets such as the whole numbers, even numbers, odd numbers have the same cardinality as that of the natural numbers (by establishing a 1-1 correspondence), but have had no courses in set theory or topology---so don't know of the arguments that underlie things like the countable union of countable sets is countable.

I do not want to iterate something like $$Z$$ is a subset of $$Q$$ and therefore countable. I want to try to explain it directly.

It seems that a straightforward 1-1 argument doesn't apply here.

• $0,1,-1,2,-2,3,-3,4,-4,\ldots$ – Lord Shark the Unknown Jul 12 at 16:59
• Define things clearly...and then show a bijective function between $\;\Bbb N\;$ and $\;\Bbb Z\;$ . I think that may be as simple as expected. – DonAntonio Jul 12 at 17:00
• I think Hilbert's hotel is a nice illustration for this. Assign all rooms to natural numbers then let zero arrive, followed by $-1, -2, ...$ – Vasya Jul 12 at 17:05
• I've used Hilbert's Hotel for a finite number of additions/subtractions, but I wasn't sure it would be a valid argument for adding infinitely many " additional rooms." – mlchristians Jul 12 at 17:09
• @mlchristians: From wiki: en.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Grand_Hotel Infinitely many new guests: It is also possible to accommodate a countably infinite number of new guests: just move the person occupying room 1 to room 2, the guest occupying room 2 to room 4, and, in general, the guest occupying room n to room 2n (2 times n), and all the odd-numbered rooms (which are countably infinite) will be free for the new guests. – Vasya Jul 12 at 17:14

Here's one:

$$1\mapsto0$$

$$2\mapsto1$$

$$3\mapsto-1$$

$$4\mapsto2$$

$$5\mapsto-2$$

$$6\mapsto3$$

$$7\mapsto-3$$

$$\vdots$$

• can even make it explicit: $(-1)^n \lfloor \frac{n}{2} \rfloor$ – user113102 Jul 12 at 17:01

There is a straightforward bijection, though - contra your last sentence - gotten by "interleaving:"

$$0, -1, 1, -2, 2, -3, 3, ...$$

I think this is readily understandable. It's when we look at the rationals that things get difficult.

• The formula for this bijection from $\mathbb{N} \rightarrow \mathbb{Z}$ is: $$n \mapsto \frac{n}{2}, \text{ when n is even}$$ $$n \mapsto (-1)^n \cdot \frac{n+1}{2}, \text{ when n is odd}$$ – Selrach Dunbar Jul 12 at 17:06
• @SelrachDunbar Sure, but I don't think that having the formula in hand actually makes things any clearer just writing the first few values should make the idea clear to the student. (Also, note that if $n$ is odd we have $(-1)^n=-1$.) – Noah Schweber Jul 12 at 17:59
• @ NoahSchweber That is a good point. – Selrach Dunbar Jul 12 at 19:29

Well, countability of a set means that one can tabulate the elements of the set in a list like this: $$\begin{array}{cccc} 0 & 1 & 2 & 3 & \ldots \\ a_0 & a_1 & a_2 & a_3 &\ldots \end{array}$$ This holds for the natural numbers, $$\begin{array}{cccc} 0 & 1 & 2 & 3 & \ldots \\ 0 & 1 & 2 & 3 &\ldots \end{array}$$ the natural numbers without 0, $$\begin{array}{cccc} 0 & 1 & 2 & 3 & \ldots \\ 1 & 2 & 3 & 4 &\ldots \end{array}$$ the even natural numbers, $$\begin{array}{cccc} 0 & 1 & 2 & 3 & \ldots \\ 0 & 2 & 4 & 6 &\ldots \end{array}$$ the odd natural numbers, $$\begin{array}{cccc} 0 & 1 & 2 & 3 & \ldots \\ 1 & 3 & 5 & 7 &\ldots \end{array}$$ the integers, $$\begin{array}{cccccccc} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7& \ldots \\ 0 & 1 & -1 & 2 &-2 & 3 &-3 & 4 & \ldots \end{array}$$ and also the rational numbers by the 1st Cantor diagonalization argument.

If these students trust that the evens and odds both have the same cardinality as $$\mathbb{N}$$, then I don't see why a 1-1 correspondence doesn't work. Consider $$f: \mathbb{N}\to\mathbb{Z}$$ defined such that $$f(0)=0$$ and $$f(2n)=n$$, while $$f(2n+1)=-(n+1)/2$$.

In other words, the even numbers get mapped to $$\mathbb{N}$$, the odd numbers get mapped to $$-\mathbb{N}$$, and $$0$$ maps to $$0$$.

• True, but I initially thought of that as being equivalent to the union of two countable sets, and wasn't sure it I would be appealing to the theorem I noted in the question. – mlchristians Jul 12 at 17:05
• That's fair. And if you don't want to mention that theorem to the students, you don't necessarily have to. In this specific case, it should be intuitively clear that this is valid, even though technically, the rigorous proof might be slightly more complicated. – Calvin Godfrey Jul 12 at 17:10