Infinite Sets

Introduction

Most of the interesting sets we have looked at have an infinite number of elements, the sets $\mathbb{Z}$, $\mathbb{Q}$, and $\mathbb{R}$ being the most important examples.

In the 19th century, mathematicians attempted to introduce rigor into calculus. In doing so, they undertook a comprehensive study of the properties of the real numbers. As the theory advanced, it soon became clear that infinite sets in general had to be studied.But the very idea of a set with an infinite number of elements was resisted for a long time, mainly because it seemed to lead to contradictions.

There is a way to show that two finite sets $A$ and $B$ have the same number of elements: find a bijective function with domain $A$ and codomain $B$.

Consider the set $\mathbb{Z}$ of integers and the set $\mathbb{E}$ of even integers. The function $f: \mathbb{Z} \to \mathbb{E}$ defined by $f(n) = 2n$ is a bijection between $\mathbb{Z}$ and $\mathbb{E}$.

Where we have the seeming contradiction of a set having the same size as one of its proper subsets.

Gradually, as the 19th century came to a close, these examples came to be seen as paradoxes rather than actual mathematical contradictions. Paradoxes, in this context, are seemingly contradictory statements that are actually true. In the last example, if we accept the fact that two sets having the same size means that there is a bijection between them, then it is a true statement to say that $\mathbb{Z}$ and $\mathbb{E}$ have the same size.

Countable Sets

Numerically Equivalent Sets

Cantor distinguished infinite sets by their “size” in the same way we discussed.

If $A$ and $B$ are numerically equivalent, we write $A \approx B$.

The definition of numerical equivalence actually defines an equivalence relation on the power set of $U$. Specifically, we have the following:

1. Reflectivity: For every set $A, A \approx A$
2. Symmetry: For all sets $A$ and $B$, if $A \approx B$, then $B \approx A$.
3. Transitivity: For all sets, $A, B$ and $C$, if $A \approx B$ and $B \approx C$ then $A \approx C$.

A set that is not finite is called an infinite set. The cardinality of a set is a measure of the size of a set. The cardinality or cardinal number of a finite set is the number of elements in the set. Every nonnegative integer then is a cardinal number.

Countable Sets

The most natural example of an infinite set, the one we first encounter in arithmetic, is the set $\mathbb{Z}^+$ of positive integers.

A set that is not countable is called uncountable.

Any two countably infinite sets then have the same cardinality. We denote this cardinality by $\mathcal{N}_0$ (read “aleph zero” or “aleph naught”). $\mathcal{N}_0$ is our first example of an infinite cardinal number.

Proof

Since $A$ is countably infinite, there exists a bijection $f: \mathbb{Z}^+ \to A$. To prove that $B$ is countably infinite, we will define a bijective function $g: \mathbb{Z}^+ \to B$. To do this, we first inductively define a collection of nonempty subsets of $\mathbb{Z}^+$.

Let $S_1 = \{i \in \mathbb{Z}^+|f(i) \in B\}$. $S_1$ is the set of positive integers that get mapped to $B$ by the function $f$. Since $f$ is surjective, $S_1$ is an infinite subset of $\mathbb{Z}^+$. Next we define $S_2$ as follows: by the Well-Ordering Principle, $S_1$ has a smallest element that we will call $k_1$. So we let $S_2 = S_1 - {k_1}$.

Now suppose that we have defined $n - 1$ nonempty subsets of $\mathbb{Z}^+$, $S_1, S_2, \cdots, S_{n - 1}$. By the Well-Ordering Principle, each $S_i$ has a smallest element. Call it $k_i$ We define $S_n = S_1 - \{k_1, k_2, \cdots, k_{n - 1}\}$. Then $S_n$ is nonempty since $B$ is an infinite set. Let $k_n$ be the smallest element of $S_n$. Now we define $g: \mathbb{Z}^+ \to B$ by $g(n) = f( k_n)$.

Note that the sequence of integers $k_1, k_2, \cdots$ has the property that if $n < m$, then $k_n < k_m$. We now show that $g$ is a bijective function. To see that $g$ is injective, let $n, m \in \mathbb{Z}^+$ and suppose that $g(n) = g(m)$. Then $f(k_n) = f(k_m)$. Since $f$ is injective, we have $k_n = k_m$. It now follows from the above remark that $n = m$. Therefore, $g$ is injective.

To prove that $g$ is surjective, let $b \in B$. We must find $n \in \mathbb{Z}^+$ such that $g(n) = b$. Since $f$ is surjective, there exists $t \in \mathbb{Z}^+$ such that $f(t) = b$. Note that $t \in S_1$ since $f(t) \in B$. Let $m$ be the number of integers in $S_1$ that are less than $t$. If there are no such integers, that is, if $m = 0$, then $t = k_1$. Otherwise the integers that are less than $t$ are $k_1, k_2, \cdots, k_m$. Since $S_{m+1} =S_1 - \{k_1, k_2, \cdots, k_m\}$, $t$ must be the smallest element of $S_{m + 1}$ and hence $t =k_{m+1}$. Thus if $m = 0$ or not, $g(m + 1) = f(t) = b$. This proves that $g$ is surjective.

Since $g$ is a bijection, it follows that $B$ is countably infinite.

We have seen that a set $A$ is countably infinite if there is a bijection from $\mathbb{Z}^+$ to $A$. Sometimes it may be difficult or cumbersome to define such a function.

In our next result, we prove that we only have to find a surjective function from $\mathbb{Z}^+$ to $A$.

Proof

We will inductively define a bijective function $g: \mathbb{Z}^+ \to A$.

