Integers are Countably Infinite

From ProofWiki
Jump to: navigation, search

Theorem

The set $\Z$ of integers is countably infinite.


Proof

Define the inclusion mapping $i: \N \to \Z$.

From Inclusion Mapping is Injection, $i: \N \to \Z$ is an injection.

Thus there exists an injection from $\N$ to $\Z$.

Hence $\Z$ is infinite.


Next, let us arrange $\Z$ in the following order:

$\Z = \set {0, 1, -1, 2, -2, 3, -3, \ldots}$

Then we can directly see that we can define a mapping $\phi: \Z \to \N$ as follows:

$\forall x \in \Z: \map \phi x = \begin{cases} 2 x - 1 & : x > 0 \\ -2 x & : x \le 0 \end{cases}$


This is shown to be an injection as follows:

Let $\map \phi x = \map \phi y$.

Then one of the following applies:

$(1): \quad -2 x = -2 y$ in which case $x = y$
$(2): \quad 2 x - 1 = 2 y - 1$ in which case $2 x = 2 y$ and so $x = y$
$(3): \quad 2 x - 1 = -2 y$ in which case $y = -x + \frac 1 2$ and therefore $y \notin \Z$
$(4): \quad 2 y - 1 = -2 x$ in which case $x = -y + \frac 1 2$ and therefore $x \notin \Z$.

So $2 x - 1 = -2 y$ and $2 y - 1 = -2 x$ can't happen and so $x = y$.

Thus $\phi$ is injective.

The result follows from Domain of Injection to Countable Set is Countable.

$\blacksquare$


Sources