math.wiki
Analysis › The real numbers › Countable and uncountable sets
Sign in

Countable and uncountable sets

The rationals can be listed and the reals cannot, but the usual proof leans on decimal expansions whose existence it never proved. Which property of the real line makes it too big to list, and where do decimals come from?

Where you are 4 in The real numbers

Why this exists

Countable sets listed \mathbb{Z}, \mathbb{N} \times \mathbb{N} and \mathbb{Q}, and Uncountable sets and the diagonal argument proved \mathbb{R} cannot be listed. That proof left two debts. It used the fact that every number in [0, 1) has a decimal expansion, stated there without proof; and it never said which axiom of the real line is responsible. The axioms of The real numbers as an ordered field cannot be enough, since \mathbb{Q} satisfies all of them and is countable.

This lesson pays both debts with the least-upper-bound property of Least upper bounds and completeness. A version of Cantor’s first proof (1874) shows, with no decimals at all, that every sequence of reals misses a point of every interval. The supremum then builds the decimal expansion of every number. Last, the union of countably many countable sets, only sketched in Countable sets, is proved in full.

Definition

A set is countable when it is finite or there is a bijection f : \mathbb{N} \to A, with \mathbb{N} = \{0, 1, 2, \dots\}; otherwise it is uncountable. Sequences in this course start at n = 1, so a countably infinite set is the set of terms \{x_n : n \ge 1\} of a sequence with no repeats, x_n = f(n - 1).

A closed bounded interval is [a, b] with a \le b; its length is b - a. Intervals I_1, I_2, I_3, \dots are nested when I_{n+1} \subseteq I_n for every n. For sets A_1, A_2, \dots,

\begin{aligned} \bigcap_{n=1}^{\infty} A_n &= \{x : x \in A_n \text{ for every } n\}, \\ \bigcup_{n=1}^{\infty} A_n &= \{x : x \in A_n \text{ for some } n\}. \end{aligned}

A digit is an integer from 0 to 9. A sequence of digits d_1, d_2, d_3, \dots has truncations

D_n = \sum_{k=1}^{n} \frac{d_k}{10^k}, \qquad D_0 = 0,

and it represents x, written x = 0.d_1 d_2 d_3 \dots, when x = \sup\{D_n : n \ge 1\}. The D_n are the partial sums of \sum d_k 10^{-k}; they increase, so this supremum is the sum used in Uncountable sets and the diagonal argument (an increasing bounded sequence converges to its supremum, Convergence of sequences). The standard expansion of x \in [0, 1) is a digit sequence with

D_n \le x < D_n + 10^{-n} \quad \text{for every } n \ge 1.

Intuition

0
\displaystyle \frac{1}{3}
\displaystyle \frac{2}{3}
1
I_0
I_1
x_1
\displaystyle \frac{2}{3}
\displaystyle \frac{7}{9}
\displaystyle \frac{8}{9}
1
I_1
I_2
x_2
\displaystyle \frac{2}{3}
\displaystyle \frac{19}{27}
\displaystyle \frac{20}{27}
\displaystyle \frac{7}{9}
I_2
I_3
Figure 1The trisection rule of Result 2 on the list \displaystyle 0, 1, \frac{1}{2}, \dots (Example 1). Each row is the current interval at full width. The first third is kept unless it holds x_n; then the last third is kept. Here \displaystyle x_3 = \frac{1}{2} is not in I_2 at all.

Picture an opponent reading out a list x_1, x_2, x_3, \dots while you hold a closed interval. At each turn you shrink to a third of it that avoids the number just read. The intervals are nested, and the least-upper-bound property says some point survives in all of them. That point was avoided at every turn, so it is on no list position.

Decimals run the same machine the other way. The first digit of x picks which of the ten intervals \displaystyle [\frac{j}{10}, \frac{j+1}{10}] holds x, the second picks a tenth of that, and so on. The digits are the address of x in a nest of shrinking intervals, and the supremum is what turns an address back into a number.

Results

Results of Countable sets are cited as CS1 to CS11, of Uncountable sets and the diagonal argument as CD1 to CD9, of Least upper bounds and completeness as C1 to C7 and of The Archimedean property and density of the rationals as A1 to A6.

