Closed uncountable subsets of the real line

Posted on June 3, 2010 by Dan Ma

This is post #12 of the series on the Euclidean topology of the real line. See the links at the bottom for other posts in the series.

In the previous post Perfect sets and Cantor sets, II, we show that every subset of the real line that is a perfect set contains a Cantor set and thus has cardinality continuum. We would like to add an observation that every uncountable closed subset of the real line contains a perfect set. Thus every uncountable closed subset of the real line contains a Cantor set and thus has the same cardinality as the real line itself.

Recall that a subset $A$ of the real line is a perfect set if it is closed and every point of $A$ is a limit point of $A$ . In the previous post Perfect sets and Cantor sets, II, we demonstrate a procedure for constructing a Cantor set out of any nonempty perfect set. In another post The Lindelof property of the real line, we show that every uncountable subset $A$ of the real line contains at least one of its limit points. Thus all but countably many points of $A$ are limit points of $A$ . Consequently, for any uncountable closed subset $A$ of the real line, all but countably many points of $A$ are limit points of $A$ . By removing the countably many non-limit points (isolated points), we have a perfect set.

Links to previous posts on the topology of the real line:
1. The Euclidean topology of the real line (1)
2. The Euclidean topology of the real line (2)
3. The Euclidean topology of the real line (3) – Completeness
4. The Euclidean topology of the real line (4) – Compactness
5. The Cantor bus tour
6. The Cantor set, I
7. The Cantor set, II
8. The Cantor set, III
9. Perfect sets and Cantor sets, I
10. The Lindelof property of the real line
11. Perfect sets and Cantor sets, II

Perfect sets and Cantor sets, II

Posted on May 30, 2010 by Dan Ma

This is post #11 of the series on the Euclidean topology of the real line. See the links at the bottom for other posts in the series.

In the previous post Perfect sets and Cantor sets, I, we show that every nonempty perfect set is uncountable. We now show that any perfect contains a Cantor set. Hence the cardinality of any perfect set is continuum.

Given a perfect set $W$ , we construct a Cantor set within $W$ . Consider the following cases:

Case 1. $W$ contains some bounded closed interval $[a,b]$ .
Case 2. $W$ does not any bounded closed interval.

If case 1 holds, then we can apply the middle third process on $[a,b]$ and produce a Cantor set. So in the remaining dicussion of this post, we assume case 2 holds. This means that for each closed interval $[a,b]$ , there is some $x \in [a,b]$ such that $x \notin W$ .

Background Discussion
Let $A \subset \mathbb{R}$ and $p \in A$ . The point $p$ is a right-sided limit point of $A$ if for each open interval $(a,b)$ containing $p$ , the open interval $(p,b)$ contains a point of $A$ . The point $p$ is a left-sided limit point of $A$ if for each open interval $(a,b)$ containing $p$ , the open interval $(a,p)$ contains a point of $A$ . The point $p$ is a two-sided limit point of $A$ if it is both a right-sided limit point and a left-sided limit point of $A$ . For the proof of the following lemma, see the post labeled #10 listed below.

In Lemma 2 below, we apply the least upper bound property and the greatest lower bound property. See the post labeled #4 listed below.

Key Lemmas for Construction

Lemma 1
Suppose that $X \subset \mathbb{R}$ is an uncountable set. Then $X$ contains a two-sided limit point.

As a corollary to the lemma 1, for the perfect set $W$ in question, all but countably many points of $W$ are two-sided limit points of $W$ .

Lemma 2
Suppose $E \subset \mathbb{R}$ is a nonempty perfect set that satisfies Case 2 indicated above. Suppose that for the closed interval $[a,b]$ , we have:

$(a,b) \cap E \ne \phi$ ,
the left endpoint $a$ is a right-sided limit point of $E$ ,
the right endpoint $b$ is a left-sided limit point of $E$ .

Then we have $a<a^*<b^*<b$ such that:

there are no points of $E$ in the open interval $(a^*,b^*)$ ,
the point $a^*$ is a left-sided limit point of $E$ ,
the point $b^*$ is a right-sided limit point of $E$ .

Proof. Since Case 2 holds, for the closed interval $[a,b]$ in question, there is some $x \in (a,b)$ such that $x \notin E$ . Then we can find an open interval $(c,d)$ such that $x \in (c,d)$ and $a<c<d<b$ and $(c,d) \cap E = \phi$ .

Any point in $(c,d)$ is an upper bound of $W_1=[a,c) \cap E$ . By the least upper bound property, $W_1$ has a least upper bound $a^*$ . Any point in $(c,d)$ is an lower bound of $W_2=(d,b] \cap E$ . By the greatest lower bound property, $W_2$ has a greatest lower bound $b^*$ . Then $a^*$ and $b^*$ satisfy the conclusion of the lemma. $\blacksquare$

Lemma 3
Suppose $E \subset \mathbb{R}$ is a nonempty perfect set. Suppose we have a closed interval $[s,t]$ such that the left endpoint $s$ is a right-sided limit point of $E$ and the right endpoint $t$ is a left-sided limit points of $E$ . Then we have $s<s_*<t_*<t$ such that:

the open interval $(s_*,t_*)$ contains points of $E$ ,
both endpoints $s_*$ and $t_*$ are two-sided limit points of $E$ ,
$t_*-s_*<0.5(t-s)$ .

Proof. Suppose we have a closed interval $[s,t]$ as described in the lemma. Then $E_1=[s,t] \cap E$ is a nonempty perfect set. Thus $E_1$ is uncountable. So pick $p \in (s,t)$ such that $p$ is a two-sided limit point of $E_1$ .

Choose open interval $(c,d)$ such that $s<c<p<d<t$ and $d-c<0.5(t-s)$ . Since $p$ is a two-sided limit point of $E_1$ , choose $s^*$ and $t^*$ such that $c<s^*<p$ , $p<t^*<d$ and both $s^*$ and $t^*$ are two-sided limit points of $E_1$ . It follows that $s^*$ and $t^*$ satisfy the conclusion of the lemma. $\blacksquare$

Lemma 4
Suppose $E \subset \mathbb{R}$ is a nonempty perfect set that satisfies Case 2 indicated above. Suppose we have a closed interval $[a,b]$ such that the endpoints are two-sided limit points of $E$ . Then we have disjoint closed intervals $K_0=[p_0,q_0]$ and $K_1=[p_1,q_1]$ such that

$K_0 \subset [a,b]$ and $K_1 \subset [a,b]$ ,
the lengths of both $K_0$ and $K_1$ are less then $0.5(b-a)$ ,
for each of $K_0$ and $K_1$ , the endpoints are two-sided limit points of $E$ .

Proof. This is the crux of the construction of a Cantor set from a perfect set and is the result of applying Lemma 2 and Lemma 3.

Applying Lemma 2 on $[a,b]$ and obtain the open interval $(a^*,b^*)$ . We remove the open interval $(a^*,b^*)$ from $[a,b]$ and obtain two disjoint closed intervals $[a,a^*]$ and $[b^*,b]$ . Each of these two subintervals contains points of the perfect set $W$ since the endpoints are limit points of $W$ in the correct direction.

Now apply Lemm 3 to shrink $[a,a^*]$ to obtain a smaller subinterval $K_0=[p_0,q_0]$ such that the length of $K_0$ is less than $0.5(a^*-a)$ and is thus less than $0.5(b-a)$ . Likewise, apply Lemma 3 on $[b^*,b]$ to obtain $K_1=[p_1,q_1]$ such that the length of $K_1$ is less than $0.5(b-b^*)$ and is thus less than $0.5(b-a)$ . Note that both $K_0$ and $K_1$ constain points of $E$ , making both $K_0 \cap E$ and $K_1 \cap E$ perfect sets and compact sets. $\blacksquare$

Construction
Suppose $W \subset \mathbb{R}$ is a nonempty perfect set that satisfies Case 2. Pick two two-sided limit $a_0$ and $b_0$ of $W$ . Obtain $B_0=K_0$ and $B_1=K_1$ as a result of applying Lemma 4. Let $A_1=B_0 \cup B_1$ .

Then we apply Lemma 4 on the closed interval $B_0$ and obtain closed intervals $B_{00}$ , $B_{01}$ . Likewise we apply Lemma 4 on the closed interval $B_1$ and obtain closed intervals $B_{10}$ , $B_{11}$ . Let $A_2=B_{00} \cup B_{01} \cup B_{10} \cup B_{11}$ .

Continue this induction process. Let $C=\bigcap \limits_{n=1}^{\infty} A_n$ . The set $C$ is a Cantor set and has all the properties discussed in the posts labled #6 and #7 lised at the end of this post.

