## 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}\)