1. Nested intervals. Let I_n = [a_n, b_n], with a_n \le b_n, be nested closed bounded intervals. Then \sup\{a_n : n \ge 1\} lies in every I_n, so \bigcap_{n=1}^{\infty} I_n is nonempty. If moreover for every \varepsilon > 0 some n has b_n - a_n < \varepsilon, the intersection is exactly one point.

2. Cantor’s theorem on intervals. Let \{x_n\}_{n=1}^{\infty} be any sequence of real numbers and let a < b. There is y \in [a, b] with y \ne x_n for every n. Consequently [a, b] and (a, b) are uncountable whenever a < b, and \mathbb{R} is uncountable.

3. Decimal expansions. (a) Every digit sequence represents exactly one number x \in [0, 1], and D_n \le x \le D_n + 10^{-n} for every n. (b) Every x \in [0, 1) has exactly one standard expansion. Its digits and truncations are

\begin{aligned} d_n &= \lfloor 10^n x \rfloor - 10 \lfloor 10^{n-1} x \rfloor, \\ D_n &= \frac{\lfloor 10^n x \rfloor}{10^n}. \end{aligned}

4. Countable unions. If A_1, A_2, A_3, \dots are countable sets, then \bigcup_{n=1}^{\infty} A_n is countable. So is the union of the sets of any countable family (finitely many sets, or sets listed as a sequence).

Why it is true

Result 1. Proof. Nesting means a_n \le a_{n+1} \le b_{n+1} \le b_n for every n, so the a_n increase and the b_n decrease. Let m and n be any indices. If m \le n, then a_m \le a_n \le b_n; if m > n, then a_m \le b_m \le b_n. So a_m \le b_n for all m, n, and C4 gives that y = \sup\{a_m\} and \inf\{b_n\} exist with y \le \inf\{b_n\}. Hence a_n \le y \le b_n for every n.

If z also lies in every I_n, then \lvert y - z \rvert \le b_n - a_n for every n. Were y \ne z, the hypothesis with \varepsilon = \lvert y - z \rvert would give an n with b_n - a_n < \lvert y - z \rvert. So z = y. \square

Result 2. Proof. Put I_0 = [a, b]. Given a closed interval I_{n-1} = [c, d] of length L = d - c > 0, form its first and last thirds,

\begin{aligned} F &= [c, c + \tfrac{L}{3}], \\ G &= [d - \tfrac{L}{3}, d]. \end{aligned}

They are disjoint, since \displaystyle c + \frac{L}{3} < d - \frac{L}{3}. Let I_n = F if x_n \notin F and I_n = G if x_n \in F; in the second case x_n \notin G by disjointness. Either way I_n is a closed subinterval of I_{n-1} of length \displaystyle \frac{L}{3} > 0 with x_n \notin I_n. This defines nested intervals I_1, I_2, \dots by recursion, and Result 1 gives y in all of them. Then y \in I_1 \subseteq [a, b], and for each n, y \in I_n while x_n \notin I_n, so y \ne x_n.

Now suppose [a, b] were countable. It is infinite (the numbers \displaystyle a + \frac{b - a}{k}, k \ge 1, are all different), so there would be a bijection f : \mathbb{N} \to [a, b], and the sequence x_n = f(n - 1) would have every point of [a, b] as a term, against the first part. The open interval (a, b) contains \displaystyle [a + \frac{b - a}{3}, b - \frac{b - a}{3}], and \mathbb{R} contains [0, 1], so both are uncountable by CD6. \square

No digit appears in this proof. Completeness enters once, through the supremum in Result 1.

Result 3. Proof. (a) Each D_{n+1} - D_n = d_{n+1} 10^{-(n+1)} \ge 0, so the D_n increase from D_0 = 0. For m > n, since 9 \cdot 10^{-k} = 10^{-(k-1)} - 10^{-k} the sum telescopes:

D_m - D_n \le \sum_{k=n+1}^{m} \frac{9}{10^k} = 10^{-n} - 10^{-m} < 10^{-n}.

