Skip to main content
Mathematics LibreTexts

9.3: Uncountable Sets

  • Page ID
    7088
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\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}}\) \(\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}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Preview Activity \(\PageIndex{1}\): The Game of Dodge Ball

    (From The Heart of Mathematics: An Invitation to Effective Thinking by Edward B. Burger and Michael Starbird, Key Publishing Company, 屏幕快照 2019-04-22 下午4.18.03.png2000 by Edward B. Burger and Michael Starbird.)

    Dodge Ball is a game for two players. It is played on a game board such as the one shown in Figure 9.4. Player One has a 6 by 6 array to complete and Player Two has a 1 by 6 row to complete. Each player has six turns as described next.

    • Player One begins by filling in the first horizontal row of his or her table with a sequence of six X’s and O’s, one in each square in the first row.
    • Then Player Two places either an X or an O in the first box of his or her row. At this point, Player One has completed the first row and Player Two has filled in the first box of his or her row with one letter.
      屏幕快照 2019-04-22 下午4.07.02.png
    • The game continues with Player One completing a row with six letters (X’s and O’s), one in each box of the next row followed by Player Two writing one letter (an X or an O) in the next box of his or her row. The game is completed when Player One has completed all six rows and Player Two has completed all six boxes in his or her row.

    Winning the Game

    • Player One wins if any horizontal row in the 6 by 6 array is identical to the row that Player Two created. (Player One matches Player Two.)
    • Player Two wins if Player Two’s row of six letters is different than each of the six rows produced by Player One. (Player Two “dodges” Player One.)

    There is a winning strategy for one of the two players. This means that there is plan by which one of the two players will always win. Which player has a winning strategy? Carefully describe this winning strategy.

    Applying the Winning Strategy to Lists of Real Numbers

    Following is a list of real numbers between 0 and 1. Each real number is written as a decimal number.

    \(a_1 = 0.1234567890\) \(a_6 = 0.0103492222\)
    \(a_2 = 0.3216400000\) \(a_7 = 0.0011223344\)
    \(a_3 = 0.4321593333\) \(a_8 = 0.7077700022\)
    \(a_4 = 0.9120930092\) \(a_9 = 0.2100000000\)
    \(a_5 = 0.0000234102\) \(a_{10} = 0.9870008943\)

    Use a method similar to the winning strategy in Cantor’s dodge ball to write a real number (in decimal form) between 0 and 1 that is not in this list of 10 numbers.

    1. Do you think your method could be used for any list of 10 real numbers between 0 and 1 if the goal is to write a real number between 0 and 1 that is not in the list?
    2. Do you think this method could be extended to a list of 20 different real numbers? To a list of 50 different real numbers?
    3. Do you think this method could be extended to a list consisting of countably infinite list of real numbers?
    Preview Activity \(\PageIndex{2}\): Functions from a Set to Its Power Set

    Let \(A\) be a set. In Section 5.1, we defined the power set \(\mathcal{P}(A)\) of \(A\) to be the set of all subsets of \(A\). This means that

    \(X \in \mathcal{P}(A)\) if and only if \(X \subseteq A\).

    Theorem 5.5 in Section 5.1 states that if a set \(A\) has n elements, then \(A\) has \(2^{n}\) subsets or that \(\mathcal{P}(A)\) has \(2^{n}\) elements. Using our current notation for cardinality, this means that

    if card\((A) = n\), then card\((\mathcal{P}(A) = 2^{n}\).

    (The proof of this theorem was Exercise (17) on page 229.)

    We are now going to define and explore some functions from a set \(A\) to its power set \(\mathcal{P}(A)\). This means that the input of the function will be an element of \(A\) and the output of the function will be a subset of \(A\).

    1. Let \(A = \{1, 2, 3, 4\}\). Define \(f: A \to \mathcal{P}(A)\) by
      \(f(1) = \{1, 2, 3\}\) \(f(3) = \{1, 4\}\)
      \(f(2) = \{1, 3, 4\}\) \(f(4) = \{2, 4\}\).

      (a) Is \(1 \in f(1)\)? Is \(2 \in f(2)\)? Is \(3 \in f(3)\)? Is \(4 \in f(4)\)?
      (b) Determine \(S = \{x \in A\ |\ x \notin f(x)\}\).
      (c) Notice that \(S \in \mathcal{P}(A)\). Does there exist an element \(t\) in \(A\) such that \(f(t) = S\)? That is, is \(S \in \text{range}(f)\)?
    2. Let \(A = \{1, 2, 3, 4\}\). Define \(f: A \to \mathcal{P}(A)\) by \[f(x) = A - \{x\} \text{ for each } x \in A.\]
      (a) Determine \(f(1)\). Is \(1 \in f(1)\)?
      (b) Determine \(f(2)\). Is \(2 \in f(2)\)?
      (c) Determine \(f(3)\). Is \(3 \in f(3)\)?
      (d) Determine \(f(4)\). Is \(4 \in f(4)\)?
      (e) Determine \(S = \{x \in A\ |\ x \notin f(x)\}\).
      (f) Notice that \(S \in \mathcal{P}(A)\). Does there exist an element \(t\) in \(A\) such that \(f(t) = S\)? That is, is \(S \in \text{range}(f)\)?
    3. Define \(f: \mathbb{N} \to \mathcal{P}(\mathbb{N})\) by
      \[f(n) - \mathbb{N} - \{n^2, n^2 - 2n\} \text{, for each} n \in \mathbb{N}.\]
      (a) Determine \(f(1)\), \(f(2)\), \(f(3)\), and \(f(4)\). In each of these cases, determine if \(k \in f(k)\).
      (b) Prove that if \(n > 3\), then \(n \in f(n)\). Hint: Prove that if \(n > 3\), then \(n^2 > n\) and \(n^2 - 2n > n\).
      (c) Determine \(S = \{x \in \mathbb{N}\ |\ x \notin f(x)\}\).
      (d) Notice that \(S \in \mathcal{P}(\mathbb{N})\). Does there exist an element \(t\) in \(\mathbb{N}\) such that \(f(t) = S\)? That is, is \(S \in \text{range}(f)\)?

    We have seen examples of sets that are countably infinite, but we have not yet seen an example of an infinite set that is uncountable. We will do so in this section. The first example of an uncountable set will be the open interval of real numbers (0, 1). The proof that this interval is uncountable uses a method similar to the winning strategy for Player Two in the game of Dodge Ball from Preview Activity 1. Before considering the proof, we need to state an important results about decimal expressions for real numbers.

    Decimal Expressions for Real Numbers

    In its decimal form, any real number a in the interval (0, 1) can be written as \(a = 0.a_{1}a_{2}a_{3}a_{4} ...\), where each \(a_i\) is an integer with \(0 \le a_i \le 9\). For example,

    \(\dfrac{5}{12} = 0.416666...\)

    We often abbreviate this as \(\dfrac{5}{12} = 0.41\bar{6}\) to indicate that the 6 is repeated. We can also repeat a block of digits. For example, \(\dfrac{5}{26} = 0.19\overline{230769}\) to indicate that the block 230769 repeats. That is

    \(\dfrac{5}{26} = 0.19230769230769230769...\)

    There is only one situation in which a real number can be represented as a decimal in more than one way. A decimal that ends with an infinite string of 9’s is equal to one that ends with an infinite string of 0’s. For example, 0.3199999... . represents the same real number as 0.3200000... . Geometric series can be used to prove that a decimal that ends with an infinite string of 9’s is equal to one that ends with an infinite string of 0’s, but we will not do so here.

    Definition

    A decimal representation of a real number \(a\) is in normalized form provided that there is no natural number \(k\) such that for all natural numbers \(n\) with \(n > k\), \(a_n = 9\). That is, the decimal representation of \(a\) is in normalized form if and only if it does not end with an infinite string of 9’s.

    One reason the normalized form is important is the following theorem (which will not be proved here).

    Theorem 9.21

    Two decimal numbers in normalized form are equal if and only if they have identical digits in each decimal position.

    Uncountable Subsets of \(\mathbb{R}\)

    In the proof that follows, we will use only the normalized form for the decimal representation of a real number in the interval (0, 1).

    Theorem 9.22.

    The open interval (0, 1) is an uncountable set.

    Proof

    Since the interval (0, 1) contains the infinite subset�� \(\{\dfrac{1}{2}, \dfrac{1}{3}, \dfrac{1}{4}, ...\}\), we can use Theorem 9.10, to conclude that (0, 1) is an infinite set. So (0, 1) is either countably infinite or uncountable. We will prove that (0, 1) is uncountable by proving that any injection from (0, 1) to \(\mathbb{N}\) cannot be a surjection, and hence, there is no bijection between (0, 1) and \(\mathbb{N}\).

    So suppose that the function \(f: \mathbb{N} \to (0, 1)\) is an injection. We will show that \(f\) cannot be a surjection by showing that there exists an element in (0, 1) that cannot be in the range of \(f\). Writing the images of the elements of \(\mathbb{N}\) in normalized form, we can write

    \(f(1) = 0.a_{11} a_{12} a_{13} a_{14} a_{15} ...\)
    \(f(2) = 0.a_{21} a_{22} a_{23} a_{24} a_{25} ...\)
    \(f(3) = 0.a_{31} a_{32} a_{33} a_{34} a_{35} ...\)
    \(f(4) = 0.a_{41} a_{42} a_{43} a_{44} a_{45} ...\)
    \(f(5) = 0.a_{51} a_{52} a_{53} a_{54} a_{55} ...\)
    ...
    \(f(n) = 0.a_{n1} a_{n2} a_{n3} a_{n4} a_{n5} ...\)
    ...

    Notice the use of the double subscripts. The number \(a_{ij}\) is the \(j\)th digit to the right of the decimal point in the normalized decimal representation of \(f(i)\).

    We will now construct a real number \(b = 0.b_{1} b_{2} b_{3} b_{4} b_{5} ...\) in (0, 1) and in normalized form that is not in this list.

    Note: The idea is to start in the upper left corner and move down the diagonal in a manner similar to the winning strategy for Player Two in the game in Preview Activity 1. At each step, we choose a digit that is not equal to the diagonal digit.

    Start with \(a_{11}\) in \(f(1)\). We want to choose \(b_1\) so that \(b_1 \ne 0\), \(b_1 \ne a_{11}\), and \(b_1 \ne 9\). (To ensure that we end up with a decimal that is in normalized form, we make sure that each digit is not equal to 9.) We then repeat this process with \(a_{22}\), \(a_{33}\), \(a_{44}\), \(a_{55}\), and so on. So we let \(b\) be the real number \(b = 0.b_{1} b_{2} b_{3} b_{4} b_{5} ...\), where for each \(k \in \mathbb{N}\)

    \(b_k = \begin{cases} 3 & \text{ if \(a_{kk} \ne 3\)} \\ 5 & \text{ if \(a_{kk} = 3\).} \end{cases}\)

    (The choice of 3 and 5 is arbitrary. Other choices of distinct digits will also work.)

    Now for each \(n \in \mathbb{N}\), \(b \ne f(n)\) since \(b\) and \(f(n)\) are in normalized form and \(b\) and \(f(n)\) differ in the \(n\)th decimal place. This proves that any function from \(\mathbb{N}\) to (0, 1) cannot be surjection and hence, there is no bijection from \(\mathbb{N}\) to (0, 1). Therefore, (0, 1) is not countably infinite and hence must be an uncountable set.

    Progress Check 9.23 (Dodge Ball and Cantor’s Diagonal Argument)

    The proof of Theorem 9.22 is often referred to as Cantor’s diagonal argument. It is named after the mathematician Georg Cantor, who first published the proof in 1874. Explain the connection between the winning strategy for Player Two in Dodge Ball (see Preview Activity 1) and the proof of Theorem 9.22 using Cantor’s diagonal argument.

    Answer

    Add texts here. Do not delete this text first.

    The open interval (0, 1) is our first example of an uncountable set. The cardinal number of (0, 1) is defined to be \(c\), which stands for the cardinal number of the continuum. So the two infinite cardinal numbers we have seen are \(\aleph_0\) for countably infinite sets and \(c\).

    Definition

    A set \(A\) is said to have cardinality \(c\) provided that \(A\) is equivalent to (0, 1). In this case, we write card\((A) = c\) and say that the cardinal number of \(A\) is \(c\).

    The proof of Theorem 9.24 is included in Progress Check 9.25.

    Theorem 9.24.

    Let \(a\) and \(b\) be real numbers with \(a < b\). The open interval \((a, b)\) is uncountable and has cardinality \(c\).

    Proof

    Add proof here and it will automatically be hidden

    Progress Check 9.25 (Proof of Theorem 9.24)
    1. In Part (3) of Progress Check 9.2, we proved that if \(b \in \mathbb{R}\) and \(b > 0\), then the open interval (0, 1) is equivalent to the open interval (0, \(b\)). Now let \(a\) and \(b\) be real numbers with \(a < b\). Find a function
      \[f: (0, 1) \to (a, b)\]
      that is a bijection and conclude that \((0, 1) \thickapprox (a, b)\).
      Hint: Find a linear function that passes through the points (0, \(a\)) and (1, \(b\)). Use this to define the function \(f\). Make sure you prove that this function \(f\) is a bijection.
    2. Let \(a, b, c, d\) be real numbers with \(a < b\) and \(c < d\). Prove that \((a, b) \thickapprox (c, d)\).
    Answer

    Add texts here. Do not delete this text first.


    Theorem 9.26.

    The set of real numbers \(\mathbb{R}\) is uncountable and has cardinality \(c\).

    Proof

    Let \(f: (-\dfrac{\pi}{2}, \dfrac{\pi}{2}) \to \mathbb{R}\) be defined by \(f(x) = tan x\), for each \(x \in \mathbb{R}\). The function \(f\) is as bijection and, hence, \((-\dfrac{\pi}{2}, \dfrac{\pi}{2}) \thickapprox \mathbb{R}\). So by Theorem 9.24, \(\mathbb{R}\) is uncountable and has cardinality \(c\).

    Cantor’s Theorem

    We have now seen two different infinite cardinal numbers, \(\aleph_0\) and \(c\). It can seem surprising that there is more than one infinite cardinal number. A reasonable question at this point is, “Are there any other infinite cardinal numbers?” The astonishing answer is that there are, and in fact, there are infinitely many different infinite cardinal numbers. The basis for this fact is the following theorem, which states that a set is not equivalent to its power set. The proof is due to Georg Cantor (1845–1918), and the idea for this proof was explored in Preview Activity 2. The basic idea of the proof is to prove that any function from a set \(A\) to its power set cannot be a surjection.

    Theorem 9.27 (Cantor’s Theorem).

    For every set \(A\), \(A\) and \(\mathcal{P}(A)\) do not have the same cardinality.

    Proof

    Let \(A\) be a set. If \(A = \emptyset\), then \(\mathcal{P}(A) = \{\emptyset\}\), which has cardinality 1. Therefore, \(\emptyset\) and \(\mathcal{P}(\emptyset)\) do not have the same cardinality.

    Now suppose that \(A \ne \emptyset\), and let \(f: A \to \mathcal{P}(A)\). We will show that \(f\) cannot be a surjection, and hence there is no bijection from \(A\) to \(\mathcal{P}(A)\). This will prove that \(A\) is not equivalentt to \(\mathcal{P}(A)\). Define

    \(S = \{x \in A\ |\ x \notin f(x)\}\).

    Assume that there exists a \(t\) in \(A\) such that \(f(t) = S\). Now, either \(f \in S\) to \(t \notin S\).

    • If \(t \in S\), then \(t \in \{x \in A\ |\ x \notin f(x)\}\). By the definition of \(S\), this means that \(t \notin f(t)\). However, \(f(t) = S\) and so we conclude that \(t \notin S\). But now we have \(t \in S\) and \(t \notin S\). This is a contradiction.
    • If \(t \notin S\), then \(t \notin \{x \in A\ |\ x \notin f(x)\}\). By the definition of \(S\), this means that \(t \in f(t)\). However, \(f(t) = S\) and so we conclude that \(t \in S\). But now we have \(t \notin S\) and \(t \in S\). This is a contradiction.

    So in both cases we have arrived at a contradiction. This means that there does not exist a \(t\) in \(A\) such that \(f(t) = S\). Therefore, any function from \(A\) to \(\mathcal{P}(A)\) is not a surjection and hence not a bijection. Hence, \(A\) and \(\mathcal{P}(A)\) do not have the same cardinality.

    corollary 9.28.

    \(\mathcal{P}(\mathbb{N})\) is an infinite set that is not countably infinite.

    Proof

    Since \(\mathcal{P}(\mathbb{N})\) contains the infinite subset \(\{\{1\}, \{2\}, \{3\} ...\}\), we can use Theorem 9.10, to conclude that \(\mathcal{P}(\mathbb{N})\) is an infinite set. By Cantor’s Theorem (Theorem 9.27), \(\mathbb{N}\) and \(\mathcal{P}(\mathbb{N})\) do not have the same cardinality. Therefore, P.N/ is not countable and hence is an uncountable set.

    Some Final Comments about Uncountable Sets

    1. We have now seen that any open interval of real numbers is uncountable and has cardinality c. In addition, R is uncountable and has cardinality c. Now, Corollary 9.28 tells us that P.N/ is uncountable. A question that can be asked is,
      \[\text{“Does \(\mathcal{P}(\mathbb{N})\) have the same cardinality as \(\mathbb{R}\)?”}\]
      The answer is yes, although we are not in a position to prove it yet. A proof of this fact uses the following theorem, which is known as the Cantor-Schr\(\ddot{o}\)der-Bernstein Theorem.
      Theorem 9.29. Cantor-Schr\(\ddot{o}\)der-Bernstein

      Let \(A\) and \(B\) be sets. If there exist injections \(f: A \to B\) and \(g: B \to A\), then \(A \thickapprox B\)

      In the statement of this theorem, notice that it is not required that the function \(g\) be the inverse of the function \(f\). We will not prove the Cantor-Schr\(\ddot{o}\)der-Bernstein Theorem here. The following items will show some uses of this important theorem.
    2. The Cantor-Schr\(\ddot{o}\)der-Bernstein Theorem can also be used to prove that the closed interval [0, 1] is equivalent to the open interval (0, 1). See Exercise (6) on page 486.
    3. Another question that was posed earlier is,
      \[\text{“Are there other infinite cardinal numbers other than \(\aleph_0\) and \(c\)?”}\]

      Again, the answer is yes, and the basis for this is Cantor’s Theorem (Theorem 9.27). We can start with card\((\mathbb{N}) = \aleph_0\). We then define the following infinite cardinal numbers:
      \[\begin{array} {lll} {\text{card}(\mathcal{P}(\mathbb{N})) = \alpha_1.} & & {\text{card}(\mathcal{P}(\mathcal(\mathcal(\mathbb{N})))) = \alpha_1.} \\ {\text{card}(\mathcal{P}(\mathcal(\mathbb{N}))) = \alpha_1.} & & {...} \end{array}\]
      Cantor’s Theorem tells us that these are all different cardinal numbers, and so we are just using the lowercase Greek letter \(\alpha\) (alpha) to help give names to these cardinal numbers. In fact, although we will not define it here, there is a way to “order” these cardinal numbers in such a way that
      \[\aleph_0 < \alpha_1 < \alpha_2 < \alpha_3 < \cdot\cdot\cdot.\]
      Keep in mind, however, that even though these are different cardinal numbers, Cantor’s Theorem does not tell us that these are the only cardinal numbers.

    4. In Comment (1), we indicated that \(\mathcal{P}(\mathbb{N})\) and \(\mathbb{R}\) have the same cardinality. Combining this with the notation in Comment (3), this means that

      \[\alpha_1 = c.\]

      However, this does not necessarily mean that \(c\) is the “next largest” cardinal number after \(\aleph_0\). A reasonable question is, “Is there an infinite set with cardinality between \(\aleph_0\) and \(c\)?” Rewording this in terms of the real number line, the question is, “On the real number line, is there an infinite set of points that is not equivalent to the entire line and also not equivalent to the set of natural numbers?” This question was asked by Cantor, but he was unable to find any such set. He conjectured that no such set exists. That is, he conjectured that \(c\) is really the next cardinal number after \(\aleph_0\). This conjecture has come to be known as the Continuum Hypothesis. Stated somewhat more formally, the Continuum Hypothesis is

      \[\text{There is no set \(X\) such that \(\aleph_0 < \text{card}(X) < c\).}\]
      The question of whether the Continuum Hypothesis is true or false is one of the most famous problems in modern mathematics.

      Through the combined work of Kurt G\(\ddot{o}\)del in the 1930s and Paul Cohen in 1963, it has been proved that the Continuum Hypothesis cannot be proved or disproved from the standard axioms of set theory. This means that either the Continuum Hypothesis or its negation can be added to the standard axioms of set theory without creating a contradiction.


    Exercise 9.3
    1. Use an appropriate bijection to prove that each of the following sets has cardinality \(c\).

      (a) (0, \(\infty\))
      (b) (\(a\), \(\infty\)), for any \(a \in \mathbb{R}\)
      (c) \(\mathbb{R} - \{0\}\)
      (d) \(\mathbb{R} - \{a\}\), for any \(a \in \mathbb{R}\)
    2. Is the set of irrational numbers countable or uncountable? Prove that your answer is correct.
    3. Prove that if \(A\) is uncountable and \(A \subseteq B\), then \(B\) is uncountable.
    4. Do two uncountable sets always have the same cardinality? Justify your conclusion.
    5. Let \(C\) be the set of all infinite sequences, each of whose entries is the digit 0 or the digit 1. For example,
      \[\begin{array} {rcl} {(1, 0, 1, 0, 1, 0, 1, 0, ...)} &\in & {C;} \\ {(0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, ...)} &\in & {C;} \\ {(2, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, ...)} &\notin & {C.} \end{array}\]
      Is the set \(C\) a countable set or an uncountable set? Justify your conclusion.
    6. The goal of this exercise is to use the Cantor-Schr\(\ddot{o}\)der-Bernstein Theorem to prove that the cardinality of the closed interval [0, 1]�� is \(c\).

      (a) Find an injection \(f:(0, 1) \to [0, 1]\).
      (b) Find an injection \(h:[0, 1] \to (-1, 2)\).
      (c) Use the fact that \((-1, 2) \thickapprox (0, 1)\) to prove that there exists an injection \(g: [0, 1] \to (0, 1)\). (It is only necessary to prove that the injection \(g\) exists. It is not necessary to determine a specific formula for \(g(x)\).)
      Note: Instead of doing Part (b) as stated, another approach is to find an injection \(k: [0, 1] \to (0, 1)\). Then, it is possible to skip Part (c) and go directly to Part (d).
      (d) Use the Cantor-Schr\(\ddot{o}\)der-Bernstein Theorem to conclude that \([0, 1] \thickapprox (0, 1)\) and hence that the cardinality of [0, 1] is \(c\).
    7. In Exercise (6), we proved that the closed interval [0, 1] is uncountable and has cardinality \(c\). Now let \(a, b \in \mathbb{R}\) with \(a < b\). Prove that \([a, b] \thickapprox [0, 1]\) and hence that \([a, b]\) is counttable and has cardinality \(c\).
    8. Is the set of all finite subsets of \(\mathbb{N}\) countable or uncountable? Let \(F\) be the set of all finite subsets of \(\mathbb{N}\). Determine the cardinality of the set \(F\).

      Consider defining a function \(f: F \to \mathbb{N}\) that produces the following.
      \(\bullet\) If \(A = \{1, 2, 6\}\), then \(f(A) = 2^{1}3^{2}5^{6}\).
      \(\bullet\) If \(B = \{3, 6\}\), then \(f(B) = 2^{3}3^{6}\).
      \(\bullet\) If \(C = \{m_{1}, m_{2}, m_{3}, m_{4}\}\) with \(m_{1} < m_{2} < m_{3} < m_{4}\), then \(f(C) = 2^{m_1} 3^{m_2} 5^{m_3} 7^{m_4}\).
      It might be helpful to use the Fundamental Theorem of Arithmetic on page 432and to denote the set of all primes as \(P = \{p_1, p_2, p_3, p_4, ...\}\) with \(p_1 > p_2 < p_3 < p_4 \cdot\cdot\cdot\). Using the sets \(A\), \(B\), and \(C\) define above, we could then write
      \(f(A) = p_{1}^{1}p_{2}^{2}p_{3}^{6}\), \(f(B) = p_{1}^{3}p_{2}^{6}\), and \(f(C) = p_{1}^{m_1} p_{2}^{m_2} p_{3}^{m_3} p_{4}^{m_4}\).
    9. In Exercise (2), we showed that the set of irrational numbers is uncountable. However, we still do not know the cardinality of the set of irrational numbers. Notice that we can use \(\mathbb{Q}^c\) to stand for the set of irrational numbers.

      (a) Construct a function \(f: \mathbb{Q}^c \to \mathbb{R}\) that is an injection.

      We know that any real number a can be represented in decimal form as follows:
      \[a = A.a_{1}a_{2}a_{3}a_{4} \cdot\cdot\cdot a_{n} \cdot\cdot\cdot,\]
      where \(A\) is an integer and the decimal part (\(0.a_{1}a_{2}a_{3}a_{4} \cdot\cdot\cdot\)) is in normalized form. (See page 480.) We also know that the real number \(a\) is an irrational number if and only \(a\) has an infinite non-repeating decimal expansion. We now associate with \(a\) the real number
      \[A.a_{1}0a_{2}11a_{3}000a_{4}1111a_{5}00000a_{6}111111 \cdot\cdot\cdot .\]
      Notice that to construct the real number in (9.3.12), we started with the decimal expansion of a, inserted a 0 to the right of the first digit after the decimal point, inserted two 1’s to the right of the second digit to the right of the decimal point, inserted three 0’s to the right of the third digit to the right of the decimal point, and so on.

      (b) Explain why the real number in (9.3.12) is an irrational number.
      (c) Use these ideas to construct a function \(g: \mathbb{R} \to \mathbb{Q}^c\) that is an injection.
      (d) What can we now conclude by using the Cantor-Schr\(\ddot{o}\)der-Bernstein Theorem?
    10. Let \(J\) be the unit open interval. That is, \(J = \{x \in \mathbb{R}\ |\ 0 < x < 1\}\) and let \(S = \{(x, y) \in \mathbb{R} \times \mathbb{R} \ |\ 0 < x < 1 \text{ and } 0 < y <1\}\). We call \(S\) the unit open square. We will now define a function \(f\) from \(S\) to \(J\). Let \((a, b) \in S\) and write the decimal expansions of \(a\) and \(b\) in normalized form as
      \[\begin{array} {rcl} {a} &= & {0.a_{1}a_{2}a_{3}a_{4} \cdot\cdot\cdot a_{n} \cdot\cdot\cdot } \\ {b} &= & {0.b_{1}b_{2}b_{3}b_{4} \cdot\cdot\cdot b_{n} \cdot\cdot\cdot .} \end{array}\]
      We then define \(f(a, b) = 0.a_{1}b_{1}a_{2}b_{2}a_{3}b_{3}a_{4}b_{4} \cdot\cdot\cdot a_{n}b_{n} \cdot\cdot\cdot .\)

      (a) Determine the values of \(f(0.3, 0.625)\), \(f(\dfrac{1}{3}, \dfrac{1}{4})\), and \(f(\dfrac{1}{6}, \dfrac{5}{6})\).
      (b) If possible, find \((x, y) \in S\) such that \(f(x, y) = 0.2345\).
      (c) If possible, find \((x, y) \in S\) such that \(f(x, y) = \dfrac{1}{3}\).
      (d) If possible, find \((x, y) \in S\) such that \(f(x, y) = \dfrac{1}{2}\).
      (e) Explain why the function \(f: S \to J\) is an injection but is not a surjection.
      (f) Use the Cantor-Schr\(\ddot{o}\)der-Bernstein Theorem to prove that the cardinality of the unit open square \(S\) is equal to \(c\). If this result seems surprising, you are in good company. In a letter written in 1877 to the mathematician Richard Dedekind describing this result that he had discovered, Georg Cantor wrote, “I see it but I do not believe it.”

      Explorations and Activities
    11. The Closed Interval [0,1]. In Exercise (6), the Cantor-Schr\(\ddot{o}\)der-Bernstein Theorem was used to prove that the closed interval [0, 1] has cardinality \(c\). This may seem a bit unsatisfactory since we have not proved the Cantor-Schr\(\ddot{o}\)der-Bernstein Theorem. In this activity, we will prove that card\(([0, 1]) = c\) by using appropriate bijections.

      (a) Let \(f:[0, 1] \to [0, 1)\) by
      \[f(x) = \begin{cases} \dfrac{1}{2} & \text{ if \(x = 0\)} \\ \dfrac{1}{n + 1} & \text{ if \(x = \dfrac{1}{2}\) for some \(n \in \mathbb{N}\)} \\ x & \text{otherwise.} \end{cases}\]
      i. Determine \(f(0)\), \(f(1)\), \(f(\dfrac{1}{2})\), \(f(\dfrac{1}{3})\), \(f(\dfrac{1}{4})\), and \(f(\dfrac{1}{5})\).
      ii. Sketch a graph of the function \(f\). Hint: Start with the graph of \(y = x\) for \(0 \le x \le 1\). Remove the point (1, 1) and replace it with the point (1, \(\dfrac{1}{2}\)). Next, remove the point \((\dfrac{1}{2}, \dfrac{1}{2})\) and replace it with the point \((\dfrac{1}{2}, \dfrac{1}{3})\). Continue this process of removing points on the graph of \(y = x\) and replacing them with the points determined from the information in Part (11(a)i). Stop after repeating this four or five times so that pattern of this process becomes apparent.
      iii. Explain why the function \(f\) is a bijection.
      iv. Prove that \([0, 1] \thickapprox [0, 1)\).

      (b) Let \(g: [0, 1) \to (0, 1)\) by
      \[g(x) = \begin{cases} \dfrac{1}{n + 1} & \text{ if \(x = \dfrac{1}{2}\) for some \(n \in \mathbb{N}\)} \\ x & \text{otherwise.} \end{cases}\]
      i. Follow the procedure suggested in Part (11a) to sketch a graph of \(g\).
      ii. Explain why the function \(g\) is a bijection.
      iii. Prove that \([0, 1) \thickapprox (0, 1)\).
      (c) Prove that [0, 1] and [0, 1) are both uncountable and have cardinality \(c\).

    Answer

    Add texts here. Do not delete this text first.



    This page titled 9.3: Uncountable Sets is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Ted Sundstrom (ScholarWorks @Grand Valley State University) via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.