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.
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.
Read Definition 9.2.1 and Definition 9.1.4 and Definition 9.1.8 once more and complete the definitions in Checkpoint 9.2.2.
Checkpoint 9.2.2. 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
select
a good
an injective
an invertible
a nice
an onto
We say that \(A\) is
select
finite
infinite
good
bad
nice
boring
select
a good
an injective
an invertible
a nice
an onto
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.2.3 we recap 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.2.4.
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.2.5.
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.2.4, the set of natural numbers \(\N\) is infinite.
Because Definition 9.1.4 is formulated for any two sets it allows us to determine when two infinite sets have the same cardinality.
Definition 9.2.6.
We say a set \(S\) is countably infinite when \(S\) has the same cardinality as \(\N\text{.}\)
Checkpoint 9.2.7. 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
select
a good
an injective
an invertible
a nice
an onto
We say that \(A\) is
select
accountable
countable
innocent
numbered
unaccountable
uncountable
select
a good
an injective
an invertible
a nice
an onto
Definition 9.2.6 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.2.8.
The set \(\{\dots,-3,-2,-1\}\) of negative integers is countably infinite.
Algebraic proof.
By Definition 9.2.6, 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.1.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
and let
Then we have
Thus \((g\circ f)=\id_\N\text{.}\) By Theorem 7.5.13 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.6 this means that \(\{\dots,-3,-2,-1\}\) is countably infinite.
Second proof.
By Definition 9.2.6, 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.1.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.1.4, the two sets \(\{\dots,-3,-2,-1\}\) and \(\N\) have the same cardinality. By Definition 9.2.6 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.2.9.
The set of integers \(\Z\) is countably infinite.
Proof.
By Definition 9.2.6, 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.1.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.2.10.
The set \(S\) of subsets of the set \(\N\) of natural numbers is not countably infinite.
Checkpoint 9.2.11. 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}\)