Definition 9.18.
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.
Read Definition 9.18 and Definition 9.4 and Definition 9.8 once more and complete the definitions in Checkpoint 9.19.
Checkpoint 9.19. Definition of cardinality.
Complete the following:
Let \(A\) and \(B\) be nonempty sets.
We say that \(A\) and \(B\) have the same
- select
- cardinality
- depth
- height
- volume
- width
if there exists
- select
- a good
- an injective
- an invertible
- a nice
- an onto
function \(f:A\to B\text{.}\)
We say that \(A\) is
- select
- finite
- infinite
- good
- bad
- nice
- boring
if for some \(n\in\mathbb{N}\) there is
- select
- a good
- an injective
- an invertible
- a nice
- an onto
function from \(A\) to
- select
- the set of natural numbers
- the set of integers
- {0,1,2,...,n-1}
.
If no such function exists we call \(A\)
- select
- finite
- infinite
- good
- bad
- nice
- boring
.
In the video in Figure 9.20 we recall the definitions above and give an overview over the remainder 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.21.
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 the infinitude of sets to proof that the set of natural numbers \(\N\) is infinite.
Theorem 9.22.
The set of natural numbers \(\N\) is infinite.
Proof.
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.
Because Definition 9.4 is formulated for any two sets it allows us to determine when two infinite sets have the same cardinality.
Definition 9.23.
We say a set \(S\) is countably infinite when \(S\) has the same cardinality as \(\N\text{.}\)
Checkpoint 9.24. Definition of countably infinite.
Complete the following:
Let \(A\) and \(B\) be nonempty sets.
We say that \(A\) and \(B\) have the same
- select
- cardinality
- depth
- height
- volume
- width
if there exists
- select
- a good
- an injective
- an invertible
- a nice
- an onto
function \(f:A\to B\text{.}\)
We say that \(A\) is
- select
- accountable
- countable
- innocent
- numbered
- unaccountable
- uncountable
if there is
- select
- a good
- an injective
- an invertible
- a nice
- an onto
function from \(A\) to the set of natural numbers.
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.
Theorem 9.25.
The set \(\{\dots,-3,-2,-1\}\) of negative integers is countably infinite.
Algebraic proof.
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*}
Then we have
\begin{equation*}
(g\circ f)(x)= g(f(x)) = g(-x) = -(-x) = x
\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.
Second proof.
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 \(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\) | \(-3\) | \(-3\) | \(-4\) | \(-5\) | \(-6\) | \(-7\) | \(-8\) | \(-9\) | \(-10\) | \(-11\) | \(-12\) | \(-13\) | \(-14\) | \(\cdots\) |
The inverse of the function \(f\) is \(f^{-1}:\N\to\{\dots,-3,-2,-1\}\to\N\) given by:
| \(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.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.
Theorem 9.26.
The set of integers \(\Z\) is countably infinite.
Proof.
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
| \(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. 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.
Theorem 9.27.
The set \(S\) of subsets of the set \(\N\) of natural numbers is not countably infinite.
Checkpoint 9.28. Finite and countably infinite sets.
For each of these sets decide whether it is finite, infinite and countable or infinite and not countable.
Select the correct statement:
- the set of odd natural numbers
- \(\displaystyle \lbrace 29, 30, 31,...,40\rbrace\)
- \(\displaystyle \lbrace40\rbrace\)
- \(\displaystyle \mathbb{Z}_{29}\)
