We have not addressed the cardinalities of the set of integers and the set of natural numbers. Before we address this issue, we define what we mean by finite and infinite sets.
To show that a non-empty set \(B\) is infinite, we need to show that there is no such \(n\) that will work. We do this by showing that whichever \(n\) we pick, we find that it is too small. That is if we choose any finite subset \(S\) of \(B\) with \(\nr S = n\) elements, there is an element of \(B\) that is not in \(S\text{.}\) Then \(B\) is infinite. In the formulation of the criterion, we do not need to mention the number \(n\text{,}\) it simply is the cardinality of \(S\text{.}\)
Let \(S\) be a finite subset of \(\N\text{.}\) Let \(b\) be the greatest of the elements of \(S\text{.}\) Then \(b+1\) is not an element of \(S\) but it is an element of \(\N\text{.}\) In this way we can find an element of \(\N\) that is not in \(S\) for any finite subset of \(S\) of \(\N\text{.}\) Thus by Theorem 9.21, the set of natural numbers \(\N\) is infinite.
Definition 9.23 yields surprising results. We show that the set of natural numbers \(\N\) and the set of negative integers have the same cardinality, which means that the set of negative integers is countably infinite.
By Definition 9.23, we can prove that the set \(\{\dots,-3,-2,-1\}\) of negative integers is countably infinite by proving that \(\Z\) has the same cardinality as \(\N\) By Definition 9.4 we can prove that \(\{\dots,-3,-2,-1\}\) has the same cardinality as \(\N\) by constructing an invertible function from \(\N\) to \(\Z\text{.}\) Consider the function
\begin{equation*}
f:\N\to\{\dots,-3,-2,-1\} \text{ given by }f(x)=-x
\end{equation*}
and let
\begin{equation*}
g:\{\dots,-3,-2,-1\}\to\N \text{ given by }g(x)=-x\text{.}
\end{equation*}
Thus \((g\circ f)=\id_\N\text{.}\) By Theorem 7.60 this means that \(f\) is invertible. So we have found an invertible function from \(\N\) to \(\{\dots,-3,-2,-1\}\text{.}\) By Definition 9.4 this means that \(\{\dots,-3,-2,-1\}\) and \(\N\) have the same cardinality. By Definition 9.23 this means that \(\{\dots,-3,-2,-1\}\) is countably infinite.
By Definition 9.23, we can prove that the set \(\{\dots,-3,-2,-1\}\) of negative integers is countably infinite by proving that \(\Z\) has the same cardinality as \(\N\) By Definition 9.4 we can prove that \(\{\dots,-3,-2,-1\}\) has the same cardinality as \(\N\) by constructing an invertible function from \(\N\) to \(\Z\text{.}\)
The existence of the inverse \(f^{-1}\) of \(f\) proofs that \(f\) is invertible. Because there is an invertible function from \(\N\) to \(\{\dots,-3,-2,-1\}\text{,}\) by Definition 9.4, the two sets \(\{\dots,-3,-2,-1\}\) and \(\N\) have the same cardinality. By Definition 9.23 this means that \(\{\dots,-3,-2,-1\}\) is countably infinite.
We now prove the even more surprising result that the set of natural numbers \(\N\) and the set of integers \(\Z\) have the same cardinality, which means that \(\Z\) is countably infinite.
By Definition 9.23, we can prove that the set of integers \(\Z\) is countably infinite by proving that \(\Z\) has the same cardinality as \(\N\) By Definition 9.4 we can prove that \(\Z\) has the same cardinality as \(\N\) by constructing an invertible function from \(\N\) to \(\Z\text{.}\) Consider the function \(f:\N\to\Z\) given by
It is not difficult to see that the function \(f\) is invertible. Thus \(\N\) and \(\Z\) have the same cardinality. This also means that \(\Z\) is countably infinite.
We end with remarking that not all infinite sets are countably infinite. For example the real numbers are not countably infinite. In the following theorem we give another example of a set that is not countably infinite. The existence of such a set means that there are different kinds of infinity.