Skip to main content
\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Mathematics LibreTexts

9.2: Infinite Sets

  • Page ID
    9108
  • [ "article:topic", "Cantor\u2019s Theorem", "authorname:eboman" ]

    \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    Skills to Develop

    • Explain Infinite sets

    The following theorem follows directly from our previous work with the NIP and will be very handy later. It basically says that a sequence of nested closed intervals will still have a non-empty intersection even if their lengths do not converge to zero as in the NIP.

    Theorem \(\PageIndex{1}\)

    Let \(\left ( [a_n, b_n] \right )_{n=1}^{\infty }\) be a sequence of nested intervals such that \(\lim_{n \to \infty } \left | b_n - a_n \right | > 0\). Then there is at least one \(c ∈ \mathbb{R}\) such that \(c ∈ [a_n, b_n]\) for all \(n ∈ N\).

    Proof

    By Corollary 7.4.1 of Chapter 7, we know that a bounded increasing sequence such as \((a_n)\) converges, say to \(c\). Since \(a_n ≤ a_m ≤ b_n\) for \(m > n\) and \(\lim_{m \to \infty } a_m = c\), then for any fixed \(n\), \(a_n ≤ c ≤ b_n\). This says \(c ∈ [a_n, b_n]\) for all \(n ∈ N\).

    Exercise \(\PageIndex{1}\)

    Suppose \(\lim_{n \to \infty } \left | b_n - a_n \right | > 0\). Show that there are at least two points, \(c\) and \(d\), such that \(c ∈ [a_n,b_n]\) and \(d ∈ [a_n,b_n]\) for all \(n ∈ N\).

    Our next theorem says that in a certain, very technical sense there are more real numbers than there are counting numbers 2. This probably does not seem terribly significant. After all, there are real numbers which are not counting numbers. What will make this so startling is that the same cannot be said about all sets which strictly contain the counting numbers. We will get into the details of this after the theorem is proved.

    Theorem \(\PageIndex{2}\): Cantor, 1874

    Let \(S = \left ( s_n \right )_{n=1}^{\infty }\) be a sequence of real numbers. There is a real number \(c\), which is not in 1 \(S\).

    Proof

    For the sake of obtaining a contradiction assume that the sequence \(S\) contains every real number; that is, \(S = \mathbb{R}\). As usual we will build a sequence of nested intervals \(\left ( [x_i, y_i] \right )_{i=1}^{\infty }\).

    Let \(x_1\) be the smaller of the first two distinct elements of \(S\), let \(y_1\) be the larger and take \([x_1, y_1]\) to be the first interval.

    Next we assume that \([x_{n-1}, y_{n-1}]\) has been constructed and build \([x_n, y_n]\) as follows. Observe that there are infinitely many elements of \(S\) in \((x_{n-1}, y_{n-1})\) since \(S = \mathbb {R}\). Let \(s_m\) and \(s_k\) be the first two distinct elements of \(S\) such that

    \[s_m,s_k \epsilon (x_{n-1}, y_{n-1})\]

    Take \(x_n\) to be the smaller and \(y_n\) to be the larger of \(s_m\) and \(s_k\). Then \([x_n, y_n]\) is the \(n_{th}\) interval.

    From the way we constructed them it is clear that

    \[[x_1, y_1] ⊇ [x_2, y_2] ⊇ [x_3, y_3] ⊇ .... \]

    Therefore by Theorem \(\PageIndex{1}\) there is a real number, say \(c\), such that

    \[c ∈ [x_n, y_n] \text{ for all } n ∈ \mathbb {N}\]

    In fact, since \(x_1 < x_2 < x_3 ... < y_3 < y_2 < y_1\) it is clear that

    \[x_n < c < y_n, ∀n\]

    We will show that \(c\) is the number we seek. That the inequalities in the above formula \(\PageIndex{4}\) are strict will play a crucial role.

    To see that \(c \not{\epsilon }\; S\) we suppose that \(c ∈ S\) and derive a contradiction.

    So, suppose that \(c = s_p\) for some \(p ∈ \mathbb {N}\). Then only \(\{s_1, s_2,..., s_{p-1}\}\) appear before \(s_p\) in the sequence \(S\). Since each \(x_n\) is taken from \(S\) it follows that only finitely many elements of the sequence (\(x_n\)) appear before \(s_p = c\) in the sequence as well.

    Let \(x_l\) be the last element of (\(x_n\)) which appears before \(c = s_p\) in the sequence and consider \(x_{l+1}\). The way it was constructed, \(x_{l+1}\) was one of the first two distinct terms in the sequence \(S\) strictly between \(x_l\) and \(y_l\), the other being \(y_{l+1}\). Since \(x_{l+1}\) does not appear before \(c = s_p\) in the sequence and \(x_l < c < y_l\), it follows that either \(c = x_{l+1}\) or \(c = y_{l+1}\). However, this gives us a contradiction as we know from equation \(\PageIndex{4}\) that \(x_{l+1} < c < y_{l+1}\).

    Thus \(c\) is not an element of \(S\).

    So how does this theorem show that there are “more” real numbers than counting numbers? Before we address that question we need to be very careful about the meaning of the word ’more’ when we’re talking about infinite sets.

    First let’s consider two finite sets, say \(A = {α,β,γ,δ}\) and \(B = {a,b,c,d,e}\). How do we know that \(B\) is the bigger set? (It obviously is.) Clearly we can just count the number of elements in both \(A\) and \(B\). Since \(|A| = 4\) and \(|B| = 5\) and \(4 < 5\). \(B\) is clearly bigger. But we’re looking for a way to determine the relative size of two sets without counting them because we have no way of counting the number of elements of an infinite set. Indeed, it isn’t even clear what the phrase “the number of elements” might mean when applied to the elements of an infinite set.

    When we count the number of elements in a finite set what we’re really doing is matching up the elements of the set with a set of consecutive positive integers, starting at \(1\). Thus since \[1 \leftrightarrow \alpha \\ 2 \leftrightarrow \beta \\ 3 \leftrightarrow \gamma \\ 4 \leftrightarrow \delta\] we see that \(|A| = 4\). Moreover, the order of the match-up is unimportant. Thus since \[2 \leftrightarrow e \\ 3 \leftrightarrow a \\ 5 \leftrightarrow b \\ 4 \leftrightarrow d \\ 1 \leftrightarrow c\] it is clear that the elements of \(B\) and the set \(\{1,2,3,4,5\}\) can be matched up as well. And it doesn’t matter what order either set is in. They both have \(5\) elements.

    Such a match-up is called a one-to-one correspondence. In general, if two sets can be put in one-to-one correspondence then they are the same “size.” Of course the word “size” has lots of connotations that will begin to get in the way when we talk about infinite sets, so instead we will say that the two sets have the same cardinality. Speaking loosely, this just means that they are the same size.

    More precisely, if a given set \(S\) can be put in one-to-one correspondence with a finite set of consecutive integers, say \(\{1,2,3,...,N\}\), then we say that the cardinality of the set is \(N\). But this just means that both sets have the same cardinality. It is this notion of one-to-one correspondence, along with the next two definitions, which will allow us to compare the sizes (cardinalities) of infinite sets.

    Definition \(\PageIndex{1}\)

    Any set which can be put into one-to-one correspondence with \(N = \{1,2,3,...\}\) is called a countably infinite set. Any set which is either finite or countably infinite is said to be countable.

    Since \(\mathbb{N}\) is an infinite set, we have no symbol to designate its cardinality so we have to invent one. The symbol used by Cantor and adopted by mathematicians ever since is \(\aleph _0\).3 Thus the cardinality of any countably infinite set is \(\aleph _0\).

    We have already given the following definition informally. We include it formally here for later reference.

    Definition: \(\PageIndex{2}\)

    If two sets can be put into one-to-one correspondence then they are said to have the same cardinality.

    With these two definitions in place we can see that Theorem \(\PageIndex{2}\) is nothing less than the statement that the real numbers are not countably infinite. Since it is certainly not finite, then we say that the set of real numbers is uncountable and therefore “bigger” than the natural numbers!

    To see this let us suppose first that each real number appears in the sequence \(\left ( s_n \right )_{n=1}^{\infty }\) exactly once. In that case the indexing of our sequence is really just a one-to-one correspondence between the elements of the sequence and \(\mathbb{N}\):

    \[1 \leftrightarrow s_1 \\ 2 \leftrightarrow s_2 \\ 3 \leftrightarrow s_3 \\ 4 \leftrightarrow s_4 \\ \vdots\]

    If some real numbers are repeated in our sequence then all of the real numbers are a subset of our sequence and will therefore also be countable.

    In either case, every sequence is countable. But our theorem says that no sequence in \(\mathbb{R}\) includes all of \(\mathbb{R}\). Therefore \(\mathbb{R}\) is uncountable.

    Most of the sets you have encountered so far in your life have been countable.

    Exercise \(\PageIndex{2}\)

    Show that each of the following sets is countable.

    1. \(\{2,3,4,5,...\} = \left \{ n \right \}_{n=2}^{\infty }\)
    2. \(\{0,1,2,3,...\} = \left \{ n \right \}_{n=0}^{\infty }\)
    3. \(\{1,4,9,16,...,n^2,...\} = \left \{ n^2 \right \}_{n=1}^{\infty }\)
    4. The set of prime numbers.
    5. \(\mathbb{Z}\)

    In fact, if we start with a countable set it is rather difficult to use it to build anything but another countable set.

    Exercise \(\PageIndex{3}\)

    Let \(\{A_i\}\) be a collection of countable sets. Show that each of the following sets is also countable:

    1. Any subset of \(A_1\).
    2. \(A_1 ∪ A_2\)
    3. \(A_1 ∪ A_2 ∪ A_3\)
    4. \(\bigcup_{i=1}^{n} A_i\) 
    5. \(\bigcup_{i=1}^{\infty } A_i\)

    It seems that no matter what we do the only example of an uncountably infinite set is \(\mathbb{R}\). But wait! Remember the rational numbers? They were similar to the real numbers in many ways. Perhaps they are uncountably infinite too?

    Alas, no. The rational numbers turn out to be countable too.

    Theorem \(\PageIndex{3}\)

    Show that \(\mathbb{Q}\) is countable.

    Sketch of Proof

    First explain how you know that all of the non-negative rational numbers are in this list:

    \[\frac{0}{1}, \frac{0}{2}, \frac{1}{1}, \frac{0}{3}, \frac{1}{2}, \frac{2}{1}, \frac{0}{4}, \frac{1}{3}, \frac{2}{2}, \frac{3}{1}, \cdots\]

    However there is clearly some duplication. To handle this, apply part (a) of Exercise \(\PageIndex{3}\). Does this complete the proof or is there more to do?

    Exercise \(\PageIndex{4}\)

    Prove Theorem \(\PageIndex{1}\)

    The following corollary says that the cardinality of the real numbers is much larger than the cardinality of the rational numbers, despite the fact that both are infinite.

    That is, as a subset of the reals, the rationals can be contained in a sequence of intervals, the sum of whose lengths can be arbitrarily small. In a sense this says that a countably infinite set is so small (on the transfinite scale) that it is “almost” finite.

    Usually we express this idea with the statement, “\(\mathbb{Q}\) is a set of measure zero in \(\mathbb{R}\).” The term “measure” has a precise meaning which we will not pursue. The following corollary contains the essence of the idea.

    Corollary \(\PageIndex{1}\)

    Let \(ε > 0\) be given. There is a collection of intervals in \(\mathbb{R}\), \(I_n = [a_n,b_n]\) such that

    \[\mathbb{Q} \subset \bigcup_{n=1}^{\infty } I_n\]

    and

    \[\sum_{n=1}^{\infty } (b_n - a_n) < \varepsilon\]

    Exercise \(\PageIndex{5}\)

    Prove Corollary \(\PageIndex{1}\).

    Hint

    If we had only finitely many rationals to deal with this would be easy. Let \(\{r_1, r_2, ..., r_k\}\) be these rational numbers and take \(a_n = r_n - \frac {ε}{2k}\) and \(b_n = r_n + \frac {ε}{2k}\). Then for all \(n = 1,..., k r_n ∈ [a_n, b_n]\) and

    \[\sum_{n=1}^{k} b_n - a_n = \sum_{n=1}^{k} \frac{\varepsilon }{k} = \varepsilon\]

    The difficulty is, how do we move from the finite to the infinite case?

    Notice how this idea hearkens back to the discussion of  Leibniz’s approach to the Product Rule. He simply tossed aside the expression \(dxdy\) because it was ‘infinitely small’ compared to either \(xdy\) or \(ydx\). Although this isn’t quite the same thing we are discussing here it is similar and it is clear that Leibniz’s insight and intuition were extremely acute. They were moving him in the right direction, at least.

    All of our efforts to build an uncountable set from a countable one have come to nothing. In fact many sets that at first “feel” like they should be uncountable are in fact countable. This makes the uncountability of \(\mathbb{R}\) all the more remarkable.

    However if we start with an uncountable set it is relatively easy to build others from it.

    Exercise \(\PageIndex{6}\)

    1. Let \((a,b)\) and \((c,d)\0 be two open intervals of real numbers. Show that these two sets have the same cardinality by constructing a one-to-one onto function between them.
    Hint

    A linear function should do the trick.

    1. Show that any open interval of real numbers has the same cardinality as \(\mathbb{R}\). 
    Hint

     Consider the interval \((-π/2,π/2)\).

    1. Show that \((0,1]\) and \((0,1)\) have the same cardinality.
    Hint

    Note that \(\{1,1/2,1/3,...\}\) and \(\{1/2,1/3,...\}\) have the same cardinality.

    1. Show that \([0,1]\) and \((0,1)\) have the same cardinality.

    References

    To streamline things, we are abusing notation here as we are letting \(S\) denote both the sequence (which is ordered) and the underlying (unordered) set of entries in the sequence.

    \(\aleph _0\) is the first letter of the Hebrew alphabet and is pronounced ”aleph.” \(\aleph _0\) is pronounced ”aleph null.”

    Contributor 

    • Eugene Boman (Pennsylvania State University) and Robert Rogers (SUNY Fredonia)