For m \le n, D_m \le D_n. So D_n + 10^{-n} is an upper bound of \{D_m : m \ge 1\} for every n \ge 0, in particular 1 is. By the least-upper-bound property the set has a supremum x, unique by C1. As an upper bound, x \ge D_n; as the least one, x \le D_n + 10^{-n}. And 0 \le D_1 \le x \le 1.

(b) Let x \in [0, 1) and m_n = \lfloor 10^n x \rfloor (A3), so m_0 = 0 and m_n \le 10^n x < m_n + 1. Multiplying the case n - 1 by 10 gives 10 m_{n-1} \le 10^n x < 10 m_{n-1} + 10. The integer 10 m_{n-1} is at most 10^n x, so it is at most the greatest such integer, m_n; and m_n \le 10^n x < 10 m_{n-1} + 10 gives m_n \le 10 m_{n-1} + 9. So d_n = m_n - 10 m_{n-1} is a digit. The truncations telescope,

\begin{aligned} D_n &= \sum_{k=1}^{n} \left( \frac{m_k}{10^k} - \frac{m_{k-1}}{10^{k-1}} \right) \\ &= \frac{m_n}{10^n}, \end{aligned}

and dividing m_n \le 10^n x < m_n + 1 by 10^n gives D_n \le x < D_n + 10^{-n}. So x is an upper bound of the D_n. Given \varepsilon > 0, A2 gives n with \displaystyle \frac{1}{n} < \varepsilon, and Bernoulli’s inequality (The Archimedean property and density of the rationals) gives 10^n \ge 1 + 9n > n, so D_n > x - 10^{-n} > x - \varepsilon. By C2, x = \sup\{D_n\}: the digits represent x, as a standard expansion.

For uniqueness, let e_1, e_2, \dots be a standard expansion of x with truncations E_n. Then 10^n E_n = \sum_{k=1}^{n} e_k 10^{n-k} is an integer with 10^n E_n \le 10^n x < 10^n E_n + 1, so 10^n E_n = m_n by the uniqueness in A3. Thus E_n = D_n for every n, and e_n = 10^n (E_n - E_{n-1}) = d_n. \square

Result 4. Proof. Let U = \bigcup_{n=1}^{\infty} A_n. If U is empty it is finite; otherwise fix u \in U. Each nonempty A_n is countable, so there is a surjection g_n : \mathbb{N} \to A_n: a bijection if A_n is infinite, and if A_n = \{a_0, \dots, a_{r-1}\} with r \ge 1, the map j \mapsto a_{\min(j, r - 1)}. Choose one for each such n. Let p : \mathbb{N} \times \mathbb{N} \to \mathbb{N} be the bijection of CS6. For k \in \mathbb{N} write k = p(i, j) and put

F(k) = \begin{cases} g_{i+1}(j) & \text{if } A_{i+1} \ne \varnothing, \\ u & \text{if } A_{i+1} = \varnothing. \end{cases}

Every x \in U lies in some nonempty A_n, so x = g_n(j) for some j, and then x = F(p(n - 1, j)). So F : \mathbb{N} \to U is onto, and U is countable by CS4. A finite family is the case where A_n = \varnothing for all large n, and a family listed as a sequence is this case exactly. \square

The word “choose” picks a surjection for infinitely many sets at once, which uses the axiom of countable choice. When each A_n comes with its own list by a formula, as in Examples 4 and 6, no choice is needed.

Worked examples

Example 1

Sophia’s intervals

Sophia and Liam play a game. Liam names real numbers one at a time; Sophia starts with I_0 = [0, 1] and answers his nth number x_n with the interval I_n of the trisection rule in the proof of Result 2. Liam names \displaystyle 0, 1, \frac{1}{2}, \frac{1}{3}, \frac{2}{3}. Find I_1 to I_5, and a number in I_5.

Solution