We claim that $C \subset W$ . For any countably infinite sequence $g$ of zeros and ones, let $g_n$ be the first $n$ terms in $g$ . Let $y \in C$ . Then $\left\{y\right\}=\bigcap \limits_{n=1}^{\infty} B_{g_n}$ for some countably infinite sequence $g$ of zeros and ones (see post #6 listed below). Then every open interval $(a,b)$ containing $y$ would contain some closed interval $B_{g_n}$ . Thus $y$ is a limit point of $W$ . Hence $y \in W$ .

The Lindelof property of the real line

Posted on May 29, 2010 by Dan Ma

This is post #10 of the series on the Euclidean topology of the real line. See the links at the bottom for other posts in the series.

In the real line, the set $\mathbb{Z}$ of all integers (positive, negative and zero) is a closed set as well as a discrete set. It is closed because the complement is an open set. It is discrete since no point of $\mathbb{Z}$ is a limit point of $\mathbb{Z}$ . It turns out that in the real line, only countable sets can be both closed and discrete. Equivalently, the real line satisfies the following property:

$* \$ Every uncountable subset has a limit point.

A set $A \subset \mathbb{R}$ is discrete if no point of $A$ is a limit point of $A$ . The set $H=\left\{\frac{1}{n}: n=1,2,3,\cdots\right\}$ is a discrete set, as is the set $\mathbb{Z}$ . However, unlike $\mathbb{Z}$ , the set $H$ is not a closed set. It turns out that in the real line, only countable sets can be discrete. Equivalently, the real line satisfies the following property:

$** \$ Every uncountable subset contains one of its limit points.

It follows that for any uncountable subset $A$ of the real line, all but countably many points of $A$ are limit points of $A$ .

We show that both the statements $*$ and $**$ are intimately tied to the Lindelof property. Specifically, both $*$ and $**$ hold for the real line because the real line itself and every subset of the real line has the Lindelof property.

We also prove that for every uncountable subset $A$ of the real line, there is at least one $p \in A$ such that $p$ is a two-side limit point of $A$ . It follows that for every uncountable subset $A$ of the real line, all but countably many points of $A$ are two-sided limit points of $A$ .

Definitions
Let $X$ be a topological space. A collection $\mathcal{U}$ of subsets of $X$ is said to be a cover of $X$ if every point of $X$ belongs to some set in $\mathcal{U}$ . The collection $\mathcal{U}$ is said to be an open cover if it is a cover of $X$ and it consists entirely of open subsets of $X$ . If $\mathcal{U}$ is an open cover of $X$ and if $\mathcal{V} \subset \mathcal{U}$ also covers $X$ , then $\mathcal{V}$ is said to be a subcover of $\mathcal{U}$ .

The space $X$ is said to be a Lindelof space (or has the Lindelof property) if every open cover of $X$ has a countable subcover. The space $X$ is said to be hereditarily Lindelof if every subspace of $X$ is a Lindelof space.

Theorem 1
Let $X$ be a topological space.

If $X$ is Lindelof, then $X$ satisfies the property $*$ .
If $X$ is hereditarily Lindelof, then $X$ satisfies the property $**$ .

Proof. We prove the contrapositive, that is, if $X$ has an uncountable subset that has no limit point, then $X$ is not Lindelof. Let $A \subset X$ be uncountable such that $A$ has no limit point. Then $A$ is a closed set. For each $x \in A$ , there is an open set $O_x$ such that $x \in O_x$ and $O_x$ contains no point of $A$ other than $x$ . Then the following is an open cover of $X$ :

$\mathcal{U}=\displaystyle \left\{O_x: x \in A\right\} \cup \left\{X-A\right\}$

Note that only countably many $O_x$ cannot cover $A$ . Thus $\mathcal{U}$ is an open cover of $X$ that has no countable subcover, showing that $X$ is not Lindelof.

To show 2, we also prove the contrapositive. Let $A \subset X$ be some uncountable set such that no point of $A$ is a limit point of $A$ . Then for each $x \in A$ , $\left\{x\right\}$ is an open set relative to $A$ . Thus the subspace $A$ is not Lindelof, showing that $X$ is not hereditarily Lindelof. $\blacksquare$

Theorem 2
Every subset of the real line $\mathbb{R}$ has the Lindelof property, i.e. $\mathbb{R}$ is hereditarily Lindelof.

Remark. This follows from Lemma 4 in the post labeled #4 listed below. This theorem follows from the fact that the Euclidean topology of the real line is generated by a countable base (specifically, the open intervals with rational numbers as endpoints).

Corollary 3
The real line satisfies properties $*$ and $**$ . Thus we have:

Every uncountable subset of the real line has a limit point.
Every uncountable subset of the real line contains one of its limit points.

Remark
This follows from Theorem 1 and Theorem 2. It also follows that if $A$ is an uncountable subset of the real line, all but countably many points of $A$ are limit points of $A$ . $\blacksquare$

Let $A \subset \mathbb{R}$ and $p \in A$ . The point $p$ is said to be right-sided limit point of $A$ if for each open interval $(a,b)$ such that $p \in (a,b)$ , we have $(p,b) \cap A \ne \phi$ . The point $p$ is said to be left-sided limit point of $A$ if for each open interval $(a,b)$ such that $p \in (a,b)$ , we have $(a,p) \cap A \ne \phi$ . The point $p$ is said to be a two-sided limit point of $A$ if it is both a right-sided and left-sided limit point.

Based on the discussion in the previous post on completness (the post labeled #3 below), we can assume the least upper property whenever we work with the real line. This property states that for every subset $A$ of the real line, if $A$ is bounded above, then $A$ has a least upper bound (the upper bound that is the smallest among all the upper bounds). This assumption simplies the proof of the next theorem. The least upper bound property is equivalent to the greatest lower bound property, which states that for every subset $A$ of the real line, if $A$ is bounded below, then $A$ has a greatest lower bound (the lower bound that is the greatest among all the lower bounds).

Theorem 4
Every uncountable subset of the real line has at least one point that is a two-sided limit point.

Proof. Suppose that $A \subset \mathbb{R}$ is an uncountable set such that none of its points is a two-sided limit point. By corollary 3, all but countably many points of $A$ is a limit point of $A$ . So by removing these countably many points if necessary, assume that every point of $A$ is a limit point of $A$ .

For each $x \in A$ , $x$ is either a right-sided limit point of $A$ or a left-sided limit point of $A$ but not both. So either $(1)$ there are uncountably many points of $A$ that are left-sided limit points of $A$ or $(2)$ there are uncountably many points of $A$ that are right-sided limit points of $A$ . Assume $(1)$ and use the least upper bound property. The proof assuming $(2)$ is similar and uses the greatest lower bound property.

Let $B$ be the set of all points of $A$ that are left-sided limit points of $A$ . By assumption $(1)$ , $B$ is uncountable. For each $x \in B$ , choose a rational number $b_x$ such that $(x,b_x)$ contains no point of $A$ . Then there must be some rational number $r$ such that $r=b_x$ for uncountably many $x \in B$ . Thus the following set $C$ is uncountable:

$\displaystyle C=\left\{x \in B: b_x=r\right\}$

Note that the rational number $r$ is an upper bound of $C$ . By the least upper bound property, let $u$ be the least upper bound of $C$ . Choose some $y \in C$ such that $y<u$ . This is possible since $x \le u$ for all $x \in C$ and $C$ is uncountable. There must be some $z \in C$ such that $y<z<u$ . Otherwise, $y$ would be an upper bound. Since $z$ is a left-sided limit point of $A$ , $(y,z)$ contains infinitely many points of $A$ . But $(y, b_y)=(y,r)$ is supposed to contain no points of $A$ , a contradiction.

Under assumption $(2)$ , the proof is similar and uses the greatest lower bound property. Thus we establish that in each uncountable subset of the real line, one of its points must be a two-sided limit point. As a corollary to this fact, all but countably many points of an uncountable set of real numbers must be two-sided limit points of the set. $\blacksquare$

Perfect sets and Cantor sets, I

Posted on May 27, 2010 by Dan Ma

This is post #9 of the series on the Euclidean topology of the real line. See the links at the bottom for other posts in the series.

Recall that a subset $A$ of the real line is a perfect set if $A$ is closed in Euclidean topology of the real line and that every point of $A$ is a limit point of $A$ . Any closed and bounded interval $[a,b]$ is a perfect set. The Cantor sets (the middle third version and other variations) are perfect sets (see the links #7 and #8 below). It turns out that any nonempty perfect set contains a Cantor set. In this series of posts on Euclidean topology of the real line, by Cantor sets we mean any set that can be constructed by a binary process of splitting closed intervals into two halves at each stage (see links for #6 and #8 below). We demonstrate the algorithm of constructing a Cantor set from any perfect set. This post (part I) shows that any nonempty perfect set is uncountable. Knowing that a perfect is uncountable will simplify the construction process (next post).

Suppose $W \subset \mathbb{R}$ is a nonempty perfect subset. We show that $W$ is uncountable. Since $W$ has at least one point and every point is a limit point, $W$ is infinite. The key to showing $W$ is uncountable is that every nested decreasing sequence of compact subsets of the real line (actually in any topological space) has nonempty intersection. If $W$ happens to be countable, we can define a nested sequence of compact subsets of $W$ with empty intersection. Thus $W$ cannot be countable.

The following lemma is a corollary to Theorem 3 in the post # 4 listed below. The lemma applies to any abstract spaces where compactness can be defined. We state the lemma in terms of the real line since this is our focus.

Lemma
Suppose $C_1,C_2,C_3, \cdots$ are compact subsets of the real line such that

$\displaystyle C_1 \supset C_2 \supset C_3 \supset \cdots$ .

Then $\bigcap \limits_{n=1}^{\infty} C_n \ne \phi$ .

To make the argument that $W$ is uncountable more precise, suppose that $W$ is countable. Then we can enumerate $W$ in a sequence indexed by the positive integers. We have:

$\displaystyle W=\left\{w_1,w_2,w_3,\cdots\right\}$

Pick a bounded open interval $O_1$ such that $w_1 \in O_1$ . Next, pick an open interval $O_2$ such that $\overline{O_2} \subset O_1$ and $w_2 \notin \overline{O_2}$ and $O_2 \cap W \ne \phi$ .

In the $n^{th}$ stage where $n \ge 2$ , pick an open interval $O_n$ such that $\overline{O_n} \subset O_{n-1}$ and $w_n \notin \overline{O_n}$ and $O_n \cap W \ne \phi$ . Since $W$ is a perfect set, the induction step can continue at every stage.

Now, let $C_n=\overline{O_n} \cap W$ . Note that $C_n$ is a compact set since $\overline{O_n}$ is compact. By the lemma, the intersection of the $C_n$ must be nonempty. By the induction steps, no point of $W$ belongs to all the sets $\overline{O_n}$ , implying the intersection of $C_n$ is empty, a contradiction. Thus $W$ must be uncountable.

Remark
As a corollary, the real line and the unit intervals are uncountable. A more interesting corollary is that any nonempty perfect set has a two-sided limit point. In fact all but countably many points of a nonempty perfect set are two sided limit points. See the post The Lindelof property of the real line for a proof that any uncountable subset of the real line has a two sided limit point. This fact will simplify the construction of a Cantor set from a perfect set.

Reference

Rudin, W., Principles of Mathematical Analysis, Third Edition, 1976, McGraw-Hill, Inc, New York.

The Cantor set, III

Posted on May 23, 2010 by Dan Ma

This is post # 8 of the series on the Euclidean topology of the real line. See the links at the bottom for other posts in the series.

The Cantor set, I
The Cantor set, II

In two previous posts (see links above), we discuss the “middle third” Cantor set constructed on the unit interval. In this post, we discuss two variations on this construction. In the first variation, the lengths of the removed intervals sum to 1 (hence these Cantor sets have zero Lebesgue measure). The middle third construction is a specific example if this algorithm. In the second variation, the sum of the lengths of removed intervals is less than one. Thus these Cantor sets have positive Lebesgue measure. However, the resulting Cantor sets from either approach have the same topological properties.

The Middle k Cantor Set
Let $0<k<1$ . In this construction, we remove the middle $k^{th}$ open interval of $[0,1]$ . This removed open interval has length $k$ and the remaining set has length $1-k$ .

In the second stage, for each of the two remaining two closed intervals, we remove the middle $k^{th}$ open interval. The two removed open intervals have a combined length of $(1-k)k$ . Thus, the length of the remaining set is $(1-k)-(1-k)k=(1-k)^2$ .

In the third stage, the four removed intervals have a combined length of $(1-k)^2k$ . Then the remaining set has length:

$(1-k)^2-(1-k)^2k=(1-k)^3$ .

When the inductive process is completed, the set of the remaining points is a Cantor set. The total length of removed open intervals is:

$\displaystyle k+(1-k)k+(1-k)^2k+ \cdots=1$

When $k=\frac{1}{3}$ , we have the middle third Cantor set that is constructed in the previous post The Cantor set, I. Whether $k=\frac{1}{3}$ or another fraction, the resulting Cantor sets have the same properties. This middle $k$ process always produces a compact subset of the real line that has cardinality continuum, which is also a perfect set and a nowhere dense set in $[0,1]$ as well as a totally disconnected set. In other words, all the properties discussed in the two previous posts (see the links indicated above) hold for the Cantor sets produced by this middle $k$ algorithm.

The Cantor Sets of Positive Measure
Pick a sequence $\left\{a_n\right\}$ such that $0<\sum \limits_{n=1}^{\infty} a_n<1$ . For the illustration here, we use $a_n=\frac{1}{2^{n+1}}$ where $n=1,2,3,\cdots$ . Note that $\sum \limits_{n=1}^{\infty} a_n=\frac{1}{2}$ .

In this construction, we still remove the middle open interval in any remaining closed interval. The key is that in each stage we remove open intervals with a total length of $a_n=\frac{1}{2^{n+1}}$ . In the end, the removed intervals have a total length of $\frac{1}{2}$ , making the left over piece of length $\frac{1}{2}$ .

In stage $n=1$ , we remove the middle $\frac{1}{2^2}$ open interval of $[0,1]$ . In stage $n=2$ , in each of the remaining two closed intervals, we remove the middle part such that the two removed open intervals have equal length and the combined length of $\frac{1}{2^3}$ .

In stage $n=3$ , the four removed open intervals are of equal length and with a combined total length of $\frac{1}{2^4}$ .

Continue with the inductive process, making sure that any removed open interval is the middle part of the remaining closed interval. When it is done, the removed open intervals have a total length of $\frac{1}{2}$ . The set of the remaining points is a Cantor set of length $\frac{1}{2}$ . Other than having positive Lebesgue measure, the Cantor sets produced by this algorithm have the same topological properties as the middle third Cantor set, namely, being totally disconnected and a perfect set.

Links to previous posts on the topology of the real line:
The Euclidean topology of the real line (1)
The Euclidean topology of the real line (2)
The Euclidean topology of the real line (3) – Completeness
The Euclidean topology of the real line (4) – Compactness
The Cantor bus tour
The Cantor set, I
The Cantor set, II

The Cantor set, II

Posted on May 23, 2010 by Dan Ma

This is post # 7 of the series on the Euclidean topology of the real line. See the links at the bottom for other posts in the series.

In the previous post The Cantor set, I, we constructed the “middle third” Cantor set and we showed that it has cardinality continuum. In this post we discuss some basic topological properties of the Cantor set.

The Cantor set we defined in the previous post is the “middle third” Cantor set, the traditional version found in many texts. In this “middle third” recipe, the open interval in the middle third of $[0,1]$ is taken out. Two closed intervals remain. In each of the succeeding stages, the open interval in the middle third of any remaining closed interval is removed. After the inductive process is completed, the remaining points form the Cantor set. Note that the open intervals removed in this process have a total length of $1$ since $\frac{1}{3}+\frac{2}{3^2}+\frac{2^2}{3^3}+\cdots =1$ . Yet the points remained have the same cardinality as the unit interval $[0,1]$ .

There are other striking properties about the Cantor set. For example, the Cantor set contains no open intervals $(a,b)$ . This makes the Cantor set a very “thin” set (a nowhere dense set). On the other hand, the Cantor set has no isolated points since every point of the Cantor set is a limit point of itself.

Cantor Set Preliminary
Let $C$ be the Cantor set as defined in the previous post. Recall that $C=\bigcap \limits_{n=0}^{\infty}A_n$ where

$A_0=[0,1]$
$A_1=B_0 \cup B_1$
$A_2=B_{00} \cup B_{01} \cup B_{10} \cup B_{11}$
$A_3=B_{000} \cup B_{001} \cup B_{010} \cup B_{011} \cup B_{100} \cup B_{101} \cup B_{110} \cup B_{111}$
and so on.

Each $B_g$ , where $g$ is a string of zeros and ones of finite length, is a closed interval and is obtained by removing the middle third of the previous closed interval. For example, $B_{010}$ and $B_{011}$ are obtained by removing the middle third of the closed interval $B_{01}$ . Refer to the previous post The Cantor set, I for more information about the construction.

Each point $y \in C$ is the single point in the intersection of a nested decreasing sequence of $B_g$ , i,e, $\left\{y\right\}=\bigcap \limits_{n=1}^{\infty}B_{g_n}$ where $g_i$ and $g_j$ agree on the first $i$ many coordinates if $i<j$ . The $g_n$ can be obtained by tracing the construction steps. For example, $y \in B_0$ or $y \in B_1$ . Say $y \in B_0$ . Then $y \in B_{00}$ or $y \in B_{01}$ . Say, $y \in B_{01}$ . Now $y \in B_{010}$ or $y \in B_{011}$ . Say, $y \in B_{010}$ . Thus, we have:

$\displaystyle y \in B_0 \cap B_{01} \cap B_{010} \cap \cdots$

As a result, each $y \in C$ is associated with $h(y)$ , which is a sequence of countably infinite many zeros and ones such that the first $n$ coordinates of $h(y)$ agree with $g_n$ .

The mapping $h$ in the above paragraph is a bijection between the Cantor set $C$ and $S_{\omega}$ , the set of all countably infinite sequences of zeros and ones. If $g \in S_{\omega}$ , we let $g_n$ be the string of zeros and ones that agrees with the first $n$ coordinates of $g$ . Thus in this notation, for $y \in C$ , we have $\left\{y\right\}=\bigcap \limits_{n=1}^{\infty}B_{h(y)_n}$ .

To facilitate the subsequent discussion, we have the following lemma.

Lemma

For each $y \in C$ , the intervals $B_{h(y)_n}$ form a local base at $y$ , i.e. for each open interval $(a,b)$ with $y \in (a,b)$ , there is some integer $n$ such that $B_{h(y)_n} \subset (a,b)$ .
Let $D$ be the set of endpoints of the closed intervals $B_{g_n}$ obtained in the construction process. We have $D \subset C$ .
The set $D$ is dense in $C$ .

Proof
Condition 1 follows from the fact that the lengths of the closed intervals $B_{h(y)_n}$ go to zero.

We now prove condition 2. Let $B_{g_n}$ be a closed interval obtained in the construction process and let $s$ be the left endpoint and $t$ be the right endpoint. Both $s$ and $t$ belong to $C$ since:

$\displaystyle \left\{s\right\}=B_{g_n} \cap B_{g_n0} \cap B_{g_n00} \cap B_{g_n000} \cap \cdots$

$\displaystyle \left\{t\right\}=B_{g_n} \cap B_{g_n1} \cap B_{g_n11} \cap B_{g_n111} \cap \cdots$

The fact that $D$ is dense in $C$ follows from condition 1. Every open interval containing a point of $C$ has to contain one closed interval $B_{g_n}$ and thus the endpoints of $B_{g_n}$ . $\blacksquare$

Main Discussion
We discuss the following proeprties:

The Cantor set $C$ is a compact subset of $[0,1]$ .
The Cantor set $C$ is a perfect set.
$[0,1]-C$ , the complement of $C$ , is dense in $[0,1]$ .
The Cantor set $C$ contains no open interval.
The Cantor set $C$ is nowhere dense in $[0,1]$ .
The Cantor set $C$ is totally disconnected.

Discussion of 1
In the real line or in any other topological space, the intersection of closded sets is always a closed set. The Cantor set $C$ is the intersection of $A_n$ where each $A_n$ is a closed set (it being a finite union of closed intervals). Thus the Cantor set $C$ is a closed subset of $[0,1]$ . Being a closed and bounded subset of the real line, $C$ is compact. $\blacksquare$

Discussion of 2
Recall that a subset $W$ of the real line is a perfect set if it is closed and every point of $W$ is a limit point of $W$ . Let $y \in C$ . Let $(a,b)$ be an open interval of the real line such that $y \in (a,b)$ . We want to show that there are infinitely many points of $C$ inside $(a,b)$ . This following from condition 1 of the lemma. The interval $(a,b)$ contains $B_{g_n}$ which would contain infinitely many points in the Cantor set. Note that the construction process of the Cantor set would continue within the interval $B_{g_n}$ . $\blacksquare$

Discussion of 3
This also follows from condition 1 of the lemma. We need to demonstrate that every point in $[0,1]$ is either a point of $[0,1]-C$ or a limit point of $[0,1]-C$ . Let $y \in [0,1]$ . If $y \in [0,1]-C$ , then we are done. So suppose $y \in C$ . By condition 1 of the lemma, every open interval containing $y$ contains some closed interval $B_{g_n}$ . Since the middle third of $B_{g_n}$ is removed in the construction process, we see that $(a,b) \cap ([0,1]-C) \ne \phi$ . $\blacksquare$

Discussion of 4
This is a corollary of 3. Suppose we have $(a,b) \subset C$ . By 3, $(a,b)$ contains points of the removed open intervals, which is a contraction. $\blacksquare$

Discussion of 5
Let $A \subset \mathbb{R}$ . The set $A$ is nowhere dense in $\mathbb{R}$ if $A$ is dense in no open interval of $\mathbb{R}$ , or equivalently, for each open interval $(a,b)$ , there is some subinterval $(c,d) \subset (a,b)$ such that $(c,d) \cap A=\phi$ . To say that $A$ is nowhere dense in $[0,1]$ , we only need to concern with the open intervals that have points in $[0,1]$ .

This is a corollary of condition 4. For each open interval $(a,b)$ in $[0,1]$ , it cannot be a subset of $C$ . So there must some point $x \in (a,b)$ such that $x \notin C$ . But the Cantor set $C$ is a closed subset of $[0,1]$ . Then there must be some $(c,d) \subset (a,b)$ such that $x \in (c,d)$ and $(c,d) \cap C=\phi$ . $\blacksquare$

Discussion of 6
The Cantor set is totally disconnected. A subset $A$ of the real line $\mathbb{R}$ is a disconnected set if there are disjoint open sets $U$ and $V$ , both containing points of $A$ , such that $A=(U \cap A) \cup (V \cap A)$ . A set $A$ is connected if it is not disconnected.

The Cantor set $C$ is disconnected. Note that $C=([0,0.5) \cap C) \cup (0.5,1] \cap C)$ .

A set $A \subset \mathbb{R}$ is totally disconnected if the only connected subsets of $A$ are the singleton sets. We show that any subset of the Cantor set with at least two points is not connected. Let $A \subset C$ with $x,y \in A$ where $x<y$ . Since $C$ is nowhere dense, there exists $(c,d) \subset (x,y)$ such that $(c,d)$ has no points of $C$ . Let $t=0.5(c+d)$ . Then we have:

$\displaystyle A=([0,t) \cap A) \cup ((t,1] \cap A)$

The Cantor set, I

Posted on May 21, 2010 by Dan Ma

This is post # 6 of the series on the Euclidean topology of the real line. See the links at the bottom for other posts in the series.

The goal is this post is to construct the Cantor set and demonstrate that the Cantor set has the same cardinality as the set of all real numbers. In the next post we discuss the topological properties of the Cantor set.

The Construction
For each positive integer $n=1,2,3,\cdots$ , let $S_n$ be the set of all sequences zeros and ones of length $n$ . For example, $S_1=\{ 0,1 \}$ , $S_2=\{ 00, 01, 10, 11 \}$ , $S_3=\{000, 001, 010, 011, 100, 101, 110, 111 \}$ and so on. Each $S_n$ has $2^n$ sequences. For each $f \in S_n$ , we can tag on a $0$ or $1$ and obtain an element of $S_{n+1}$ . For example, for $011000 \in S_6$ , both $0110000, 0110001 \in S_7$ .

Let $A_0=[0,1]$ be the unit interval. Remove the middle third open interval $(\frac{1}{3},\frac{2}{3})$ from $A_0$ . Label the remaining two intervals by $B_0=[0,\frac{1}{3}]$ and $B_1=[\frac{2}{3},1]$ . Let $A_1=B_0 \cup B_1$ be the union of these two closed intervals.

Consider the stage at $n=2$ . For $0 \in S_1$ , remove the middle third of $B_0$ and obtain $B_{00}=[0,\frac{1}{9}]$ and $B_{01}=[\frac{2}{9},\frac{1}{3}]$ . For $1 \in S_1$ , remove the meddle third of $B_1$ and obtain $B_{10}=[\frac{2}{3},\frac{7}{9}]$ and $B_{11}=[\frac{8}{9},1]$ . Let $A_2=B_{00} \cup B_{01} \cup B_{10} \cup B_{11}$ . Note that the length of each closed interval $B_{ij}$ is $\displaystyle \frac{1}{3^2}=\frac{1}{9}$ .

Suppose we have the following at the $n^{th}$ stage, where $n \ge 1$ .

The closed interval $B_f$ has been defined for each $f \in S_n$ .
The length of each $B_f$ is $\frac{1}{3^n}$ .
$A_n=\bigcup \limits_{h \in S_n} B_h$ .

We now define the closed intervals in stage $n+1$ . For each closed interval $B_f$ , we remove the middle third open intervals and obtain two closed intervals $B_{f0}$ and $B_{f1}$ where each has length $\frac{1}{3^{n+1}}$ . Let $A_{n+1}$ be defined as:

$\displaystyle A_{n+1}=\bigcup \limits_{f \in S_n} (B_{f0} \cup B_{f1})=\bigcup \limits_{g \in S_{n+1}} B_g$

We now define the Cantor set $C=\bigcap \limits_{i=0}^{\infty} A_j$ . This is a nonempty set subset of the unit interval. The point $0 \in C$ since $0 \in B_0 \cap B_{00} \cap B_{000} \cap \cdots$ . Being the union of finitely many closed intervals, each $A_n$ is a closed subset of $[0,1]$ . Thus each $A_n$ is a compact subset of $[0,1]$ . Any nested decreasing sequence of compact subsets of the real line is nonempty. See the post The Euclidean topology of the real line (4) – Compactness. In the remainder of this post, we show that the Cantor set $C$ has the cardinality continuum.

General Discussion
Let $A$ and $B$ be sets. A function $f:A \rightarrow B$ is a one-to-one function if for $x,y \in A$ with $x \ne y$ , $f(x) \ne f(y)$ , that is, distinct elements of the domain are mapped to distinct elements of the range. A function $f:A \rightarrow B$ is said to be a surjection if $f(A)=B$ , i.e. every point in the set $B$ is mapped by some point of $A$ . A function $f:A \rightarrow B$ is said to be a bijection if it is both a one-to-one function and a surjection.

The sets $A$ and $B$ have the same cardinality if there is a bijection $f:A \rightarrow B$ . When $A$ and $B$ have the same cardinality, we use the notation $\lvert A \lvert=\lvert B \lvert$ . For example, the set of all rational numbers has the same cardinality as the integers since we can define a bijection between the two sets. More informally, we can put the rational numbers in an exhaustive list indexed by the integers. When a set has the same cadinality as the set of real numbers, we say that the set has cardinality continuum.

When there is a one-to-one function $f:A \rightarrow B$ , we denote this condition by $\lvert A \lvert \le \lvert B \lvert$ . Obviously when $A \subset B$ , we have $\lvert A \lvert \le \lvert B \lvert$ . The Cantor–Bernstein–Schroeder theorem states that when there are one-to-one functions $f:A \rightarrow B$ and $g:B \rightarrow A$ , we have $\lvert A \lvert=\lvert B \lvert$ . In other words, if $\lvert A \lvert \le \lvert B \lvert$ and $\lvert B \lvert \le \lvert A \lvert$ , we have $\lvert A \lvert=\lvert B \lvert$ . We utilize this fact when we show that the Cantor set and the set of all real numbers have the same cardinality.

The Cardinality of the Cantor Set
Let $\omega=\left\{0,1,2,3,\cdots\right\}$ be the set of all nonnegative integers. Let $S_{\omega}$ be the set of all infinite sequences of 0’s and 1’s. Let $\mathcal{P}(\omega)$ be the set of subsets of $\omega$ . The cardinality of the Cantor set follows from the following relationship:

$\displaystyle \lvert \mathbb{R} \lvert \le \lvert \mathcal{P}(\omega) \lvert = \lvert S_{\omega} \lvert = \lvert C \lvert \le \lvert \mathbb{R} \lvert$

The inequality $\lvert C \lvert \le \lvert \mathbb{R} \lvert$ is clear since the Cantor set is a subset of the real line. The following claims establish the relationship.

Claim 1 $\lvert S_{\omega} \lvert = \lvert C \lvert$
This follows from the contruction of the Cantor set. Let $y \in C$ . At each stage of the construction, there are $2^n$ many closed intervals and the point $y$ belongs to exactly one of these intervals, say $B_{f_n}$ . At the next stage, the point $y$ belongs to one of the closed intervals as a result of splitting $B_{f_n}$ by removing the middle third. Since the lengths of $B_{f_n}$ approaches to zero, we have $\left\{y\right\}=\bigcap \limits_{n=1}^{\infty} B_{f_n}$ .

Note that for each $f_n$ and $f_{n+1}$ agree on the first $n$ coordinates. Thus the finite sequences form an countably infinite sequence $f \in S_{\omega}$ such that $f$ and $f_n$ agree on the first $n$ coordinates of $f$ . Let $H(y)=f$ .

We just describe a mapping $H: C \rightarrow S_{\omega}$ . This mapping is one-to-one. For $x,y \in C$ where $x \ne y$ , there must be some stage $n$ where $x$ and $y$ belong to disjoint closed intervals. Otherwise, $x=y$ . Let $n$ be the least integer such that $x$ and $y$ belong to disjoint closed intervals. Then $x$ and $y$ belong to the same interval $B_{g}$ in stage $n-1$ . However, $x$ and $y$ belong to disjoint closed intervals at stage $n$ , say $x \in B_{g0}$ and $y \in B_{g1}$ . As a result, $H(x)$ and $H(y)$ disagree at the $n^{th}$ coordinate, implying $H(x) \ne H(y)$ .

No point in $S_{\omega}$ is missed by the mapping $H$ . For each $f \in S_{\omega}$ , let $f_n$ be the sequence of its first $n$ coordinates. Then the sequence of closed intervals $B_{f_n}$ collapses to a point $x$ . It is clear that $H(x)=f$ . $\blacksquare$

Claim 2 $\lvert \mathcal{P}(\omega) \lvert = \lvert S_{\omega} \lvert$
The surjection is defined by an indicator function. For each $A \in \mathcal{P}(\omega)$ , $F(A) \in S_{\omega}$ such that the $n^{th}$ coordinate $F(A)_n$ is:

$\displaystyle F(A)_n=\left\{\begin{matrix}0&\thinspace n \notin A \\{1}&\thinspace n \in A \end{matrix}\right.$

It can be verified that $F: \mathcal{P}(\omega) \rightarrow S_{\omega}$ is a one-to-one map and that $F(\mathcal{P}(\omega))=S_{\omega}$ . $\blacksquare$

Claim 3 $\lvert \mathbb{R} \lvert \le \lvert \mathcal{P}(\omega) \lvert$
Let $\mathbb{Q}$ be the set of all rational numbers. Since $\lvert \mathbb{Q} \lvert=\lvert \omega \lvert$ , we have $\lvert \mathcal{P}(\mathbb{Q}) \lvert=\lvert \mathcal{P}(\omega) \lvert$ . We now define a one-to-one map $G: \mathbb{R} \rightarrow \mathcal{P}(\mathbb{Q})$ .

For each $x \in \mathbb{R}$ , let $G(x)=\left\{r \in \mathbb{Q}: r<x\right\}$ . It is clear that $G(x) \ne G(y)$ for $x \ne y$ .

Links to previous posts on the topology of the real line:
The Euclidean topology of the real line (1)
The Euclidean topology of the real line (2)
The Euclidean topology of the real line (3) – Completeness
The Euclidean topology of the real line (4) – Compactness
The Cantor bus tour

Revised October 29, 2019

The Cantor bus tour

Posted on May 18, 2010 by Dan Ma

This is post # 5 of the series on the Euclidean topology of the real line. See the links at the bottom for other posts in the series.

Steven Strogatz is a professor of applied math at Cornell University. He also writes a column in New York Times on math. The latest column and the last in 2010 (May 9, 2010) is titled The Hilbert Hotel. We admire anyone who can write math for popular audience and can make it seem so natural and interesting. In this latest column, professor Strogatz ventures into the world of infinity that is the legacy of Georg Cantor (introduced in the late 1800s). His illustration of infinity is through the telling of the parable of a grand hotel that is now called Hilbert Hotel (in honor of David Hilbert).

The Hilbert Hotel has infinitely many rooms (labeled by the positive integers). Even when it is full, the hotel manager can always accommodate another guest. In fact, when the hotel is full, it can even accommodate infinitely many guests (e.g. guests are labeld by the positive integers). Even stranger still, when the infinitely many guests are labeled by fractions $\frac{p}{q}$ where $p$ and $q$ are positive integers, the Hilbert Hotel, if the manager knows some set theorey, can still find rooms for these guests (in the parable, the fractions $\frac{p}{q}$ are in the form of infinitely many buses and each bus has infinitely many guests). However, the Hilbert Hotel cannot accommodate the guests if the infinitely many guests are labeled by the real numbers within the unit interval $[0,1]$ .

So the Hilbert Hotel parable illustrates better than numbers and points that the rational numbers can be put in a one-to-one correspondance with the positive integers while the real numbers between zero and one cannot be put in a one-to-one correspondance with the positive integers. In other words, the cardinality of the set of all real numbers is greater than the cardinality of the set of integers.

The column by Professor Strogatz illustrates that we can make an exhaustive list of the positive rational numbers (fractions of two integers) and the listing is indexed by the positive integers. On the other hand, the real numbers between zero and one cannot be listed out exhaustively in an integer indexed listing. When the elements of a set can be listed by a listing indexed by the integers, we say the set is a countable set. Otherwise, the set is said to be an uncountable set. Right off the bat, the handy examples of countable sets are the set of all positive integers, the set of all integers and the set of all positive rational numbers. With just a little more care, the set of all rational numbers is a countable set too. The set of all real numbers is an uncountable set.

In preparation for a subsequent post, we would like to demonstrate that the set of sequences of 0’s and 1’s is an uncountable set. Our device is not a hotel but rather the tossing of infinitely many coins (the number of coins is infinite as in the positive integers and not the real numbers). Suppose we toss infinitely many coins. Record a tail as 0 and record a tail as 1. The following is one example of an outcome where the first toss results in a tail, the second toss results in a head and so on:

$\displaystyle (0,1,0,1,1,0,0,0,1, \cdots)$

How many such outcomes are possible? Can the set of all such sequences be listed exhaustively by the integers? The answer is no. Suppose we can do so and the following is the exhaustive listing:

$\displaystyle x_1=(x_{1,1}, \ x_{1,2}, \ x_{1,3}, \ x_{1,4}, \ x_{1,5}, \cdots)$
$\displaystyle x_2=(x_{2,1}, \ x_{2,2}, \ x_{2,3}, \ x_{2,4}, \ x_{2,5}, \cdots)$
$\displaystyle x_3=(x_{3,1}, \ x_{3,2}, \ x_{3,3}, \ x_{3,4}, \ x_{3,5}, \cdots)$
$\displaystyle x_4=(x_{4,1}, \ x_{4,2}, \ x_{4,3}, \ x_{4,4}, \ x_{4,5}, \cdots)$
$\displaystyle x_5=(x_{5,1}, \ x_{5,2}, \ x_{5,3}, \ x_{5,4}, \ x_{5,5}, \cdots)$
$\displaystyle \cdot$
$\displaystyle \cdot$
$\displaystyle \cdot$

Each $x_{i,j}$ is either 0 or 1 and is the result of the $j^{th}$ toss in the $i^{th}$ sequence in the list. We consider the terms in the diagonal $x_{1,1}, x_{2,2},x_{3,3}$ and so on. Then for each $i=1,2,3, \cdots$ , define $y_i$ as the following:

$\displaystyle y_i=\left\{\begin{matrix}0&\thinspace x_{i,i}=1 \\{1}&\thinspace x_{i,i}=0 \end{matrix}\right.$

Then $y=(y_1,y_2,y_3, \cdots)$ is an outcome of tossing infinitely many coins that is not on the listing. Thus, in attempting to make an exhaustive listing, we can always come up with another outcome that is not on the listing. This means the set of all possible sequences of 0’s and 1’s is an uncountable set. In the next post, we will show that it is the same size as the real numbers. These sequences of 0’s and 1’s are important in the construction of the Cantor set.

The Euclidean topology of the real line (4) – Compactness

Posted on May 16, 2010 by Dan Ma

In this post we discuss several notions of compactness, which are presented in the context of the real line. This is part of a series of posts on the topology of the real line. Our goal is to use this series of posts on the real line to motivate the topological notions being discussed. For basic definitions of open intervals, open sets and closed sets of the real line, refer to these previous posts:

The Euclidean topology of the real line (3) – Completeness
The Euclidean topology of the real line (2)
The Euclidean topology of the real line (1)

This is a post on introductory topology. Concepts discussed here are basic notions found in beginning topology courses and elementary analysis courses. For the readers who are taking math courses that transition their math career from calculation to proving of theorems, we encourage such readers to think about the concepts and theorems discussed here before reading the proofs.

Let $\mathbb{R}$ be the set of all real numbers. Let $\mathcal{U}$ be a collection of subsets of $\mathbb{R}$ . The set $\bigcup \mathcal{U}$ denotes the union of all sets in $\mathcal{U}$ and is the set of all real numbers which belong to at least one set $U \in \mathcal{U}$ .

$\displaystyle \begin{aligned} \bigcup \mathcal{U}&=\bigcup \left\{U: U \in \mathcal{U}\right\}\\&=\left\{x: x \in U \text{ where }U \in \mathcal{U}\right\}\end{aligned}$

Let $W \subset \mathbb{R}$ . By an open cover of $W$ , we mean a collection $\mathcal{U}$ of open sets of $\mathbb{R}$ such that $W \subset \bigcup \mathcal{U}$ , that is, every point in $W$ belongs to some open set in $\mathcal{U}$ . The subset $W$ of $\mathbb{R}$ is said to be compact if for each open cover $\mathcal{U}$ of $W$ , there is a finite subcollection $\mathcal{V}$ of $\mathcal{U}$ such that $W \subset \bigcup \mathcal{V}$ .

The real line $\mathbb{R}$ is not compact since $\left\{(-n,n): n=1,2,3, \cdots\right\}$ is an open cover of $\mathbb{R}$ such that no finite subcollection of which is a cover of the real line.

Any convergent sequence along with its limit is a compact set. For example, the set $A=\left\{0\right\} \cup \left\{1,\frac{1}{2},\frac{1}{3},\cdots\right\}$ is compact since any open interval containing $0$ contains all but finitely many points of the convergent sequence $\left\{1,\frac{1}{2},\frac{1}{3},\cdots\right\}$ .

Any subset of the real line that is not closed can never be compact since every compact subset of the real line is closed. Thus we have the following theorem.

Theorem 1
Let $W \subset \mathbb{R}$ . If $W$ is compact, then $W$ is closed in $\mathbb{R}$ .

Proof
Suppose $W$ is not closed. Then there is a limit point $p$ of $W$ such that $p \notin W$ . Let $\mathbb{N}$ be the set of all positive integers. Then the following is an open cover of $W$ such that it has no finite subcollection covering $W$ :

$\displaystyle \left\{(-\infty,p-\frac{1}{n}):n \in \mathbb{N}\right\} \cup \left\{(p+\frac{1}{n},+\infty):n \in \mathbb{N}\right\}$

Therefore, if $W$ is compact, then $W$ must be closed. $\blacksquare$

Recall from the previous post (The Euclidean topology of the real line (2)) that open sets and closed sets are relative to the space in which they are embedded. For example, take $Y=(0,1) \cup \left\{2\right\}$ . The singleton set $\left\{2\right\}$ is surely not an open subset of the whole real line. However, it is open relative to the space $Y$ . The property of being closed sets is also relative. The interval $(0,1)$ is a closed set relative to the space $Y=(0,1) \cup \left\{2\right\}$ . However, $(0,1)$ is not a closed set in the whole real line since both endpoints are limit points that are not in the $(0,1)$ .

The notion of compactness is not a relative concept. Let $W \subset \mathbb{R}$ . Let’s call the definition of $W$ being a compact set as defined above the property of being compact relative to $\mathbb{R}$ . We say that $W$ is compact relative to $W$ if in the same definition of compactness above, the open cover consists of open sets relative to $W$ . It turns out that these two notions are equivalent. We have the following theorem.

Theorem 2
Let $W \subset \mathbb{R}$ . Then $W$ is compact relative to $W$ if and only if it is compact relative to $\mathbb{R}$ .

Proof
$\Rightarrow$ Let $W$ be compact relative to $W$ . We show that $W$ is compact relative to $\mathbb{R}$ . To this end, let $\mathcal{U}$ be an open cover of $W$ . Here $\mathcal{U}$ consists of open sets of $\mathbb{R}$ . Then the following is an open cover of $W$ consisting of open sets relative to $W$ .

$\displaystyle \mathcal{U^*}=\left\{U \cap W: U \in \mathcal{U}\right\}$

Since $W$ is compact relative to $W$ , $\mathcal{U^*}$ has a finite subcollection that is also an open cover. The following lists out this finite subcollection:

$\displaystyle U_1 \cap W, \ U_2 \cap W, \ \cdots, \ U_n \cap W$

Then $\left\{U_1,U_2, \cdots, U_n\right\} \subset \mathcal{U}$ and covers $W$ .

$\Leftarrow$ Let $W$ be compact relative to $\mathbb{R}$ . We show that $W$ is compact relative to itself. To this end, let $\mathcal{V}$ be an open cover of $W$ consisting of open sets relative to $W$ . Note that each set in $\mathcal{V}$ is of the form $V \cap W$ where $V$ is an open subset of $\mathbb{R}$ . So consider the following:

$\displaystyle \mathcal{V^*}=\left\{V: V \cap W \in \mathcal{V} \text{ and } V \text{ is open subset of } \mathbb{R}\right\}$

Note that $\mathcal{V^*}$ is an open cover of $W$ . Since $W$ is compact relative to $\mathbb{R}$ , we have a finite subcollection $\mathcal{F}=\left\{V_1, \cdots, V_n\right\} \subset \mathcal{V^*}$ such that $\mathcal{F}$ is a cover of $W$ . Consider the following:

$\mathcal{G}=\left\{V_1 \cap W, V_2 \cap W, \cdots, V_n \cap W\right\}$

Note that $\mathcal{G}$ is a cover of $W$ and is a finite subcollection of $\mathcal{V}$ . $\blacksquare$

The above theorem shows that compactness does not depend on the space in which the compact set is embedded. A subset of the real line is compact in its own right as well as compact relative to the real line. This same thinking applies in topological spaces in general.

Theorem 3
Let $W \subset \mathbb{R}$ . Suppose that $W$ is a compact set. Then if $\mathcal{C}$ is a collection of compact subsets of $W$ such that the intersection of every finite subcollection of $\mathcal{C}$ is nonempty, then $\bigcap \mathcal{C} \ne \phi$ .

Proof
Suppose $\mathcal{C}$ is a collection of compact subsets of $W$ with the property indicated in the theorem (called the finite intersection property). We want to show that $\bigcap \mathcal{C} \ne \phi$ . Suppose $\bigcap \mathcal{C} = \phi$ . Then the following is an open cover of the compact set $W$ .

$\displaystyle \mathcal{U}=\left\{W-C: C \in \mathcal{C}\right\}$

Since $W$ is compact, there exists $\left\{C_1,C_2, \cdots, C_n\right\} \subset \mathcal{C}$ such that $\left\{W-C_1, \cdots, W-C_n\right\}$ covers $W$ . This means $\bigcap \limits_{i=1}^n C_i=\phi$ , contradicting that the collection $\mathcal{C}$ has the finite intersection property. $\blacksquare$

There are other notions of compactness that are equivalent in Euclidean spaces (the real line in particular) and some in metric spaces in general. Let $W \subset \mathbb{R}$ . The set $W$ is said to be countably compact if every countable open cover $\left\{U_1,U_2,U_3,\cdots\right\}$ of $W$ has a finite subcollection that is also a cover of $W$ , i.e. there exists some positive integer $n$ such that $W \subset U_1 \cup \cdots \cup U_n$ . The set $W$ is said to have the Bolzano-Weierstrass property if $W$ is closed relative to $\mathbb{R}$ and every infinite subset of $W$ has a limit point. The set $W$ is said to be sequentially compact if $W$ is closed relative to $\mathbb{R}$ and every sequence of points of $W$ has a subsequence that converges.

Lemma 4
Let $\mathcal{U}$ be a collection of open subsets of $\mathbb{R}$ . Then there is a countable subcollection $\mathcal{V} \subset \mathcal{U}$ such that $\bigcup \mathcal{V}=\bigcup \mathcal{U}$ .

Proof. Note that there are only countably many open intervals with rational endpoints. Thus we can enumerate these open intervals in a sequence:

$\displaystyle \left\{B_1,B_2,B_3, \cdots\right\}$

Let $W=\bigcup \mathcal{U}$ . For each $x \in W$ , there is an open set $U_x \in \mathcal{U}$ such that $x \in U_x$ . Furthermore, there is an open interval $B_j=(a,b)$ such that the endpoints are rational numbers and $x \in B_j \subset U_x$ . Each $B_j$ is associated with at least one $U \in \mathcal{U}$ such that $B_j \subset U$ . Thus for each $B_j$ , we choose one $U_j \in \mathcal{U}$ such that $B_j \subset U_j$ . Then $\mathcal{V}=\left\{U_j: j=1,2,3,\cdots\right\}$ is the desired subcollection. $\blacksquare$

Remark
By definition, any compact subset of the real line is also countably compact (this is also true in any topological spaces). The above lemma indicates that in the real line, the notion of compactness is equivalent to the notion of countably compactness. Outside of Euclidean spaces, there are classes of spaces in which these two notions coincide. But the topological structure along does not guarantee that these two notions of compactness coincide.

There are also other topological notions at work in this lemma, namely the Lindelof property and the property of having a countable base. A topological space is Lindelof if every open cover of the space has a countable subcollection that is also an open cover. The proof for lemma 4 essentially shows that any space whose topology is generated by a countable base is Lindelof. Furthermore, the Lindelof property is hereditary (any subspace is also Lindelof).

Theorem 5
Let $W \subset \mathbb{R}$ . The following are equivalent:

$W$ is compact.
$W$ is countably compact.
$W$ is closed and bounded.
$W$ has the Bolzano-Weierstrass property.
$W$ is sequentially compact.

Proof
$1 \Leftrightarrow 2$ This follows from definition and lemma 3. See the remark right below lemma 3.

$2 \Rightarrow 3$ Suppose that $W$ is countably compact. The fact that it is a closed set of $\mathbb{R}$ follows from the same proof in Theorem 1. We only need to show $W$ is bounded. Suppose not. Then no open interval $(-n,+n)$ contains $W$ where $n$ is positive integer. So $\mathcal{U}=\left\{(-n,+n): n \in\mathbb{N}\right\}$ is an open cover of $W$ such that no finite subset of $\mathcal{U}$ can cover $W$ , implying that $W$ is not countably compact. So if $W$ is countably compact, it must be bounded.

$3 \Rightarrow 4$ Suppose that $W$ is closed and bounded. The Bolzano-Weierstrass property follows from condition 4 of the main theorem in the previous post (The Euclidean topology of the real line (3) – Completeness).

$4 \Rightarrow 5$ Suppose that $W$ has the Bolzano-Weierstrass property. We claim that $W$ is a bounded set. Once we show that it is bounded, the property that $W$ is sequentially compact follows from the direction of $4 \rightarrow 5$ in the main theorem in the previous post (The Euclidean topology of the real line (3) – Completeness).

Suppose that $W$ is not bounded. Then for each positive integer $n$ , there is some $x_n \in W$ such that $\lvert x_n \lvert>n$ . The set $A=\left\{x_n: n \in \mathbb{N}\right\}$ is an infinite set. Note that $A$ is unbounded and every infinite subset of $A$ is also unbounded. By the Bolzano-Weierstrass property, $A$ has a limit point $p$ . Then every open interval containing $p$ contains infinitely many points of $A$ , contradicting the fact that every infinite subset of $A$ is unbounded.

$5 \Rightarrow 2$ Suppose that $W$ is sequentially compact. Suppose that $W$ is not countably compact. Then there is an open cover $\mathcal{U}=\left\{U_1,U_2,U_3,\cdots\right\}$ such that no finite subset of $\mathcal{U}$ can cover $W$ . Then for each $n$ , choose $x_n \in W$ such that $x_n \notin U_1 \cup \cdots \cup U_n$ .

By the assumption of sequential compactness, the sequence $\left\{x_n\right\}$ has a convergent subsequence $\left\{x_n\right\}_{n \in S}$ where $S$ is an infinite subset of $\mathbb{N}$ . Any convergent sequence of real numbers is bounded, contradicting the fact that the orginal sequence $\left\{x_n\right\}$ and any infinite subsequence of it are unbounded. $\blacksquare$

As consequence of Theorem 3 and theorem 5, we have the following corollary.

Corollary 6
Suppose we have closed intervals $\left\{[a_n,b_n]\right\}$ such that $\displaystyle [a_1,b_1] \supset [a_2,b_2] \supset \cdots$ .

Then $\bigcap \limits_{n=1}^{\infty} [a_n,b_n] \ne \phi$ .

Remark
In Theorem 5, the direction $3 \Rightarrow 1$ is the Heine-Borel theorem. Theorem 5 completely characterizes the compact subsets of the real line, namely the subsets that are closed and bounded (closed relative to the real line). By the theorem, closed intervals $[a,b]$ and closed subsets of $[a,b]$ are the only compact subsets of the real line. The theorem also holds in higher Euclidean spaces $\mathbb{R}^n$ .

Of the properties 2 through 5 listed in Theorem 5, it is a great topology exercise to find out which of the conditions are equivalent to compactness when considering spaces other than Euclidean spaces. What if we venture outside of Euclidean spaces? For example, what if we just consider abstract metric spaces? What if we only consider topological spaces? In cases where countably compact does not imply compactness, what kind of additional conditions would make countably compactness equivalent to compactness?

Reference

Rudin, W., Principles of Mathematical Analysis, Third Edition, 1976, McGraw-Hill, Inc, New York.
Steen, L. A. and Seebach, J. A., Counterexamples in Topology, 1995, Dover Publications, Inc, New York.
Willard, S., General Topology, 1970, Addison-Wesley Publishing Company.

The Euclidean topology of the real line (3) – Completeness

Posted on May 14, 2010 by Dan Ma

We discuss the completeness of the real line. With respect to the real line, completeness refers to the fact that the real line has no holes or gaps. There are many ways to state what it means for the real line to be complete. In this post, we state it using the least upper bound property. Then we show that this property is equivalent to a host of other statements. This discussion will be useful for subsequent posts where we discuss compactness and other properties of the real line.

Let $A \subset \mathbb{R}$ . By an upper bound of the set $A$ , we mean a real number number $w$ such that $x \le w$ for all $x \in A$ . If a set has an upper bound, we say that it is bounded above. Similarly, a lower bound of the set $A$ is a real number $y$ such that $y \le x$ for all $x \in A$ . If a set has a lower bound, then we say it is bounded below. If a set is both bounded above and bounded below, it is said to be bounded.

Suppose $A \subset \mathbb{R}$ is bounded above. By a least upper bound of the set $A$ , we mean a real number $u$ that is the smallest among all the upper bounds of $A$ , that is, the number $u$ is itself an upper bound of $A$ and for each upper bound $w$ of $A$ , we have $u \le w$ . It turns out that if a set has a least upper bound, then it is unique. Suppose $u$ and $v$ are both least upper bounds of $A$ . Then we have $u \le v$ and $v \le u$ . This imples $u=v$ .

Similarly, the number $z$ is the greatest lower bound of the set $A \subset \mathbb{R}$ if the number $z$ is a lower bound of $A$ and for each lower bound $y$ of $A$ , we have $y \le z$ . As with the least upper bound, if a set has a greatest lower bound, it has only one greatest lower bound. The following is the statement of the least upper bound property:

The Least Upper Bound Property. Every subset of the real line that is bounded above has a least upper bound.

In the discussion about the real line in this post and in subsequent posts, we will take the least upper bound property as a given. In the remainder of this post, we show that this property is equivalent to several other statements about the real line. Thus we could have taken any one of those statements as a given. We also have a statement that can be called the greatest lower bound property: every subset of the real line that is bounded below has a greatest lower bound. This statement is also equivalent to the least upper bound property.

For the definition of open intervals, open sets and closed sets, see the previous post The Euclidean topology of the real line (2). We have some more definitions.

Definitions

Let $A \subset \mathbb{R}$ . Let $p \in \mathbb{R}$ . The point $p$ is a limit point of $A$ if every open set containing $p$ contains a point of $A$ different from $p$ .
Let $\mathbb{N}$ be the set of all positive integers. A sequence of real numbers is a function $f:\mathbb{N} \rightarrow \mathbb{R}$ . We usually express $f(n)$ as $f_n$ and the function $f$ is expressed as $\lbrace{f_n}\rbrace_{n \in \mathbb{N}}$ or $\lbrace{f_n}\rbrace$ .
Given a sequence of real numbers $\lbrace{f_n}\rbrace$ , consider an infinite subset $S \subset \mathbb{N}$ . If we only consider terms of the sequence $\lbrace{f_n}\rbrace$ where the subscript $n \in S$ , then it is called a subsequence of $\lbrace{f_n}\rbrace$ . The notation is $\lbrace{f_n}\rbrace_{n \in S}$ .
A sequence $\lbrace{f_n}\rbrace$ converges if there is a number $p$ such that for every open interval $(a,b)$ containing $p$ , there is a positive integer $m$ such that $f_n \in (a,b)$ for all $n \ge m$ . The point $p$ is said to be the limit of $\lbrace{f_n}\rbrace$ . We use the notation $\lim \limits_{n \rightarrow \infty}f_n=p$ or $f_n \rightarrow p$ .
A sequence $\lbrace{f_n}\rbrace$ is said to be a Cauchy sequence if for each $c>0$ , there is a positive integer $m$ such that $\lvert f_i-f_j \lvert<c$ for all $i,j \ge m$ .
A sequence $\lbrace{f_n}\rbrace$ is said to be bounded if the set of the terms of the sequence $\left\{f_n: n \in \mathbb{N}\right\}$ is a bounded set, or equivalently there is a positive number $M$ such that for each term $f_n$ we have $\lvert f_n \lvert \le M$ .
A sequence $\lbrace{f_n}\rbrace$ is said to be nondecreasing if $f_n \le f_{n+1}$ for each $n \in \mathbb{N}$ . For such a sequence, we have $f_1 \le f_2 \le f_3 \le \cdots$ .
A sequence $\lbrace{f_n}\rbrace$ is said to be nonincreasing if $f_n \ge f_{n+1}$ for each $n \in \mathbb{N}$ . For such a sequence, we have $f_1 \ge f_2 \ge f_3 \ge \cdots$ .
A sequence $\lbrace{f_n}\rbrace$ is said to be monotonic if it is either nondecreasing or nonincreasing.

One of the properties that is equivalent to the least upper bound property is the nested interval property. It is stated as follows:

The Nested Interval Property. Suppose that for each positive interger $n$ we have closed intervals $I_n=[a_n,b_n]$ such that

$\displaystyle [a_1,b_1] \supset [a_2,b_2] \supset [a_3,b_3] \supset \cdots$

and $\lim \limits_{n \rightarrow \infty}(b_n-a_n)=0$ .

Then the intersection of the intervals $I_n$ has only one point, i.e. $\bigcap \limits_{n=1}^{\infty} [a_n,b_n]=\left\{x\right\}$ .

We incorporate some observations about sequences into a lemma, which is used in proving the main theorem below.

Lemma

If a sequence $\lbrace{x_n}\rbrace$ of real numbers converges, then the limit is unique.
If a sequence $\lbrace{x_n}\rbrace$ of real numbers converges, then the sequence is a Cauchy sequence.
If $\lbrace{x_n}\rbrace$ is a Cauchy sequence of real numbers, then it is bounded.
If a sequence $\lbrace{x_n}\rbrace$ of real numbers converges, then the sequence is bounded.
If the real number $p$ is a limit point of the set $A \subset \mathbb{R}$ , then there is a sequence $\lbrace{x_n}\rbrace$ of points of $A$ such that $\lbrace{x_n}\rbrace$ converges to $p$ .

Proof
$(1)$ Note that if a sequence converges to a point $p$ , then every open interval containing $p$ would contain all but finitely many terms in the sequence. Point $(1)$ in the lemma stems from the fact that every pair of distinct numbers in the real line are contained in two disjoint open intervals. For $x<y$ , we have disjoint open intervals $(x-0.1c,x+0.1c)$ and $(y-0.1c,y+0.1c)$ where $c=y-x$ . If both $x$ and $y$ are limits of the same sequence, then each of these two disjoint open intervals would contain all but finitely many terms in the sequence, which is impossible.

$(2)$ Let $\lbrace{x_n}\rbrace$ be a convergent sequence with $p$ as a limit. For each $c>0$ , we have $m$ such that $x_n \in (p-0.5c,p+0.5c)$ for all $n \ge m$ . Thus for all $i,j \ge m$ , we have:

$\displaystyle \lvert x_i-x_j \lvert \le \lvert x_i-p \lvert + \lvert p-x_j \lvert < 0.5c+0.5c=c$

The above shows that the sequence is a Cauchy sequence.

$(3)$ Let $\lbrace{x_n}\rbrace$ be a Cauchy sequence. For $c=0.5$ , there is some positive integer $m$ such that for all $i,j \ge m$ , we have $\lvert x_i-x_j \lvert<0.5$ . Let $w$ be the maximum of the following real numbers:

$0.5, \lvert x_1-x_{m} \lvert, \lvert x_2-x_{m} \lvert, \cdots, \lvert x_{m-1}-x_{m} \lvert$

Then for each term $x_n$ in the sequence we have $\lvert x_n-x_m \lvert \le w$ . Furthermore, we have:

$\displaystyle \lvert x_n \lvert=\lvert x_n-x_m+x_m \lvert \le \lvert x_n-x_m \lvert+\lvert x_m \lvert \le w+ \lvert x_m \lvert$

Thus $w+ \lvert x_m \lvert$ is an upper bound of the cauchy sequence in question.

$(4)$ This follows from $(2)$ and $(3)$ .

$(5)$ Let $p$ be a limit point of the set $A \subset \mathbb{R}$ . For each positive integer $j$ , let $x_j \in A$ such that $x_j \in (p-\frac{1}{j},p+\frac{1}{j})$ . Then $x_j \rightarrow p$ .

Theorem
The following statements are equivalent:

The least upper bound property.
Every bounded montonic sequence of real numbers converges.
The nested interval property.
(Bolzano-Weierstrass Theorem) Every infinite set of real numbers that is also bounded has a limit point.
Every bounded sequence of real numbers has a subsequence that converges.
Every Cauchy sequence of real numbers converges.

Remark
In some texts such as $[1]$ , completeness is defined in terms of Cauchy sequences (condition $6$ ). In a metric space, a Cauchy sequence is one where the distances of the successive terms diminishes to zero. Any space with a metric such that every Cauchy sequence converges is said to be a complete metric space. Thus the real line with the Euclidean metric is an example of a complete metric space.

In some texts, the nested interval property is taken as the definition of completeness. In a general metric space, the nested intervals are taken to be closed and bounded sets (bounded by the metric in question) with diameters $\rightarrow 0$ .

The least upper bound property is based on an order relation and is not applicable to metric spaces in general. Conditions $1,2,4,5$ do not hold in metric spaces in general but hold in Euclidean spaces.

Proof
We establish the equivalences by proving $(1) \rightarrow (2)$ , $(2) \rightarrow (3)$ , $(3) \rightarrow (4)$ , $(4) \rightarrow (5)$ , $(5) \rightarrow (6)$ , $(6) \rightarrow (3)$ and $(3) \rightarrow (1)$ .

$(1) \rightarrow (2)$
We show that every bounded nondecreasing sequence $\lbrace{x_n}\rbrace$ of real numbers converges. For the proof that every bounded nonincreasing sequence of real numbers converges, use a similar proof by working with the greatest lower bound. Suppose that the sequence $\lbrace{x_n}\rbrace$ is nondecreasing and bounded. Let $u$ be an upper bound of the set $A=\left\{x_1,x_2,x_3, \cdots\right\}$ . By the least upper bound property, the set $A$ has a least upper bound $v$ . We have the following:

$\displaystyle x_1 \le x_2 \le x_3 \le \cdots \le v \le u$

We claim that the number $v$ is the limit of the sequence $\lbrace{x_n}\rbrace$ . Let $(a,b)$ be an open interval containing $v$ , i.e, $a<v<b$ . There must be some term $x_j$ of the sequence such that $a<x_j \le v$ . Otherwise, $a$ would be an upper bound, which is impossible since $v$ is the least upper bound. Since the sequence is nondecreasing, we have $a<x_j \le x_k \le v$ for all $k \ge j$ . Thus $(2)$ is established.

$(2) \rightarrow (3)$
Suppose we have a sequence of nested intervals $[a_n,b_n]$ such that the widths of the intervals $b_n-a_n \rightarrow 0$ . The sequence $\lbrace{a_n}\rbrace$ is nondecreasing and has an upper bound (e.g. $b_1$ ). By $(2)$ , this sequence converges, say to the limit $a$ . On the other hand, the sequence $\lbrace{b_n}\rbrace$ is nonincreasing and has an lower bound (e.g. $a_1$ ). Thus this sequence converges, say to the limit $b$ .

Note that $[a,b] \subset [a_n,b_n]$ for each $n$ . Since $b_n-a_n \rightarrow 0$ , $a=b$ .

$(3) \rightarrow (4)$
Suppose $A \subset \mathbb{R}$ is an infinite set and is bounded. We produce a limit point by the approach of “divide and conquer”. Suppose that $A \subset [a,b]$ . Let $a_1=a$ and $b_1=b$ . Divide this interval into two equal halves, $[a_1,m]$ and $[m,b_1]$ where $m=0.5(a_1+b_1)$ . Since $A$ is infinite, one of these two halves has to contain infinitely many points of $A$ . Otherwise, $A$ is a finite set. Pick a half that has infinitely many points of $A$ and let $a_2$ be the left endpoint of this interval and $b_2$ be the right endpoint.

Continue this process inductively. Suppose $[a_n,b_n]$ has been chosen. Then we divide it into $[a_n,m]$ and $[m,b_n]$ where $m=0.5(a_n+b_n)$ . Pick a half that has infinitely many points of $A$ and let $a_{n+1}$ be the left endpoint and $b_{n+1}$ be the right endpoint. Then we have a nested sequence of decreasing intervals. Since we keep dividing each stage into halves, the lengths of the intervals $b_n-a_n$ approaches $0$ . By the nested interval property, there is only one point $x$ in the intersection of the intervals.

The point $x$ is a limit point of $A$ . To see this, let $(s,t)$ be an open interval containing $x$ . Then for some sufficiently large $n$ we have $[a_n,b_n] \subset (s,t)$ . Then the open interval $(s,t)$ contains infinitely many points of $A$ .

$(4) \rightarrow (5)$
Suppose $\lbrace{x_n}\rbrace$ is a bounded sequence of real numbers. We aim to produce a subsequence that converges. Let $A$ be the set of all terms in the sequence. The set $A$ is expressed as the following:

$A=\left\{x_1,x_2,x_3, \cdots \right\}$

Suppose $A$ is a finite set. Then starting at some integer $m$ , $x_m=x_{m+1}=x_{m+2}=\cdots$ . The sequence $\lbrace{x_n}\rbrace_{n \ge m}$ is a subsequence that is a constant sequence (thus converges). Suppose $A$ is an infinite set. By $(4)$ , $A$ has a limit point. Let $p$ be one limit point of $A$ . By $(5)$ in the lemma, there is a sequence of points from $A$ converging to $p$ . This sequence would be a subsequence of $\lbrace{x_n}\rbrace$ .

$(5) \rightarrow (6)$
By the lemma, any Cauchy sequence of real numbers is bounded. Let $\lbrace{x_n}\rbrace$ be a Cauchy sequence of real numbers. By $(5)$ , there is a subsequence $\lbrace{x_{n(j)}}\rbrace$ that converges. Let $p$ be the limit of the subsequence. Note that $p$ is also the limit of the original sequence $\lbrace{x_n}\rbrace$ .

$(6) \rightarrow (3)$
Let $[a_n,b_n]$ be a sequence of intervals satisfying the nested interval property. Then $\lbrace{a_n}\rbrace$ is a Cauchy sequence, which converges, say to the point $p$ . Then $p$ is the lone point that belongs to each $[a_n,b_n]$ .

$(3) \rightarrow (1)$
Suppose that $A \subset \mathbb{R}$ is bounded above. Let $B$ be the set of all upper bounds of $A$ . Note that for each $x \in A$ , $x$ is a lower bound of $B$ . Pick $x \in A$ and $y \in B$ . Let $a_1=x$ and $b_1=y$ . If there are only finitely many point of $B$ in between $a_1$ and $b_1$ , then the smallest points of $B$ would be the least upper bound of $A$ and we are done. So assume that $[a_1,b_1]$ contains infinitely many points of $B$ (i.e. infinitely many upper bounds of $A$ ).

Consider $[a_1,m]$ and $[m,b_1]$ where $m=0.5(a_1+b_1)$ . If the left interval $[a_1,m]$ contains upper bounds of $A$ , we assume that that it has infinitely many of them (otherwise, the minimum would be the least upper bound and we are done). Choose one of these intervals that contains infinitely many points of $B$ . If both intervals contain infinitely many points of $B$ , we choose the leftmost one. Then we let $a_2$ be the left endpoint of the chosen interval and $b_2$ be the right endpoint of the interval. We observe that to the left of $a_2$ , there are no upper bounds of $A$ (points of $B$ ).

Continue this process inductively, making sure that in each step we divide the previous interval $[a_n,b_n]$ into two equal halves. If the left interval contains upper bounds of $A$ , we assume that it has infinitely many of them (otherwise, we stop at this inductive step). We choose the first half interval that contains infinitely many upper bounds of $A$ and denote it by $[a_{n+1},b_{n+1}]$ . Observe that to the left of $a_{n+1}$ , there are no upper bounds of $A$ .

As indicated in the induction step, if we can stop at any one of the step, we would have a least upper bound of $A$ and we are done. Otherwise, we have a nested sequence of intervals $[a_n,b_n]$ such that the widths of the intervals $\rightarrow 0$ . Then the intervals have exactly one point $p$ in the intersection.

We claim that $p$ is the desired least upper bound of $A$ . First of all, there is no upper bounds of $A$ to the left of $p$ . This stems from the observation that no upper bounds of $A$ can be found at the left side of each $a_n$ and the fact that $\left\{a_n\right\}$ converges to $p$ . Thus if $p$ is an upper bound of $A$ , then $p$ is the least upper bound. Note that $p$ is a limit point of $B$ since every interval $[a_n,b_n]$ contains infinitely many points of $B$ . If $p$ is not an upper bound of $A$ , then there is some point $q$ of $A$ such that $p<q$ . Then the interval $(p, q)$ contains no points of $B$ (upper bounds of $A$ ). This constradicts the fact that $p$ is a limit point of $B$ . So $p$ must be an upper bound of $A$ . This establishes the least upper bound property.

Reference

Rudin, W., Principles of Mathematical Analysis, Third Edition, 1976, McGraw-Hill, New York.

Dan Ma's Topology Blog

Expository Articles In General Topology

Category Archives: Introductory topology

Closed uncountable subsets of the real line

Perfect sets and Cantor sets, II

The Lindelof property of the real line

Perfect sets and Cantor sets, I

The Cantor set, III

The Cantor set, II

The Cantor set, I

The Cantor bus tour

The Euclidean topology of the real line (4) – Compactness

The Euclidean topology of the real line (3) – Completeness