Let $g(1) = f(1)$. Let $n_2$ be the smallest positive integer such that $f(n_2) \neq g(1)$. Let $g(2) = f(n_2)$. Now suppose that $k \in \mathbb{Z}^+$ and $g(1), g(2), \cdots, g(k - 1)$ have been defined. Let $n_k$ be the smallest positive integer such that $f(n_k) \in A - \{g(1), g(2), \cdots, g(k - 1)\}$. We define $g(k) = f(n_k)$. This definition gives a function from $\mathbb{Z}^+$ to $A$. From the definition of $g$, $g(k) \neq g(i)$ for any $i = 1, 2, \cdots, k - 1$. Thus $g$ is injective.

We now prove that $g$ is surjective. Let $a \in A$. Since $f$ is surjective, $a$ is in the image of $f$. Let $t$ be the smallest positive integer such that $f(t) = a$. Then $f(t) \neq f(i)$ for any $i = 1, 2, \cdots, t - 1$. Let $r$ be the number of distinct elements from among $f(1), f(2), \cdots, f(t - 1)$. Then $g(1), g(2), \cdots, g(r)$ are equal to $f(1), f(2), \cdots, f(t - 1)$ in some order.

Hence $t$ is the smallest positive integer such that $f(t) \in A - \{g(1), g(2), \cdots, g(r)\}$. It follows from the definition of $g$ that $g(r + 1) = f(t) = a$, proving that $g$ is surjective.

We have thus constructed a bijection from $\mathbb{Z}^+$ to $A$ and so $A$ is countably infinite.

If $f: \mathbb{Z}^+ \to U$ is a sequence and we write $a_n = f(n)$ for each $n \in \mathbb{Z}^+$, then the sequence can be expressed in the form $\{a_1, a_2, a_3, \cdots\}$ or more simply $\{a_n\}^{\infty}_{n=1}$. Note that the elements of the sequence are not necessarily distinct. In fact, they would all assume the same value if $f$ is a constant function.

Unions of Countable Sets

We now consider the question of whether there are “bigger” sets than $\mathbb{Z}$ that are countable.

Proof

Since each $A_i$ is countably infinite, there is a bijection $f_i: \mathbb{Z}^+ \to A_i$ for each $i = 1, 2, \cdots k$. Let $A = A_1 \cup A_2 \cup \cdots \cup A_k$. We will define a surjective function $f: \mathbb{Z}^+ \to A$. Such that $A$ is countably finite. We let

$$ f(1) = f_1(1) \\ f(2) = f_2(1) \\ \vdots \\ f(k) = f_k(1) \\ f(k + 1) = f_{k + 1}(1) \\ \vdots \\ f(2k) = f_{k}(2) \\ \vdots $$

An explicit formula for $f$ can be given as follows. Let $n \in \mathbb{Z}^+$. Using a modification of the Division Algorithm, we can write $n = mk + r$ where $m$ is a nonnegative integer and $r$ is an integer such that $1 \leq r \leq k$. Moreover, $r$ and $m$ are unique. Then $f(n) = f(mk + r) = f_r(m + 1)$.

Now $f$ is not necessarily injective but it is surjective. To see this, let $a \in A$. Then $a \in A_i$ for some $i$. Since $f_i$ is surjective, there exists $n \in \mathbb{Z}^+$ such that $f_i(n) = a$. Then $f((n - 1)k + i) = f_i(n) = a$. Therefore $f$ is surjective and our proof is complete.

The Rationals Are Countable

We now consider the set $\mathbb{Q}$ of rational numbers. At first glance it seems to be a “much bigger” set than $\mathbb{Z}$. This means that any interval on the real line, no matter how small, will contain infinitely many rational numbers. Despite this fact, the rational numbers do form a countable set.

Proof

We will show that the set $\mathbb{Q}^+$ of positive rationals is countably infinite. Since it is easy to define a bijection from $\mathbb{Q}^+ to \mathbb{Q}^-$, it will follow that the set $\mathbb{Q}^-$ of negative rationals is also countably infinite. Since $\mathbb{Q} = \mathbb{Q}^+ \cup \mathbb{Q}^- \cup \{0\}$, Theorem 6.1.8 implies that $\mathbb{Q}$ is countably infinite.

Any element of $\mathbb{Q}^+$ can be written as $a/b$ where $a, b \in \mathbb{Z}^+$. So we can write the elements of $\mathbb{Q}^+$ in a rectangular array where the elements in a given row all have the same denominator; that is, the numbers in row $1$ have denominator $1$, the numbers in row $2$ have denominator $2$, the numbers in row $3$ have denominator $3$, and so on. It will look like this:

Note that elements of $\mathbb{Q}^+$ appear more than once in this listing. In fact each element appears an infinite number of times. We define $f: \mathbb{Z}^+ \to \mathbb{Q}^+$ by going through this array diagonally:

That is, we can define:

$$ \begin{matrix} f(1) = \frac{1}{1} & f(2) = \frac{1}{2} & f(3) = \frac{2}{1} & f(4) = \frac{3}{1} & f(5) = \frac{2}{2} \\[12pt] f(6) = \frac{1}{3} & f(7) = \frac{1}{4} & f(8) = \frac{2}{3} & \cdots \end{matrix} $$

We will forego giving an explicit formula for $f$ since it is complicated. But it is clear from the construction of $f$ that every positive rational is in the image of $f$. It is now a consequence of Theorem 6.1.6 that $\mathbb{Q}^+$ is countably infinite. We can now conclude that $\mathbb{Q}$ is a countably infinite set.

Cartesian Products of Countable Sets

Another set that is “bigger” than $\mathbb{Z}$ is the Cartesian product $\mathbb{Z} \times \mathbb{Z}$, the set of all ordered pairs of integers.

So far we have only looked at in finite sets that are countable. There are indeed in finite sets that are not countable: the set $\mathbb{R}$ of real numbers is the outstanding example.