The first third of [0, 1] is \displaystyle [0, \frac{1}{3}], which holds x_1 = 0, so Sophia keeps the last third: \displaystyle I_1 = [\frac{2}{3}, 1]. Its first third \displaystyle [\frac{2}{3}, \frac{7}{9}] misses x_2 = 1, so \displaystyle I_2 = [\frac{2}{3}, \frac{7}{9}]. In twenty-sevenths \displaystyle I_2 = [\frac{18}{27}, \frac{21}{27}], and \displaystyle x_3 = \frac{1}{2} is not even in I_2, so \displaystyle I_3 = [\frac{18}{27}, \frac{19}{27}]. Likewise \displaystyle x_4 = \frac{1}{3} is far away, so \displaystyle I_4 = [\frac{54}{81}, \frac{55}{81}]. Now \displaystyle x_5 = \frac{2}{3} = \frac{162}{243} is the left endpoint of I_4, inside its first third \displaystyle [\frac{162}{243}, \frac{163}{243}], so

I_5 = \left[\frac{164}{243}, \frac{165}{243}\right].

Since \displaystyle \frac{164}{243} \approx 0.67490 and \displaystyle \frac{165}{243} \approx 0.67901, the number 0.675 lies in I_5, and it is none of Liam’s five numbers. The closed endpoints mattered: \displaystyle \frac{2}{3} sat in I_1 to I_4, and only a closed third could catch it. However long Liam plays, Result 1 leaves a point in every I_n that he never names.

Example 2

Digits from floors

Find the first four digits of the standard expansion of \displaystyle \sqrt{2} - 1, justifying each floor by squaring integers. Then find the standard expansion of \displaystyle \frac{5}{16}, and show that its other expansion 0.3124999\ldots is not standard.

Solution

Here \displaystyle \lfloor 10^n(\sqrt{2} - 1) \rfloor = \lfloor 10^n \sqrt{2} \rfloor - 10^n, since 10^n is an integer. For n = 4, \displaystyle 10^4 \sqrt{2} = \sqrt{200{,}000{,}000} and

\begin{aligned} 14{,}142^2 &= 199{,}996{,}164 \le 200{,}000{,}000, \\ 14{,}143^2 &= 200{,}024{,}449 > 200{,}000{,}000, \end{aligned}

so \displaystyle \lfloor 10^4 \sqrt{2} \rfloor = 14{,}142 (for positive numbers squaring keeps order). In the same way m_1 = 4, m_2 = 41, m_3 = 414, m_4 = 4142, and d_n = m_n - 10 m_{n-1} gives the digits 4, 1, 4, 2: \displaystyle \sqrt{2} - 1 = 0.4142\ldots

For \displaystyle \frac{5}{16} = 0.3125: m_1 = 3, m_2 = 31, m_3 = 312, m_4 = 3125, and m_n = 3125 \cdot 10^{n-4} after that, so the standard expansion is 0.3125000\ldots For the other, E_4 = 0.3124 and E_4 + 10^{-4} = 0.3125 = x, so the strict inequality x < E_n + 10^{-n} fails at n = 4. By Result 3(a) it still represents \displaystyle \frac{5}{16}, which is why uniqueness needs the word standard.

Example 3

Two digits repeating

Prove from the definition that the digits 2, 7, 2, 7, \dots (that is, d_n = 2 for odd n and d_n = 7 for even n) represent \displaystyle \frac{3}{11}.

Solution

Proof. Group the digits in pairs. Since 99 \cdot 100^{-j} = 100^{-(j-1)} - 100^{-j}, the sum telescopes:

\begin{aligned} D_{2k} &= \sum_{j=1}^{k} \frac{27}{100^j} = \frac{27}{99}\left(1 - 100^{-k}\right) \\ &= \frac{3}{11}\left(1 - 100^{-k}\right). \end{aligned}

The truncations increase, so each D_n is at most D_{2k} for any 2k \ge n, which is less than \displaystyle \frac{3}{11}; so \displaystyle \frac{3}{11} is an upper bound. Let \varepsilon > 0. A2 gives k with \displaystyle \frac{1}{k} < \frac{11 \varepsilon}{3}, and 100^k > k by Bernoulli’s inequality, so \displaystyle \frac{3}{11} - D_{2k} = \frac{3}{11} \cdot 100^{-k} < \frac{3}{11k} < \varepsilon. By C2, the supremum is \displaystyle \frac{3}{11}. \square

As a check with Result 3(b): \displaystyle \lfloor \frac{30}{11} \rfloor = 2 and \displaystyle \lfloor \frac{300}{11} \rfloor = 27, so the standard expansion of \displaystyle \frac{3}{11} starts 0.27.

