Definition 9.2.1.
A set \(A\) is called finite when \(A=\{\}\) or that there exists \(n\in\N\) and an invertible function \(f:A\to\Z_n\text{.}\)
A set that is not finite is called infinite.
Section 9.2 Infinite Sets
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.
The video in Figure 9.2.2 reviews the definitions above and gives an overview of the rest of the section.
To show that a non-empty set \(A\) is finite we find an \(n\in\N\) such that there is an invertible function from \(A\) to \(\Z_n\text{.}\)
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{.}\)
Theorem 9.2.3.
Let \(B\) be a set. If for each finite subset \(S\) of \(B\) there is an element \(x\in B\) with \(x\not\in S\text{,}\) then \(B\) is infinite.
We apply this criterion for infinite sets to prove that the set of natural numbers \(\N\) is infinite.
Theorem 9.2.4.
The set of natural numbers \(\N\) is infinite.
Proof.
Let \(S=\{\,\}\text{.}\) Then \(1\in\N\) but \(1\not\in S\).
Let \(S\) be a non-empty 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{.}\) So by Theorem 9.2.3, the set of natural numbers \(\N\) is infinite.
Because Definition 9.1.4 applies to any two sets, we can use it to decide when two infinite sets have the same cardinality.
Definition 9.2.5.
Definition 9.2.5 gives surprising results. We show that the set of natural numbers \(\N\) and the set of negative integers have the same cardinality. This means that the set of negative integers is countably infinite.
Theorem 9.2.6.
The set \(\{\dots,-3,-2,-1\}\) of negative integers is countably infinite.
Algebraic proof.
By Definition 9.2.5, we can prove that the set \(\{\dots,-3,-2,-1\}\) of negative integers is countably infinite. It is enough to prove that \(\{\dots,-3,-2,-1\}\) has the same cardinality as \(\N\text{.}\)
By Definition 9.1.4 we can prove that \(\{\dots,-3,-2,-1\}\) has the same cardinality as \(\N\) by building an invertible function from \(\N\) to \(\{\dots,-3,-2,-1\}\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*}
Then we have
\begin{equation*}
(g\circ f)(x)= g(f(x)) = g(-x) = -(-x) = x
\end{equation*}
So \((g\circ f)=\id_\N\text{.}\) By Theorem 7.6.11 this means that \(f\) is invertible. So we have found an invertible function from \(\N\) to \(\{\dots,-3,-2,-1\}\text{.}\) By Definition 9.1.4 this means that \(\{\dots,-3,-2,-1\}\) and \(\N\) have the same cardinality. By Definition 9.2.5 this means that \(\{\dots,-3,-2,-1\}\) is countably infinite.
Second proof.
By Definition 9.2.5, we can prove that the set \(\{\dots,-3,-2,-1\}\) of negative integers is countably infinite. It is enough to prove that \(\{\dots,-3,-2,-1\}\) has the same cardinality as \(\N\text{.}\)
By Definition 9.1.4 we can prove that \(\{\dots,-3,-2,-1\}\) has the same cardinality as \(\N\) by building an invertible function from \(\N\) to \(\{\dots,-3,-2,-1\}\text{.}\)
Consider the function \(f:\N\to\{\dots,-3,-2,-1\}\) given by:
| \(x\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) | \(9\) | \(10\) | \(11\) | \(12\) | \(13\) | \(14\) | \(\cdots\) |
| \(f(x)\) | \(-1\) | \(-2\) | \(-3\) | \(-4\) | \(-5\) | \(-6\) | \(-7\) | \(-8\) | \(-9\) | \(-10\) | \(-11\) | \(-12\) | \(-13\) | \(-14\) | \(\cdots\) |
| \(y\) | \(-1\) | \(-3\) | \(-3\) | \(-4\) | \(-5\) | \(-6\) | \(-7\) | \(-8\) | \(-9\) | \(-10\) | \(-11\) | \(-12\) | \(-13\) | \(-14\) | \(\cdots\) |
| \(f^{-1}(y)\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) | \(9\) | \(10\) | \(11\) | \(12\) | \(13\) | \(14\) | \(\cdots\) |
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.1.4, the two sets \(\{\dots,-3,-2,-1\}\) and \(\N\) have the same cardinality. By Definition 9.2.5 this means that \(\{\dots,-3,-2,-1\}\) is countably infinite.
Now we prove the even more surprising result that the set of natural numbers \(\N\) and the set of integers \(\Z\) have the same cardinality. This means that \(\Z\) is countably infinite.
Theorem 9.2.7.
The set of integers \(\Z\) is countably infinite.
Proof.
By Definition 9.2.5, we can prove that the set of integers \(\Z\) is countably infinite by proving that \(\Z\) has the same cardinality as \(\N\text{.}\) By Definition 9.1.4, we can prove that \(\Z\) has the same cardinality as \(\N\) by building an invertible function from \(\N\) to \(\Z\text{.}\) Consider the function \(f:\N\to\Z\) given by
| \(x\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) | \(9\) | \(10\) | \(11\) | \(12\) | \(13\) | \(14\) | \(\cdots\) |
| \(f(x)\) | \(0\) | \(1\) | \(-1\) | \(2\) | \(-2\) | \(3\) | \(-3\) | \(4\) | \(-4\) | \(5\) | \(-5\) | \(6\) | \(-6\) | \(7\) | \(\cdots\) |
It is not difficult to see that the function \(f\) is invertible. So \(\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.