Example 4

A list of the fractions in the unit interval

Let F_n be the set of fractions \displaystyle \frac{k}{m} with integers 1 \le m \le n and 0 \le k \le m. List the members of F_1 in increasing order, then the members of F_2 not yet listed, then those of F_3, and so on, numbering positions from 1. Prove that every rational number in [0, 1] gets exactly one position, find the 12th term, and find the position of \displaystyle \frac{3}{7}.

Solution

Each F_n is finite, so each block of the list is finite. A rational q \in [0, 1] is \displaystyle \frac{k}{m} in lowest terms with m \ge 1, and 0 \le k \le m because 0 \le q \le 1, so q \in F_m. It is listed once, in the block of the least n with q \in F_n, at a finite position. This is Result 4 for the finite sets F_n, with every list given by a rule.

The blocks are 0, 1 (positions 1, 2); \displaystyle \frac{1}{2} (3); \displaystyle \frac{1}{3}, \frac{2}{3} (4, 5); \displaystyle \frac{1}{4}, \frac{3}{4} (6, 7), since \displaystyle \frac{2}{4} = \frac{1}{2} is already listed; \displaystyle \frac{1}{5}, \dots, \frac{4}{5} (8 to 11); and \displaystyle \frac{1}{6}, \frac{5}{6} (12, 13). So the 12th term is \displaystyle \frac{1}{6}. Since 7 is prime, F_7 adds all six fractions \displaystyle \frac{k}{7}, at positions 14 to 19, and \displaystyle \frac{3}{7} is at position 16.

Example 5

Uncountably many positive numbers

Let A be an uncountable set of positive real numbers. Prove that some positive integer n makes \displaystyle A \cap (\frac{1}{n}, \infty) uncountable, and deduce that for every M some finitely many members of A have sum greater than M.

Solution

Proof. For each a \in A, A2 gives n with \displaystyle \frac{1}{n} < a. So

A = \bigcup_{n=1}^{\infty} \left( A \cap \left(\tfrac{1}{n}, \infty\right) \right).

If every set in this union were countable, A would be countable by Result 4. So some \displaystyle A_n = A \cap (\frac{1}{n}, \infty) is uncountable, hence infinite. Given M, take k > nM (A1) different members of A_n; each exceeds \displaystyle \frac{1}{n}, so their sum exceeds \displaystyle \frac{k}{n} > M. \square

Example 6

Disjoint open intervals

Prove that every set \mathcal{S} of pairwise disjoint open intervals (a, b), a < b, is countable.

Solution

Proof. Let c : \mathbb{Q} \to \mathbb{N} be the injection of CS8. For I \in \mathcal{S} the set \{c(q) : q \in \mathbb{Q} \cap I\} is a subset of \mathbb{N}, nonempty by A4; let \varphi(I) be its least member. If \varphi(I) = \varphi(J) = k, the one rational q with c(q) = k lies in both I and J, so I \cap J \ne \varnothing, and disjointness forces I = J. So \varphi : \mathcal{S} \to \mathbb{N} is injective and \mathcal{S} is countable by CS4. \square

The least member is a rule, so no choice is used. Openness carried the argument: every open interval holds a rational. The uncountably many disjoint sets \{x\}, x \in \mathbb{R}, hold none.

Boundaries

Result 1 needs closed and bounded. The intervals \displaystyle (0, \frac{1}{n}] are nested and bounded, but any x > 0 escapes \displaystyle (0, \frac{1}{n}] once \displaystyle \frac{1}{n} < x (A2), and 0 is in none: the intersection is empty. The closed intervals [n, \infty) are nested with empty intersection by A1.

Result 1 needs completeness. In \mathbb{Q} nested closed intervals can share no point (Exercise 12). That must happen, since \mathbb{Q} is countable (CS8): fed a list of the rationals in [0, 1], the trisection rule produces rational intervals whose one common real point is irrational. The proof of Result 2 fails in \mathbb{Q} exactly at the supremum.

Result 2 needs a < b. [a, a] = \{a\} is countable, and there is nothing to cut in thirds.

Result 4 needs a countable family. \mathbb{R} = \bigcup_{x \in \mathbb{R}} \{x\} is a union of finite sets, uncountably many of them.

Representation is onto, not one to one. Every digit sequence names a number in [0, 1], but 0.3125000\ldots and 0.3124999\ldots name the same one; uniqueness holds only for standard expansions (and CD3 describes every such pair).

Where this goes next

Limits of sequences, epsilon and N reads Result 3 as D_n \to x. The monotone convergence theorem returns to nested intervals through monotone sequences. Subsequences and Bolzano-Weierstrass finds a convergent subsequence in every bounded sequence, and one proof of it runs the same nest with halves. Cantor's theorem: no set matches its power set shows the uncountable sets come in ever larger sizes.

Exercises

Nested intervals

  1. Run the trisection rule on [0, 1] for \displaystyle x_1 = \frac{1}{5}, \displaystyle x_2 = \frac{3}{4}, \displaystyle x_3 = \frac{9}{10}. Find I_1, I_2, I_3, and a number in I_3 that is none of the three.
  2. Run the trisection rule on [0, 1] with x_n = 0 for every n. Prove that \displaystyle I_n = [\frac{2}{3}, \frac{2}{3} + 3^{-n}] for every n \ge 1, and find \bigcap_{n=1}^{\infty} I_n.
  3. Find \displaystyle \bigcap_{n=1}^{\infty} [-\frac{1}{n}, 2 + \frac{1}{n}] and \displaystyle \bigcap_{n=1}^{\infty} [2 - \frac{1}{n}, 2 + \frac{1}{n^2}].

Decimal expansions

  1. Find the first five digits of the standard expansion of \displaystyle \frac{2}{13} from m_n = \lfloor 10^n x \rfloor.
  2. Find the first four digits of the standard expansion of \displaystyle \sqrt{3} - 1, justifying each floor by squaring integers.
  3. Write the standard and the other expansion of \displaystyle \frac{7}{40}. For the other, find the least n with x = E_n + 10^{-n}.
  4. Prove from the definition that the digits 9, 9, 9, \dots represent 1.

Countable unions

  1. Let \displaystyle B_n = \{\frac{k}{2^n} : k \text{ an integer}, 0 \le k \le 2^n\} for n \ge 0. List B_0 in increasing order, then the new members of B_1, then of B_2, and so on, each block in increasing order, numbering from 1. Find the positions of \displaystyle \frac{5}{8} and \displaystyle \frac{11}{16}, the 20th term, and the position of \displaystyle \frac{2j + 1}{2^n} for n \ge 1 and 0 \le j < 2^{n-1}.
  2. Let R_n be the set of real roots of the polynomials x^2 + bx + c with integers \lvert b \rvert \le n and \lvert c \rvert \le n. Find the members of R_1, and prove that \bigcup_{n=1}^{\infty} R_n is countable.

Proofs

  1. Let \{x_n\} be a sequence of reals and a < b. Prove that (a, b) contains uncountably many numbers that are not terms of the sequence.
  2. Replace thirds by closed halves: keep \displaystyle [c, \frac{c + d}{2}] unless it holds x_n, else keep \displaystyle [\frac{c + d}{2}, d]. Show this rule can keep x_n. Then show that open halves avoid x_n but can lose Result 1.
  3. Let \displaystyle a_n = \frac{\lfloor 10^n \sqrt{2} \rfloor}{10^n} and b_n = a_n + 10^{-n}. Prove that the sets \{q \in \mathbb{Q} : a_n \le q \le b_n\} are nested and nonempty, yet no rational lies in all of them.
  4. Prove that the set of finite subsets of \mathbb{N} is countable.
  5. Prove that the standard expansion of x \in [0, 1) never ends in 9s: no N has d_n = 9 for every n > N.
  6. Let A \subseteq \mathbb{R} be uncountable. Prove that some a \in A has A \cap (a - \varepsilon, a + \varepsilon) uncountable for every \varepsilon > 0.
Answers
  1. \displaystyle I_1 = [\frac{2}{3}, 1], since \displaystyle \frac{1}{5} \in [0, \frac{1}{3}]. The first third of I_1 is \displaystyle [\frac{2}{3}, \frac{7}{9}], which holds \displaystyle \frac{3}{4}, so \displaystyle I_2 = [\frac{8}{9}, 1]. Its first third \displaystyle [\frac{24}{27}, \frac{25}{27}] holds \displaystyle \frac{9}{10} (as 0.888\ldots < 0.9 < 0.925\ldots), so \displaystyle I_3 = [\frac{26}{27}, 1]. The number 1 is in I_3 and is none of the three.
  2. 0 lies in \displaystyle [0, \frac{1}{3}], so \displaystyle I_1 = [\frac{2}{3}, 1], the case n = 1. If \displaystyle I_n = [\frac{2}{3}, \frac{2}{3} + 3^{-n}], its first third is \displaystyle [\frac{2}{3}, \frac{2}{3} + 3^{-n-1}], which misses 0, so I_{n+1} has the claimed form. The point \displaystyle \frac{2}{3} is in every I_n, and the lengths satisfy \displaystyle 3^{-n} < \frac{1}{n}, so by A2 and Result 1 the intersection is \displaystyle \{\frac{2}{3}\}.
  3. [0, 2] and \{2\}. If 0 \le x \le 2, then \displaystyle -\frac{1}{n} \le x \le 2 + \frac{1}{n} for every n. If x < 0, A2 gives \displaystyle \frac{1}{n} < -x, so \displaystyle x < -\frac{1}{n}; if x > 2, take \displaystyle \frac{1}{n} < x - 2. For the second, 2 is in every interval and the lengths \displaystyle \frac{1}{n} + \frac{1}{n^2} \le \frac{2}{n} get below any \varepsilon, so Result 1 leaves only 2.
  4. m_1, \dots, m_5 = 1, 15, 153, 1538, 15384 (for example \displaystyle \frac{20{,}000}{13} = 1538.46\ldots), so the digits are 1, 5, 3, 8, 4: \displaystyle \frac{2}{13} = 0.15384\ldots
  5. 17^2 = 289 \le 300 < 324 = 18^2, 173^2 = 29{,}929 \le 30{,}000 < 30{,}276 = 174^2, 1732^2 = 2{,}999{,}824 \le 3{,}000{,}000 < 3{,}003{,}289 = 1733^2 hold. Last, 17{,}320^2 = 299{,}982{,}400 and 300{,}017{,}041 = 17{,}321^2 lie on either side of 300{,}000{,}000. So m_n = 7, 73, 732, 7320 and the digits are 7, 3, 2, 0: \displaystyle \sqrt{3} - 1 = 0.7320\ldots
  6. Standard: 0.175000\ldots; other: 0.174999\ldots Its E_1 + 10^{-1} = 0.2 and E_2 + 10^{-2} = 0.18 differ from x, and E_3 + 10^{-3} = 0.174 + 0.001 = 0.175, so n = 3.
  7. Proof. Telescoping as in Result 3(a), D_n = \sum_{k=1}^{n} 9 \cdot 10^{-k} = 1 - 10^{-n} < 1, so 1 is an upper bound. Given \varepsilon > 0, choose \displaystyle n > \frac{1}{\varepsilon} (A2); then \displaystyle 10^{-n} < \frac{1}{n} < \varepsilon and D_n > 1 - \varepsilon. By C2 the supremum is 1. \square
  8. The list runs \displaystyle 0, 1, \frac{1}{2}, \frac{1}{4}, \frac{3}{4}, \frac{1}{8}, \dots The new members of B_n, n \ge 1, are the odd numerators \displaystyle \frac{2j + 1}{2^n}; blocks before them hold 2 + 1 + 2 + \dots + 2^{n-2} = 2^{n-1} + 1 terms, so \displaystyle \frac{2j + 1}{2^n} is at position 2^{n-1} + 2 + j. Then \displaystyle \frac{5}{8} is at 8, \displaystyle \frac{11}{16} at 15, and position 20 is n = 5, j = 2: the term \displaystyle \frac{5}{32}.
  9. R_1 holds 0, 1, -1, \displaystyle \frac{1 + \sqrt{5}}{2}, \displaystyle \frac{1 - \sqrt{5}}{2}, \displaystyle \frac{-1 + \sqrt{5}}{2} and \displaystyle \frac{-1 - \sqrt{5}}{2}, seven numbers, from x^2 - 1, x^2 \pm x, x^2 \pm x - 1 and x^2; the others have negative discriminant. Each R_n is finite, since (2n + 1)^2 polynomials have at most two roots each, and finite sets are countable, so Result 4 applies.
  10. Proof. The set T = \{x_n : n \ge 1\} is countable, since n \mapsto x_{n+1} maps \mathbb{N} onto it (CS4). If (a, b) \setminus T were countable, then (a, b) = ((a, b) \setminus T) \cup ((a, b) \cap T) would be countable by CS5 and CS7, against Result 2. \square
  11. On [0, 1] with \displaystyle x_1 = \frac{1}{2}, the left half holds x_1, so the rule keeps \displaystyle [\frac{1}{2}, 1], which holds it too: closed halves share the midpoint. With open halves and x_n = 1 for every n, the rule keeps (0, 2^{-n}) each time. These are nested, but any y > 0 has \displaystyle 2^{-n} < \frac{1}{n} < y for some n, and 0 is in none, so the intersection is empty. The proof needs two disjoint closed pieces, such as the thirds.
  12. Proof. With \displaystyle m_n = \lfloor 10^n \sqrt{2} \rfloor, the proof of Result 3(b) (which used x < 1 only for m_0 = 0) gives 10 m_n \le m_{n+1} \le 10 m_n + 9. Dividing by 10^{n+1}, a_n \le a_{n+1} and \displaystyle b_{n+1} = \frac{m_{n+1} + 1}{10^{n+1}} \le \frac{10 m_n + 10}{10^{n+1}} = b_n, so the sets are nested; each holds the rational a_n. Also \displaystyle a_n \le \sqrt{2} < b_n, and the lengths 10^{-n} fall below any \varepsilon, so by Result 1 the only real number in every [a_n, b_n] is \displaystyle \sqrt{2}, which is irrational (Irrational numbers). \square
  13. Proof. Let P_n be the set of subsets of \{0, 1, \dots, n\}, a finite set of 2^{n+1} members. A finite nonempty S \subseteq \mathbb{N} lies in P_{\max S}, and \varnothing \in P_0. So the finite subsets are \bigcup_{n \ge 0} P_n, countable by Result 4. \square
  14. Proof. Suppose d_n = 9 for every n > N. Then for n > N, telescoping gives D_n = D_N + 10^{-N} - 10^{-n}, so x \ge D_n for every n gives x \ge D_N + 10^{-N} - 10^{-n}. But the standard inequality gives x < D_N + 10^{-N}, so \varepsilon = D_N + 10^{-N} - x > 0. By A2 and Bernoulli’s inequality some n > N has \displaystyle 10^{-n} < \frac{1}{n} < \varepsilon, and then x \ge D_N + 10^{-N} - 10^{-n} > D_N + 10^{-N} - \varepsilon = x, a contradiction. \square
  15. Proof. Suppose not: each a \in A has \varepsilon_a > 0 with A \cap (a - \varepsilon_a, a + \varepsilon_a) countable. Let \mathcal{J} be the set of pairs (r, s) of rationals with r < s and A \cap (r, s) countable. It injects into \mathbb{N} \times \mathbb{N} by (r, s) \mapsto (c(r), c(s)), with c from CS8, and composing with the bijection p of CS6 gives an injection into \mathbb{N}, so it is countable by CS4. For a \in A, A4 gives rationals r \in (a - \varepsilon_a, a) and s \in (a, a + \varepsilon_a). Then A \cap (r, s) \subseteq A \cap (a - \varepsilon_a, a + \varepsilon_a) is countable by CS5, so (r, s) \in \mathcal{J}, and a \in A \cap (r, s). So A = \bigcup_{(r, s) \in \mathcal{J}} A \cap (r, s), a union of a countable family of countable sets, countable by Result 4. That contradicts A uncountable. \square
math.wiki · updated 2026-11-17 · CC-BY-SA-4.0