# Adding up to a non-meager set

The preceding post gives a topological characterization of bounded subsets of $\omega^\omega$. From it, we know what it means topologically for a set to be unbounded. In this post we prove a theorem that ties unbounded sets to Baire category.

A set is nowhere dense if its closure has empty interior. A set is a meager set if it is the union of countably many nowhere dense sets. By definition, the union of countably many meager sets is always a meager set. In order for meager sets to add up to a non-meager set (though taking union), the number of meager sets must be uncountable. What is this uncountable cardinal number? We give an indication of how big this number is. In this post we give a constructive proof to the following fact:

Theorem 1 …. Given an unbounded set $F \subset \omega^\omega$, there exist $\kappa=\lvert F \lvert$ many meager subsets of the real line whose union is not meager.

We will discuss the implications of this theorem after giving background information.

We use $\omega$ to denote the set of all non-negative integers $\{ 0,1,2,\cdots \}$. The set $\omega^\omega$ is the set of all functions from $\omega$ into $\omega$. It is called the Baire space when it is topologized with the product space topology. It is well known that the Baire space is homeomorphic to the space of irrational numbers $\mathbb{P}$ (see here).

The notion of boundedness or unboundedness used in Theorem 1 refers to the eventual domination order ($\le^*$) for functions in the product space. For $f,g \in \omega^\omega$, by $f \le^* g$, we mean $f(n) \le g(n)$ for all but finitely many $n$. A set $F \subset \omega^\omega$ is bounded if it has an upper bound with respect to the partial order $\le^*$, i.e. there is some $f \in \omega^\omega$ such that $g \le^* f$ for all $g \in F$. The set $F$ is unbounded if it is not bounded. To spell it out, $F$ is unbounded if for each $f \in \omega^\omega$, there exists $g \in F$ such that $g \not \le^* f$, i.e. $f(n) for infinitely many $n$.

All countable subsets of the Baire space are bounded (using a diagonal argument). Thus unbounded sets must be uncountable. It does not take extra set theory to obtain an unbounded set. The Baire space $\omega^\omega$ is unbounded. More interesting unbounded sets are those of a certain cardinality, say unbounded sets of cardinality $\omega_1$ or unbounded sets with cardinality less than continuum. Another interesting unbounded set is one that is of the least cardinality. In the literature, the least cardinality of an unbounded subset of $\omega^\omega$ is called $\mathfrak{b}$, the bounding number.

Another notion that is part of Theorem 1 is the topological notion of small sets – meager sets. This is a topological notion and is defined in topological spaces. For the purpose at hand, we consider this notion in the context of the real line. As mentioned at the beginning of the post, a set is nowhere dense set if its closure has empty interior (i.e. the closure contains no open subset). Let $A \subset \mathbb{R}$. The set $A$ is nowhere dense if no open set is a subset of the closure $\overline{A}$. An equivalent definition: the set $A$ is nowhere dense if for every nonempty open subset $U$ of the real line, there is a nonempty subset $V$ of $U$ such that $V$ contains no points of $A$. Such a set is “thin” since it is dense no where. In any open set, we can also find an open subset that has no points of the nowhere dense set in question. A subset $A$ of the real line is a meager set if it is the union of countably many nowhere dense sets. Another name of meager set is a set of first category. Any set that is not of first category is called a set of second category, or simply a non-meager set.

Corollaries

Subsets of the real line are either of first category (small sets) or of second category (large sets). Countably many meager sets cannot fill up the real line. This is a consequence of the Baire category theorem (see here). By definition, caountably many meager sets cannot fill up any non-meager subset of the real line. How many meager sets does it take to add up to a non-meager set?

Theorem 1 gives an answer to the above question. It can take as many meager sets as the size of an unbounded subset of the Baire space. If $\kappa$ is a cardinal number for which there exists an unbounded subset of $\omega^\omega$ whose cardinality is $\kappa$, then there exists a non-meager subset of the real line that is the union of $\kappa$ many meager sets. The bounding number $\mathfrak{b}$ is the least cardinality of an unbounded set. Thus there is always a non-meager subset of the real line that is the union of $\mathfrak{b}$ many meager sets.

Let $\kappa_A$ be the least cardinal number $\kappa$ such that there exist $\kappa$ many meager subsets of the real line whose union is not meager. Based on Theorem 1, the bounding number $\mathfrak{b}$ is an upper bound of $\kappa_A$. These two corollaries just discussed are:

• There always exists a non-meager subset of the real line that is the union of $\mathfrak{b}$ many meager sets.
• $\kappa_A \le \mathfrak{b}$.

The bounding number $\mathfrak{b}$ points to a non-meager set that is the union of $\mathfrak{b}$ many meager sets. However, the cardinal $\kappa_A$ is the least number of meager sets whose union is a non-meager set and this number is no more than the bounding number. The cardinal $\kappa_A$ is called the additivity number.

There are other corollaries to Theorem 1. Let $A(c)$ be the statement that the union of fewer than continuum many meager subsets of the real line is a meager set. For any cardinal number $\kappa$, let $A(\kappa)$ be the statement that the union of fewer than $\kappa$ many meager subsets of the real line is a meager set. We have the following corollaries.

• The statement $A(c)$ implies that there are no unbounded subsets of $\omega^\omega$ that have cardinalities less than continuum. In other words, $A(c)$ implies that the bounding number $\mathfrak{b}$ is continuum.
• Let $\kappa \le$ continuum. The statement $A(\kappa)$ implies that there are no unbounded subsets of $\omega^\omega$ that have cardinalities less than $\kappa$. In other words, $A(\kappa)$ implies that the bounding number $\mathfrak{b}$ is at least $\kappa$, i.e. $\mathfrak{b} \ge \kappa$.

Let $B(c)$ be the statement that the real line is not the union of less than continuum many meager sets. Clearly, the statement $A(c)$ implies the statement $B(c)$. Thus, it follows from Theorem 1 that $A(c) \Longrightarrow B(c) + \mathfrak{b}=2^{\aleph_0}$. This is a result proven in Miller [1]. Theorem 1.2 in [1] essentially states that $A(c)$ is equivalent to $B(c) + \mathfrak{b}=2^{\aleph_0}$. The proof of Theorem 1 given here is essentially the proof of one direction of Theorem 1.2 in [1]. Our proof has various omitted details added. As a result it should be easier to follow. We also realize that the proof of Theorem 1.2 in [1] proves more than that theorem. Therefore we put the main part of the constructive in a separate theorem. For example, Theorem 1 also proves that the additivity number $\kappa_A$ is no more than $\mathfrak{b}$. This is one implication in the Cichon’s diagram.

Proof of Theorem 1

Let $2=\{ 0,1 \}$. The set $2^\omega$ is the set of all functions from $\omega$ into $\{0, 1 \}$. When $2^\omega$ is endowed with the product space topology, it is called the Cantor space and is homemorphic to the middle-third Cantor set in the unit interval $[0,1]$. We use $\{ [s]: \exists \ n \in \omega \text{ such that } s \in 2^n \}$ as a base for the product topology where $[s]=\{ t \in 2^\omega: s \subset t \}$.

Let $F \subset \omega^\omega$ be an unbounded set. We assume that the unbounded set $F$ satisfies two properties.

• Each $g \in F$ is an increasing function, i.e. $g(i) for any $i.
• For each $g \in F$, if $j>g(n)$, then $g(j)>g(n+1)$.

One may wonder if the two properties are satisfied by any given unbounded set. Since $F$ is unbounded, we can increase the values of each function $g \in F$, the resulting set will still be an unbounded set. More specifically, for each $g \in F$, define $g^*\in \omega^\omega$ as follows:

• $g^*(0)=g(0)+1$,
• for each $n \ge 1$, $g^*(n)=g(n)+\text{max}\{ g^*(i): i.

The set $F^*=\{ g^*: g \in F \}$ is also an unbounded set. Therefore we use $F^*$ and rename it as $F$.

Fix $g \in F$. Define an increasing sequence of non-negative integers $n_0,n_1,n_2,\cdots$ as follows. Let $n_0$ be any integer greater than 1. For each integer $j \ge 1$, let $n_j=g(n_{j-1})$. Since $n_0>1$, we have $n_1=g(n_0)>g(1)$. It follows that for all integer $k \ge 1$, $n_k>g(k)$.

For each $g \in F$, we have an associated sequence $n_0,n_1,n_2,\cdots$ as described in the preceding paragraph. Now define $C(g)=\{ q \in 2^\omega: \forall \ k, q(n_k)=1 \}$. It is straightforward to verify that each $C(g)$ is a closed and nowhere dense subset of the Cantor space $2^\omega$. Let $X=\bigcup \{C(g): g \in F \}$. The set $X$ is a union of meager sets. We show that it is a non-meager subset of $2^\omega$. We prove the following claim.

Claim 1
For any countable family $\{C_n: n \in \omega \}$ where each $C_n$ is a nowhere dense subset of $2^\omega$, we have $X \not \subset \bigcup \{C_n: n \in \omega \}$.

According to Claim 1, the set $X$ cannot be contained in any arbitrary meager subset of $2^\omega$. Thus $X$ must be non-meager. To establish the claim, we define an increasing sequence of non-negative integers $m_0,m_1,m_2,\cdots$ with the property that for any $k \ge 1$, for any $i, and for any $s \in 2^{m_k}$, there exists $t \in 2^{m_{k+1}}$ such that $s \subset t$ and $[t] \cap C_i=\varnothing$.

The desired sequence is derived from the fact that the sets $C_n$ are nowhere dense. Choose any $m_0 to start. With $m_1$ determined, the only nowhere dense set to consider is $C_0$. For each $s \in 2^{m_1}$, choose some integer $y>m_1$ such that there exists $t \in 2^{y+1}$ such that $s \subset t$ and $[t] \cap C_0=\varnothing$. Let $m_2$ be an integer greater than all the possible $y$‘s that have been chosen. The integer $m_2$ can be chosen since there are only finitely many $s \in 2^{m_1}$.

Suppose $m_0<\cdots have been chosen. Then the only nowhere dense sets to consider are $C_0,\cdots,C_{k-1}$. Then for each $i \le k-1$, for each $s \in 2^{m_k}$, choose some integer $y>m_k$ such that there exists $t \in 2^{y+1}$ such that $s \subset t$ and $[t] \cap C_i=\varnothing$. As before let $m_{k+1}$ be an integer greater than all the possible $y$‘s that have been chosen. Again $m_{k+1}$ is possible since there are only finitely many $i \le k-1$ and only finitely many $s \in 2^{m_k}$.

Let $Z=\{ m_k: k \in \omega \}$. We make the following claim.

Claim 2
There exists $h \in F$ such that the associated sequence $n_0, n_1,n_2,\cdots$ satisfies the condition: $\lvert [n_k,n_{k+1}) \cap Z \lvert \ge 2$ for infinitely many $k$ where $[n_k,n_{k+1})$ is the set $\{ m \in \omega: n_k \le m < m_{k+1} \}$.

Suppose Claim 2 is not true. For each $g \in F$ and its associated sequence $n_0, n_1,n_2,\cdots$,

(*) there exists some integer $b$ such that for all $k>b$, $\lvert [n_k,n_{k+1}) \cap Z \lvert \le 1$.

Let $f \in \omega^\omega$ be defined by $f(k)=m_k$ for all $k$. Choose $\overline{f} \in \omega^\omega$ in the following manner. For each $k \in \omega$, define $d_k \in \omega^\omega$ by $d_k(n)=f(n+k)$ for all $n$. Then choose $\overline{f} \in \omega^\omega$ such that $d_k \le^* \overline{f}$ for all $k$.

Fix $g \in F$. Let $m_j$ be the least element of $[n_b, \infty) \cap Z$. Then for each $k>b$, we have $g(k) \le n_k \le m_{j+k}=f(j+k)=d_j(k)$. Note that the inequality $n_k \le m_{j+k}$ holds because of the assumption (*). It follows that $g \le^* d_j \le^* \overline{f}$. This says that $\overline{f}$ is an upper bound of $F$ contradicting that $F$ is an unbounded set. Thus Claim 2 must be true.

Let $h \in F$ be as described in Claim 2. We now prove another claim.

Claim 3
For each $n$, $C_n$ is a nowhere dense subset of $C(h)$.

Fix $C_n$. Let $p$ be an integer such that $[n_p,n_{p+1}) \cap Z$ has at least two points, say $m_k$ and $m_{k+1}$. We can choose $p$ large enough such that $n. Choose $s \in 2^{m_k}$. Since $n_p$ is arbitrary, $[s]$ is an arbitrary open set in $2^\omega$. Since $m_k$ is in between $n_p$ and $n_{p+1}$, $[s]$ contains a point of $C(h)$. Thus $[s] \cap C(h)$ is an arbitrary open set in $C(h)$. By the way $m_k$ and $m_{k+1}$ are chosen originally, there exists $t \in 2^{m_{k+1}}$ such that $s \subset t$ and $[t] \cap C_n=\varnothing$. Because $m_k$ and $m_{k+1}$ are in between $n_p$ and $n_{p+1}$, $[t] \cap C(h) \ne \varnothing$. This establishes the claim that $C_n$ is nowhere dense subset of $C(h)$.

Note that $C(h)$ is a closed subset of the Cantor space $2^\omega$ and hence is also compact. Thus $C(h)$ is a Baire space and cannot be the union of countably many nowhere dense sets. Thus $C(h) \not \subset \cup \{C_n: n \in \omega \}$. Otherwise, $C(h)$ would be the union of countably many nowhere dense sets. This means that $X=\bigcup \{C(g): g \in F \} \not \subset \cup \{C_n: n \in \omega \}$. This establishes Claim 1.

Considering the Cantor space $2^\omega$ as a subspace of the real line, each $C(g)$ is also a closed nowhere dense subset of the real line. The set $X=\bigcup \{C(g): g \in F \}$ is also not a meager subset of the real line. This establishes Theorem 1. $\square$

Reference

1. Miller A. W., Some properties of measure and category, Trans. Amer. Math. Soc., 266, 93-114, 1981.

$\text{ }$

$\text{ }$

$\text{ }$

Dan Ma topology

Daniel Ma topology

Dan Ma math

Daniel Ma mathematics

$\copyright$ 2020 – Dan Ma

# Compact metrizable scattered spaces

A scattered space is one in which there are isolated points found in every subspace. Specifically, a space $X$ is a scattered space if every non-empty subspace $Y$ of $X$ has a point $y \in Y$ such that $y$ is an isolated point in $Y$, i.e. the singleton set $\left\{y \right\}$ is open in the subspace $Y$. A handy example is a space consisting of ordinals. Note that in a space of ordinals, every non-empty subset has an isolated point (e.g. its least element). In this post, we discuss scattered spaces that are compact metrizable spaces.

Here’s what led the author to think of such spaces. Consider Theorem III.1.2 found on page 91 of Arhangelskii’s book on topological function space [1], which is Theorem 1 stated below:

Thereom 1
For any compact space $X$, the following conditions are equivalent:

• The function space $C_p(X)$ is a Frechet-Urysohn space.
• The function space $C_p(X)$ is a k space.
• $X$ is a scattered space.

Let’s put aside the Frechet-Urysohn property and the k space property for the moment. For any Hausdorff space $X$, let $C(X)$ be the set of all continuous real-valued functions defined on the space $X$. Since $C(X)$ is a subspace of the product space $\mathbb{R}^X$, a natural topology that can be given to $C(X)$ is the subspace topology inherited from the product space $\mathbb{R}^X$. Then $C_p(X)$ is simply the set $C(X)$ with the product subspace topology (also called the pointwise convergence topology).

Let’s say the compact space $X$ is countable and infinite. Then the function space $C_p(X)$ is metrizable since it is a subspace of $\mathbb{R}^X$, a product of countably many lines. Thus the function space $C_p(X)$ has the Frechet-Urysohn property (being metrizable implies Frechet-Urysohn). This means that the compact space $X$ is scattered. The observation just made is a proof that any infinite compact space that is countable in cardinality must be scattered. In particular, every infinite compact and countable space must have an isolated point. There must be a more direct proof of this same fact without taking the route of a function space. The indirect argument does not reveal the essential nature of compact metric spaces. The essential fact is that any uncountable compact metrizable space contains a Cantor set, which is as unscattered as any space can be. Thus the only scattered compact metrizable spaces are the countable ones.

The main part of the proof is the construction of a Cantor set in a compact metrizable space (Theorem 3). The main result is Theorem 4. In many settings, the construction of a Cantor set is done in the real number line (e.g. the middle third Cantor set). The construction here is in a more general setting. But the idea is still the same binary division process – the splitting of a small open set with compact closure into two open sets with disjoint compact closure. We also use that fact that any compact metric space is hereditarily Lindelof (Theorem 2).

____________________________________________________________________

Compact metrizable spaces

We first define some notions before looking at compact metrizable spaces in more details. Let $X$ be a space. Let $A \subset X$. Let $p \in X$. We say that $p$ is a limit point of $A$ if every open subset of $X$ containing $p$ contains a point of $A$ distinct from $p$. So the notion of limit point here is from a topology perspective and not from a metric perspective. In a topological space, a limit point does not necessarily mean that it is the limit of a convergent sequence (however, it does in a metric space). The proof of the following theorem is straightforward.

Theorem 2
Let $X$ be a hereditarily Lindelof space (i.e. every subspace of $X$ is Lindelof). Then for any uncountable subset $A$ of $X$, all but countably many points of $A$ are limit points of $A$.

We now discuss the main result.

Theorem 3
Let $X$ be a compact metrizable space such that every point of $X$ is a limit point of $X$. Then there exists an uncountable closed subset $C$ of $X$ such that every point of $C$ is a limit point of $C$.

Proof of Theorem 3
Note that any compact metrizable space is a complete metric space. Consider a complete metric $\rho$ on the space $X$. One fact that we will use is that if there is a sequence of closed sets $X \supset H_1 \supset H_2 \supset H_3 \supset \cdots$ such that the diameters of the sets $H$ (based on the complete metric $\rho$) decrease to zero, then the sets $H_n$ collapse to one point.

The uncountable closed set $C$ we wish to define is a Cantor set, which is constructed from a binary division process. To start, pick two points $p_0,p_1 \in X$ such that $p_0 \ne p_1$. By assumption, both points are limit points of the space $X$. Choose open sets $U_0,U_1 \subset X$ such that

• $p_0 \in U_0$,
• $p_1 \in U_1$,
• $K_0=\overline{U_0}$ and $K_1=\overline{U_1}$,
• $K_0 \cap K_1 = \varnothing$,
• the diameters for $K_0$ and $K_1$ with respect to $\rho$ are less than 0.5.

Note that each of these open sets contains infinitely many points of $X$. Then we can pick two points in each of $U_0$ and $U_1$ in the same manner. Before continuing, we set some notation. If $\sigma$ is an ordered string of 0’s and 1’s of length $n$ (e.g. 01101 is a string of length 5), then we can always extend it by tagging on a 0 and a 1. Thus $\sigma$ is extended as $\sigma 0$ and $\sigma 1$ (e.g. 01101 is extended by 011010 and 011011).

Suppose that the construction at the $n$th stage where $n \ge 1$ is completed. This means that the points $p_\sigma$ and the open sets $U_\sigma$ have been chosen such that $p_\sigma \in U_\sigma$ for each length $n$ string of 0’s and 1’s $\sigma$. Now we continue the picking for the $(n+1)$st stage. For each $\sigma$, an $n$-length string of 0’s and 1’s, choose two points $p_{\sigma 0}$ and $p_{\sigma 1}$ and choose two open sets $U_{\sigma 0}$ and $U_{\sigma 1}$ such that

• $p_{\sigma 0} \in U_{\sigma 0}$,
• $p_{\sigma 1} \in U_{\sigma 1}$,
• $K_{\sigma 0}=\overline{U_{\sigma 0}} \subset U_{\sigma}$ and $K_{\sigma 1}=\overline{U_{\sigma 1}} \subset U_{\sigma}$,
• $K_{\sigma 0} \cap K_{\sigma 1} = \varnothing$,
• the diameters for $K_{\sigma 0}$ and $K_{\sigma 1}$ with respect to $\rho$ are less than $0.5^{n+1}$.

For each positive integer $m$, let $C_m$ be the union of all $K_\sigma$ over all $\sigma$ that are $m$-length strings of 0’s and 1’s. Each $C_m$ is a union of finitely many compact sets and is thus compact. Furthermore, $C_1 \supset C_2 \supset C_3 \supset \cdots$. Thus $C=\bigcap \limits_{m=1}^\infty C_m$ is non-empty. To complete the proof, we need to show that

• $C$ is uncountable (in fact of cardinality continuum),
• every point of $C$ is a limit point of $C$.

To show the first point, we define a one-to-one function $f: \left\{0,1 \right\}^N \rightarrow C$ where $N=\left\{1,2,3,\cdots \right\}$. Note that each element of $\left\{0,1 \right\}^N$ is a countably infinite string of 0’s and 1’s. For each $\tau \in \left\{0,1 \right\}^N$, let $\tau \upharpoonright n$ denote the string of the first $n$ digits of $\tau$. For each $\tau \in \left\{0,1 \right\}^N$, let $f(\tau)$ be the unique point in the following intersection:

$\displaystyle \bigcap \limits_{n=1}^\infty K_{\tau \upharpoonright n} = \left\{f(\tau) \right\}$

This mapping is uniquely defined. Simply conceptually trace through the induction steps. For example, if $\tau$ are 01011010…., then consider $K_0 \supset K_{01} \supset K_{010} \supset \cdots$. At each next step, always pick the $K_{\tau \upharpoonright n}$ that matches the next digit of $\tau$. Since the sets $K_{\tau \upharpoonright n}$ are chosen to have diameters decreasing to zero, the intersection must have a unique element. This is because we are working in a complete metric space.

It is clear that the map $f$ is one-to-one. If $\tau$ and $\gamma$ are two different strings of 0’s and 1’s, then they must differ at some coordinate, then from the way the induction is done, the strings would lead to two different points. It is also clear to see that the map $f$ is reversible. Pick any point $x \in C$. Then the point $x$ must belong to a nested sequence of sets $K$‘s. This maps to a unique infinite string of 0’s and 1’s. Thus the set $C$ has the same cardinality as the set $\left\{0,1 \right\}^N$, which has cardinality continuum.

To see the second point, pick $x \in C$. Suppose $x=f(\tau)$ where $\tau \in \left\{0,1 \right\}^N$. Consider the open sets $U_{\tau \upharpoonright n}$ for all positive integers $n$. Note that $x \in U_{\tau \upharpoonright n}$ for each $n$. Based on the induction process described earlier, observe these two facts. This sequence of open sets has diameters decreasing to zero. Each open set $U_{\tau \upharpoonright n}$ contains infinitely many other points of $C$ (this is because of all the open sets $U_{\tau \upharpoonright k}$ that are subsets of $U_{\tau \upharpoonright n}$ where $k \ge n$). Because the diameters are decreasing to zero, the sequence of $U_{\tau \upharpoonright n}$ is a local base at the point $x$. Thus, the point $x$ is a limit point of $C$. This completes the proof. $\blacksquare$

Theorem 4
Let $X$ be a compact metrizable space. It follows that $X$ is scattered if and only if $X$ is countable.

Proof of Theorem 4
$\Longleftarrow$
In this direction, we show that if $X$ is countable, then $X$ is scattered (the fact that can be shown using the function space argument pointed out earlier). Here, we show the contrapositive: if $X$ is not scattered, then $X$ is uncountable. Suppose $X$ is not scattered. Then every point of $X$ is a limit point of $X$. By Theorem 3, $X$ would contain a Cantor set $C$ of cardinality continuum.

$\Longrightarrow$
In this direction, we show that if $X$ is scattered, then $X$ is countable. We also show the contrapositive: if $X$ is uncountable, then $X$ is not scattered. Suppose $X$ is uncountable. By Theorem 2, all but countably many points of $X$ are limit points of $X$. After discarding these countably many isolated points, we still have a compact space. So we can just assume that every point of $X$ is a limit point of $X$. Then by Theorem 3, $X$ contains an uncountable closed set $C$ such that every point of $C$ is a limit point of $C$. This means that $X$ is not scattered. $\blacksquare$

____________________________________________________________________

Remarks

A corollary to the above discussion is that the cardinality for any compact metrizable space is either countable (including finite) or continuum (the cardinality of the real line). There is nothing in between or higher than continuum. To see this, the cardinality of any Lindelof first countable space is at most continuum according to a theorem in this previous post (any compact metric space is one such). So continuum is an upper bound on the cardinality of compact metric spaces. Theorem 3 above implies that any uncountable compact metrizable space has to contain a Cantor set, hence has cardinality continuum. So the cardinality of a compact metrizable space can be one of two possibilities – countable or continuum. Even under the assumption of the negation of the continuum hypothesis, there will be no uncountable compact metric space of cardinality less than continuum. On the other hand, there is only one possibility for the cardinality of a scattered compact metrizable, which is countable.

____________________________________________________________________

Reference

1. Arkhangelskii, A. V., Topological Function Spaces, Mathematics and Its Applications Series, Kluwer Academic Publishers, Dordrecht, 1992.

____________________________________________________________________
$\copyright \ 2015 \text{ by Dan Ma}$

# Bernstein Sets and the Michael Line

Let $\mathbb{M}$ be the Michael line and let $\mathbb{P}$ be the set of all irrational numbers with the Euclidean topology. In the post called “Michael Line Basics”, we show that the product $\mathbb{M} \times \mathbb{P}$ is not normal. This is a classic counterexample showing that the product of two paracompact spaces need not be normal even when one of the factors is a complete metric space. The Michael line $\mathbb{M}$ is not Lindelof. A natural question is: can the first factor be made a Lindelof space? In this post, as an application of Bernstein sets, we present a non-normal product space where one factor is Lindelof and the other factor is a separable metric space. It is interesting to note that while one factor is upgraded (from paracompact to Lindelof), the other factor is downgraded (from a complete metric space to just a separable metric space).

Bernstein sets have been discussed previously in this blog. They are special subsets of the real line and with the Euclidean subspace topology, they are spaces in which the Banach-Mazur game is undecidable (see the post “Bernstein Sets Are Baire Spaces”). A Bernstein set is a subset $B$ of the real line such that every uncountable closed subset of the real line has non-empty intersection with both $B$ and the complement of $B$.

Bernstein sets are constructed by transfinite induction. The procedure starts by ordering all uncountable closed subsets of the real line in a sequence of length that is as long as the cardinality of continuum. To see how Bernstein sets are constructed, see the post “Bernstein Sets Are Baire Spaces”.

After we discuss a generalization of the definition of the Michael line, we discuss the non-normal product space based on Bernstein sets.
___________________________________________________________________________________

Generalizing the Michael Line

Let $\mathbb{R}$ be the real number line. Let $\mathbb{P}$ be the set of all irrational numbers and let $\mathbb{Q}=\mathbb{R}-\mathbb{P}$. Recall that the Michael line is the real line $\mathbb{R}$ topologized by letting points in $\mathbb{P}$ discrete and letting points in $\mathbb{Q}$ retain their usual open neighborhoods. We can carry out the same process on any partition of the real number line.

Let $D$ and $E$ be disjoint sets such that $\mathbb{R}=D \cup E$ where the set $E$ is dense in the real line. The intention is to make $D$ the discrete part and $E$ the Euclidean part. In other words, we topologize $\mathbb{R}$ be letting points in $D$ discrete and letting points in $E$ retain their Euclidean open sets. Let $X_D$ denote the resulting topological space. For the lack of a better term, we call the space $X_D$ the modified Michael line. An open set in the space $X_D$ is of the form $U \cup V$ where $U$ is a Euclidean open subset of the real line and $V \subset D$. We have the following result:

Proposition
Suppose that $D$ is not an $F_\sigma$-set in the Euclidean real line and that $D$ is dense in the Euclidean real line. Then the product space $X_D \times D$ is not normal (the second factor $D$ is considered a subspace of the Euclidean real line).

In the post “Michael Line Basics”, we give a proof that $\mathbb{M} \times \mathbb{P}$ is not normal. This proof hinges on the same two facts about the set $D$ in the hypothesis in the above proposition. Thus the proof for the above proposition is just like the one for $\mathbb{M} \times \mathbb{P}$. Whenever we topologize the modified Michael line by using a non-$F_\sigma$-set as the discrete part, we can always be certain that we have a non-normal product as indicated here.

___________________________________________________________________________________

Non-Normal Product Space

Let $B$ be any Bernstein set. The set $B$ is clearly not an $F_\sigma$-set in the real line and is clearly dense in the real line. Then $X_B \times B$ is not normal. Note that in $X_B$, the set $B$ is discrete and its complement $\mathbb{R}-B$ has the usual topology. To see that $X_B$ is Lindelof, note that any open cover of $X_B$ has a countable subcollection that covers $\mathbb{R}-B$. This countable subcollection consists of Euclidean open sets. Furthermore, the complement of the union of these countably many Euclidean open sets must contain all but countably many points of the Bernstein set $B$ (otherwise there would be an uncountable Euclidean closed set that misses $B$).

As commented at the beginning, in obtaining this non-normal product space, one factor is enhanced at the expense of the other factor (one is made Lindelof while the other is no longer a complete metric space). Even though any Bernstein set (with the Euclidean topology) is a separable metric space, it cannot be completely metrizable. Any completely metrizable subset of the real line must be a $G_\delta$-set in the real line. Furthermore any uncountable $G_\delta$ subset of the real line must contain a Cantor set and thus cannot be a Bernstein set.

A similar example to $X_B \times B$ is presented in E. Michael’s paper (see [3]). It is hinted in footnote 4 of that paper that with the additional assumption of continuum hypothesis (CH), one can have a non-normal product space where one factor is a Lindelof space and the second factor is the space of irrationals. So with an additional set-theoretic assumption, we can keep one factor from losing complete metrizability. For this construction, see point (d) in Example 3.2 of [2].

___________________________________________________________________________________

A Brief Remark

Note that the Lindelof space $X_B$ presented here is not hereditarily Lindelof, since it has uncountably many isolated points. Can a hereditarily Lindelof example be constructed such that its product with a particular separable metric space is not normal? The answer is no. The product of a hereditarily Lindelof space and any separable metric space is hereditarily Lindelof (see Result 4 in the post Cartesian Products of Two Paracompact Spaces – Continued).

___________________________________________________________________________________

Reference

1. Engelking, R., General Topology, Revised and Completed edition, Heldermann Verlag, Berlin, 1989.
2. Michael, E., Paracompactness and the Lindelof property in Finite and Countable Cartesian Products, Compositio Math. 23 (1971) 199-214.
3. Michael, E., The product of a normal space and a metric space need not be normal, Bull. Amer. Math. Soc., 69 (1963) 375-376.
4. Willard, S., General Topology, Addison-Wesley Publishing Company, 1970.

___________________________________________________________________________________

$\copyright \ \ 2012$

# Bernstein Sets Are Baire Spaces

A topological space $X$ is a Baire space if the intersection of any countable family of open and dense sets in $X$ is dense in $X$ (or equivalently, every nonempty open subset of $X$ is of second category in $X$). One version of the Baire category theorem implies that every complete metric space is a Baire space. The real line $\mathbb{R}$ with the usual Euclidean metric $\lvert x-y \lvert$ is a complete metric space, and hence is a Baire space. The space of irrational numbers $\mathbb{P}$ is also a complete metric space (not with the usual metric $\lvert x-y \lvert$ but with another suitable metric that generates the Euclidean topology on $\mathbb{P}$) and hence is also a Baire space. In this post, we show that there are subsets of the real line that are Baire space but not complete metric spaces. These sets are called Bernstein sets.

A Bernstein set, as discussed here, is a subset $B$ of the real line such that both $B$ and $\mathbb{R}-B$ intersect with every uncountable closed subset of the real line. We present an algorithm on how to generate such a set. Bernstein sets are not Lebesgue measurable. Our goal here is to show that Bernstein sets are Baire spaces but not weakly $\alpha$-favorable, and hence are spaces in which the Banach-Mazur game is undecidable.

Baire spaces are defined and discussed in this post. The Banach-Mazur game is discussed in this post. The algorithm of constructing Bernstein set is found in [2] (Theorem 5.3 in p. 23). Good references for basic terms are [1] and [3].
____________________________________________________________________________

In constructing Bernstein sets, we need the following lemmas.

Lemma 1
In the real line $\mathbb{R}$, any uncountable closed set has cardinality continuum.

Proof
In the real line, every uncountable subset of the real line has a limit point. In fact every uncountable subset of the real line contains at least one of its limit points (see The Lindelof property of the real line). Let $A \subset \mathbb{R}$ be an uncountable closed set. The set $A$ has to contain at least one of its limit point. As a result, at most countably many points of $A$ are not limit points of $A$. Take away these countably many points of $A$ that are not limit points of $A$ and call the remainder $A^*$. The set $A^*$ is still an uncountable closed set but with an additional property that every point of $A^*$ is a limit point of $A^*$. Such a set is called a perfect set. In Perfect sets and Cantor sets, II, we demonstrate a procedure for constructing a Cantor set out of any nonempty perfect set. Thus $A^*$ (and hence $A$) contains a Cantor set and has cardinality continuum. $\blacksquare$

Lemma 2
In the real line $\mathbb{R}$, there are continuum many uncountable closed subsets.

Proof
Let $\mathcal{B}$ be the set of all open intervals with rational endpoints, which is a countable set. The set $\mathcal{B}$ is a base for the usual topology on $\mathbb{R}$. Thus every nonempty open subset of the real line is the union of some subcollection of $\mathcal{B}$. So there are at most continuum many open sets in $\mathbb{R}$. Thus there are at most continuum many closed sets in $\mathbb{R}$. On the other hand, there are at least continuum many uncountable closed sets (e.g. $[-b,b]$ for $b \in \mathbb{R}$). Thus we can say that there are exactly continuum many uncountable closed subsets of the real line. $\blacksquare$

Constructing Bernstein Sets

Let $c$ denote the cardinality of the real line $\mathbb{R}$. By Lemma 2, there are only $c$ many uncountable closed subsets of the real line. So we can well order all uncountable closed subsets of $\mathbb{R}$ in a collection indexed by the ordinals less than $c$, say $\left\{F_\alpha: \alpha < c \right\}$. By Lemma 1, each $F_\alpha$ has cardinality $c$. Well order the real line $\mathbb{R}$. Let $\prec$ be this well ordering.

Based on the well ordering $\prec$, let $x_0$ and $y_0$ be the first two elements of $F_0$. Let $x_1$ and $y_1$ be the first two elements of $F_1$ (based on $\prec$) that are different from $x_0$ and $y_0$. Suppose that $\alpha < c$ and that for each $\beta < \alpha$, points $x_\beta$ and $y_\beta$ have been selected. Then $F_\alpha-\bigcup_{\beta<\alpha} \left\{x_\beta,y_\beta \right\}$ is nonempty since $F_\alpha$ has cardinality $c$ and only less than $c$ many points have been selected. Then let $x_\alpha$ and $y_\alpha$ be the first two points of $F_\alpha-\bigcup_{\beta<\alpha} \left\{x_\beta,y_\beta \right\}$ (according to $\prec$). Thus $x_\alpha$ and $y_\alpha$ can be chosen for each $\alpha.

Let $B=\left\{ x_\alpha: \alpha. Then $B$ is a Bernstein set. Note that $B$ meets every uncountable closed set $F_\alpha$ with the point $x_\alpha$ and the complement of $B$ meets every uncountable closed set $F_\alpha$ with the point $y_\alpha$.

The algorithm described here produces a unique Bernstein set that depends on the ordering of the uncountable closed sets $F_\alpha$ and the well ordering $\prec$ of $\mathbb{R}$.

____________________________________________________________________________

Key Lemmas

Baire spaces are defined and discussed in this previous post. Baire spaces can also be characterized using the Banach-Mazur game. The following lemmas establish that any Bernstein is a Baire space that is not weakly $\alpha$-favorable. Lemma 3 is applicable to all topological spaces. Lemmas 4, 5, 6, and 7 are specific to the real line.

Lemma 3
Let $Y$ be a topological space. Let $F \subset Y$ be a set of first category in $Y$. Then $Y-F$ contains a dense $G_\delta$ subset.

Proof
Let $F \subset Y$ be a set of first category in $Y$. Then $F=\bigcup \limits_{n=0}^\infty F_n$ where each $F_n$ is nowhere dense in $Y$. The set $X-\bigcup \limits_{n=0}^\infty \overline{F_n}$ is a dense $G_\delta$ set in the space $X$ and it is contained in the complement of $F$. We have:

$\displaystyle . \ \ \ \ \ X-\bigcup \limits_{n=0}^\infty \overline{F_n} \subset X-F$ $\blacksquare$

We now set up some notaions in preparation of proving Lemma 4 and Lemma 7. For any set $A \subset \mathbb{R}$, let $\text{int}(A)$ be the interior of the set $A$. Denote each positive integer $n$ by $n=\left\{0,1,\cdots,n-1 \right\}$. In particular, $2=\left\{0,1\right\}$. Let $2^{n}$ denote the collection of all functions $f: n \rightarrow 2$. Identify each $f \in 2^n$ by the sequence $f(0),f(1),\cdots,f(n-1)$. This identification makes notations in the proofs of Lemma 4 and Lemma 7 easier to follow. For example, for $f \in 2^n$, $I_f$ denotes a closed interval $I_{f(0),f(1),\cdots,f(n-1)}$. When we choose two disjoint subintervals of this interval, they are denoted by $I_{f,0}$ and $I_{f,1}$. For $f \in 2^n$, $f \upharpoonright 1$ refers to $f(0)$, $f \upharpoonright 2$ refers to the sequence $f(0),f(1)$, and $f \upharpoonright 3$ refers to the sequence $f(0),f(1),f(2)$ and so on.

The Greek letter $\omega$ denotes the first infinite ordinal. We equate it as the set of all nonnegative integers $\left\{0,1,2,\cdots \right\}$. Let $2^\omega$ denote the set of all functions from $\omega$ to $2=\left\{0,1 \right\}$.

Lemma 4
Let $W \subset \mathbb{R}$ be a dense $G_\delta$ set. Let $U$ be a nonempty open subset of $\mathbb{R}$. Then $W \cap U$ contains a Cantor set (hence an uncountable closed subset of the real line).

Proof
Let $W=\bigcap \limits_{n=0}^\infty O_n$ where each $O_n$ is an open and dense subset of $\mathbb{R}$. We describe how a Cantor set can be obtained from the open sets $O_n$. Take a closed interval $I_\varnothing=[a,b] \subset O_0 \cap U$. Let $C_0=I_\varnothing$. Then pick two disjoint closed intervals $I_{0} \subset O_1$ and $I_{1} \subset O_1$ such that they are subsets of the interior of $I_\varnothing$ and such that the lengths of both intervals are less than $2^{-1}$. Let $C_1=I_0 \cup I_1$.

At the $n^{th}$ step, suppose that all closed intervals $I_{f(0),f(1),\cdots,f(n-1)}$ (for all $f \in 2^n$) are chosen. For each such interval, we pick two disjoint closed intervals $I_{f,0}=I_{f(0),f(1),\cdots,f(n-1),0}$ and $I_{f,1}=I_{f(0),f(1),\cdots,f(n-1),1}$ such that each one is subset of $O_n$ and each one is subset of the interior of the previous closed interval $I_{f(0),f(1),\cdots,f(n-1)}$ and such that the lenght of each one is less than $2^{-n}$. Let $C_n$ be the union of $I_{f,0} \cup I_{f,1}$ over all $f \in 2^n$.

Then $C=\bigcap \limits_{j=0}^\infty C_j$ is a Cantor set that is contained in $W \cap U$. $\blacksquare$

Lemma 5
Let $X \subset \mathbb{R}$. If $X$ is not of second category in $\mathbb{R}$, then $\mathbb{R}-X$ contains an uncountable closed subset of $\mathbb{R}$.

Proof
Suppose $X$ is of first category in $\mathbb{R}$. By Lemma 3, the complement of $X$ contains a dense $G_\delta$ subset. By Lemma 4, the complement contains a Cantor set (hence an uncountable closed set). $\blacksquare$

Lemma 6
Let $X \subset \mathbb{R}$. If $X$ is not a Baire space, then $\mathbb{R}-X$ contains an uncountable closed subset of $\mathbb{R}$.

Proof
Suppose $X \subset \mathbb{R}$ is not a Baire space. Then there exists some open set $U \subset X$ such that $U$ is of first category in $X$. Let $U^*$ be an open subset of $\mathbb{R}$ such that $U^* \cap X=U$. We have $U=\bigcup \limits_{n=0}^\infty F_n$ where each $F_n$ is nowhere dense in $X$. It follows that each $F_n$ is nowhere dense in $\mathbb{R}$ too.

By Lemma 3, $\mathbb{R}-U$ contains $W$, a dense $G_\delta$ subset of $\mathbb{R}$. By Lemma 4, there is a Cantor set $C$ contained in $W \cap U^*$. This uncountable closed set $C$ is contained in $\mathbb{R}-X$. $\blacksquare$

Lemma 7
Let $X \subset \mathbb{R}$. Suppose that $X$ is a weakly $\alpha$-favorable space. If $X$ is dense in the open interval $(a,b)$, then there is an uncountable closed subset $C$ of $\mathbb{R}$ such that $C \subset X \cap (a,b)$.

Proof
Suppose $X$ is a weakly $\alpha$-favorable space. Let $\gamma$ be a winning strategy for player $\alpha$ in the Banach-Mazur game $BM(X,\beta)$. Let $(a,b)$ be an open interval in which $X$ is dense. We show that a Cantor set can be found inside $X \cap (a,b)$ by using the winning strategy $\gamma$.

Let $I_{-1}=[a,b]$. Let $t=b-a$. Let $U_{-1}^*=(a,b)$ and $U_{-1}=U^* \cap X$. We take $U_{-1}$ as the first move by the player $\beta$. Then the response made by $\alpha$ is $V_{-1}=\gamma(U_{-1})$. Let $C_{-1}=I_{-1}$.

Choose two disjoint closed intervals $I_0$ and $I_1$ that are subsets of the interior of $I_{-1}$ such that the lengths of these two intervals are less than $2^{-t}$ and such that $U_0^*=\text{int}(I_0)$ and $U_1^*=\text{int}(I_1)$ satisfy further properties, which are that $U_0=U_0^* \cap X \subset V_{-1}$ and $U_1=U_1^* \cap X \subset V_{-1}$ are open in $X$. Let $U_0$ and $U_1$ be two possible moves by player $\beta$ at the next stage. Then the two possible responses by $\alpha$ are $V_0=\gamma(U_{-1},U_0)$ and $V_1=\gamma(U_{-1},U_1)$. Let $C_1=I_0 \cup I_1$.

At the $n^{th}$ step, suppose that for each $f \in 2^n$, disjoint closed interval $I_f=I_{f(0),\cdots,f(n-1)}$ have been chosen. Then for each $f \in 2^n$, we choose two disjoint closed intervals $I_{f,0}$ and $I_{f,1}$, both subsets of the interior of $I_f$, such that the lengths are less than $2^{-(n+1) t}$, and:

• $U_{f,0}^*=\text{int}(I_{f,0})$ and $U_{f,1}^*=\text{int}(I_{f,1})$,
• $U_{f,0}=U_{f,0}^* \cap X$ and $U_{f,1}=U_{f,1}^* \cap X$ are open in $X$,
• $U_{f,0} \subset V_f$ and $U_{f,1} \subset V_f$

We take $U_{f,0}$ and $U_{f,1}$ as two possible new moves by player $\beta$ from the path $f \in 2^n$. Then let the following be the responses by player $\alpha$:

• $V_{f,0}=\gamma(U_{-1},U_{f \upharpoonright 1}, U_{f \upharpoonright 2}, \cdots,U_{f \upharpoonright (n-1)},U_f, U_{f,0})$
• $V_{f,1}=\gamma(U_{-1},U_{f \upharpoonright 1}, U_{f \upharpoonright 2}, \cdots,U_{f \upharpoonright (n-1)},U_f, U_{f,1})$

The remaining task in the $n^{th}$ induction step is to set $C_n=\bigcup \limits_{f \in 2^n} I_{f,0} \cup I_{f,1}$.

Let $C=\bigcap \limits_{n=-1}^\infty C_n$, which is a Cantor set, hence an uncountable subset of the real line. We claim that $C \subset X$.

Let $x \in C$. There there is some $g \in 2^\omega$ such that $\left\{ x \right\} = \bigcap \limits_{n=1}^\infty I_{g \upharpoonright n}$. The closed intervals $I_{g \upharpoonright n}$ are associated with a play of the Banach-Mazur game on $X$. Let the following sequence denote this play:

$\displaystyle (1) \ \ \ \ \ U_{-1},V_{-1},U_{g \upharpoonright 1},V_{g \upharpoonright 1},U_{g \upharpoonright 2},V_{g \upharpoonright 2},U_{g \upharpoonright 3},U_{g \upharpoonright 3}, \cdots$

Since the strategy $\gamma$ is a winning strategy for player $\alpha$, the intersection of the open sets in $(1)$ must be nonempty. Thus $\bigcap \limits_{n=1}^\infty V_{g \upharpoonright n} \ne \varnothing$.

Since the sets $V_{g \upharpoonright n} \subset I_{g \upharpoonright n}$, and since the lengths of $I_{g \upharpoonright n}$ go to zero, the intersection must have only one point, i.e., $\bigcap \limits_{n=1}^\infty V_{g \upharpoonright n} = \left\{ y \right\}$ for some $y \in X$. It also follows that $y=x$. Thus $x \in X$. We just completes the proof that $X$ contains an uncountable closed subset of the real line. $\blacksquare$

____________________________________________________________________________

Lemma 6 above establishes that any Bernstein set is a Baire space (if it isn’t, the complement would contain an uncountable closed set). Lemma 7 establishes that any Bernstein set is a topological space in which the player $\alpha$ has no winning strategy in the Banach-Mazur game (if player $\alpha$ always wins in a Bernstein set, it would contain an uncountable closed set). Thus any Bernstein set cannot be a weakly $\alpha$ favorable space. According to this previous post about the Banach-Mazur game, Baire spaces are characterized as the spaces in which the player $\beta$ has no winning strategy in the Banach-Mazur game. Thus any Bernstein set in a topological space in which the Banach-Mazur game is undecidable (i.e. both players in the Banach-Mazur game have no winning strategy).

One interesting observation about Lemma 6 and Lemma 7. Lemma 6 (as well as Lemma 5) indicates that the complement of a “thin” set contains a Cantor set. On the other hand, Lemma 7 indicates that a “thick” set contains a Cantor set (if it is dense in some open interval).

Reference

1. Engelking, R., General Topology, Revised and Completed edition, Heldermann Verlag, Berlin, 1989.
2. Oxtoby, J. C., Measure and Category, Graduate Texts in Mathematics, Springer-Verlag, New York, 1971.
3. Willard, S., General Topology, Addison-Wesley Publishing Company, 1970.

# A Question About The Rational Numbers

Let $\mathbb{R}$ be the real line and $\mathbb{Q}$ be the set of all rational numbers. Consider the following question:

___________________________________________________________________________________
Question

• For each nonnegative integer $n$, let $U_n$ be an open subset of $\mathbb{R}$ such that that $\mathbb{Q} \subset U_n$. The intersection $\bigcap \limits_{n=0}^\infty U_n$ is certainly nonempty since it contains $\mathbb{Q}$. Does this intersection necessarily contain some irrational numbers?

___________________________________________________________________________________

While taking a real analysis course, the above question was posted to the author of this blog by the professor. Indeed, the question is an excellent opening of the subject of category. We first discuss the Baire category theorem and then discuss the above question. A discussion of Baire spaces follow. For any notions not defined here and for detailed discussion of any terms discussed here, see [1] and [2].

In the above question, the set $\bigcap \limits_{n=0}^\infty U_n$ is a $G_\delta$ set since it is the intersection of countably many open sets. It is also dense in the real line $\mathbb{R}$ since it contains the rational numbers. So the question can be rephrased as: is the set of rational numbers $\mathbb{Q}$ a $G_\delta$ set? Can a dense $G_\delta$ set in the real line $\mathbb{R}$ be a “small” set such as $\mathbb{Q}$? The discussion below shows that $\mathbb{Q}$ is too “thin” to be a dense $G_\delta$ set. Put it another way, a dense $G_\delta$ subset of the real line is a “thick” set. First we present the Baire category theorem.
___________________________________________________________________________________

Baire Category Theorem

Let $X$ be a complete metric space. For each nonnegative integer $n$, let $O_n$ be an open subset of $X$ that is also dense in $X$. Then $\bigcap \limits_{n=0}^\infty O_n$ is dense in $X$.

Proof
Let $A=\bigcap \limits_{n=0}^\infty O_n$. Let $V_0$ be any nonempty open subset of $X$. We show that $V_0$ contains some point of $A$.

Since $O_0$ is dense in $X$, $V_0$ contains some point of $O_0$. Let $x_0$ be one such point and choose open set $V_1$ such that $x_0 \in V_1$ and $\overline{V_1} \subset V_0 \cap O_0 \subset V_0$ with the additional condition that the diameter of $\overline{V_1}$ is less than $\displaystyle \frac{1}{2^1}$.

Since $O_1$ is dense in $X$, $V_1$ contains some point of $O_1$. Let $x_1$ be one such point and choose open set $V_2$ such that $x_1 \in V_2$ and $\overline{V_2} \subset V_1 \cap O_1 \subset V_1$ with the additional condition that the diameter of $\overline{V_2}$ is less than $\displaystyle \frac{1}{2^2}$.

By continuing this inductive process, we obtain a nested sequence of open sets $V_n$ and a sequence of points $x_n$ such that $x_n \in V_n \subset \overline{V_n} \subset V_{n-1} \cap O_{n-1} \subset V_0$ for each $n$ and that the diameters of $\overline{V_n}$ converge to zero (according to some complete metric on $X$). Then the sequence of points $x_n$ is a Cauchy sequence. Since $X$ is a complete metric space, the sequence $x_n$ converges to a point $x \in X$.

We claim that $x \in V_0 \cap A$. To see this, note that for each $n$, $x_j \in \overline{V_n}$ for each $j \ge n$. Since $x$ is the sequential limit of $x_j$, $x \in \overline{V_n}$ for each $n$. It follows that $x \in O_n$ for each $n$ ($x \in A$) and $x \in V_0$. This completes the proof of Baire category theorem. $\blacksquare$

___________________________________________________________________________________

Discussion of the Above Question

For each nonnegative integer $n$, let $U_n$ be an open subset of $\mathbb{R}$ such that that $\mathbb{Q} \subset U_n$. We claim that the intersection $\bigcap \limits_{n=0}^\infty U_n$ contain some irrational numbers.

Suppose the intersection contains no irrational numbers, that is, $\mathbb{Q}=\bigcap \limits_{n=0}^\infty U_n$.

Let $\mathbb{Q}$ be enumerated by $\left\{r_0,r_1,r_2,\cdots \right\}$. For each $n$, let $G_n=\mathbb{R}-\left\{ r_n \right\}$. Then each $G_n$ is an open and dense set in $\mathbb{R}$. Note that the set of irrational numbers $\mathbb{P}=\bigcap \limits_{n=0}^\infty G_n$.

We then have countably many open and dense sets $U_0,U_1,U_2,\cdots,G_0,G_1,G_2,\cdots$ whose intersection is empty. Note that any point that belongs to all $U_n$ has to be a rational number and any point that belongs to all $G_n$ has to be an irrational number. On the other hand, the real line $\mathbb{R}$ with the usual metric is a complete metric space. By the Baire category theorem, the intersection of all $U_n$ and $G_n$ must be nonempty. Thus the intersection $\bigcap \limits_{n=0}^\infty U_n$ must contain more than rational numbers.

It follows that the set of rational numbers $\mathbb{Q}$ cannot be a $G_\delta$ set in $\mathbb{R}$. In fact, the discussion below will show that the in a complete metric space such as the real line, any dense $G_\delta$ set must be a “thick” set (see Theorem 3 below).
___________________________________________________________________________________

Baire Spaces

The version of the Baire category theorem discussed above involves complete metric spaces. However, the ideas behind the Baire category theorem are topological in nature. The following is the conclusion of the Baire category theorem:

$(*) \ \ \ \ X$ is a topological space such that for each countable family $\left\{U_0,U_1,U_2,\cdots \right\}$ of open and dense sets in $X$, the intersection $\bigcap \limits_{n=0}^\infty U_n$ is dense in $X$.

A Baire space is a topological space in which the condition $(*)$ holds. The Baire category theorem as stated above gives a sufficient condition for a topological space to be a Baire space. There are plenty of Baire spaces that are not complete metric spaces, in fact, not even metric spaces. The condition $(*)$ is a topological property. In order to delve deeper into this property, let’s look at some related notions.

Let $X$ be a topological space. A set $A \subset X$ is dense in $X$ if every open subset of $X$ contains a point of $A$ (i.e. $\overline{A}=X$). A set $A \subset X$ is nowhere dense in $X$ if for every open subset $U$ of $X$, there is some open set $V \subset U$ such that $V$ contains no point of $A$ (another way to describe this: $\overline{A}$ contains no interior point of $X$).

A set is dense if its points can be found in every nonempty open set. A set is nowhere dense if every nonempty open set has an open subset that misses it. For example, the set of integers $\mathbb{N}$ is nowhere dense in $\mathbb{R}$.

A set $A \subset X$ is of first category in $X$ if $A$ is the union of countably many nowhere dense sets in $X$. A set $A \subset X$ is of second category in $X$ if it is not of first category in $X$.

To make sense of these notions, the following observation is key:

$(**) \ \ \ \ F \subset X$ is nowhere dense in $X$ if and only if $X-\overline{F}$ is an open and dense set in $X$.

So in a Baire space, if you take away any countably many closed and nowhere dense sets (in other words, taking away a set of first category in $X$), there is a remainder (there are still points remaining) and the remainder is still dense in $X$. In thinking of sets of first category as “thin”, a Baire space is one that is considered “thick” or “fat” in that taking away a “thin” set still leaves a dense set.

A space $X$ is of second category in $X$ means that if you take away any countably many closed and nowhere dense sets in $X$, there are always points remaining. For a set $Y \subset X$, $Y$ is of second category in $X$ means that if you take away from $Y$ any countably many closed and nowhere dense sets in $X$, there are still points remaining in $Y$. A set of second category is “thick” in the sense that after taking away a “thin” set there are still points remaining.

For example, $\mathbb{N}$ is nowhere dense in $\mathbb{R}$ and thus of first category in $\mathbb{R}$. However, $\mathbb{N}$ is of second category in itself. In fact, $\mathbb{N}$ is a Baire space since it is a complete metric space (with the usual metric).

For example, $\mathbb{Q}$ is of first category in $\mathbb{R}$ since it is the union of countably many singleton sets ($\mathbb{Q}$ is also of first category in itself).

For example, let $T=[0,1] \cup (\mathbb{Q} \cap [2,3])$. The space $T$ is not a Baire space since after taking away the rational numbers in $[2,3]$, the remainder is no longer dense in $T$. However, $T$ is of second category in itself.

For example, any Cantor set defined in the real line is nowhere dense in $\mathbb{R}$. However, any Cantor set is of second category in itself (in fact a Baire space).

The following theorems summarize these concepts.

Theorem 1a
Let $X$ be a topological space. The following conditions are equivalent:

1. $X$ is of second category in itself.
2. The intersection of countably many dense open sets is nonempty.

Theorem 1b
Let $X$ be a topological space. Let $A \subset X$. The following conditions are equivalent:

1. The set $A$ is of second category in $X$.
2. The intersection of countably many dense open sets in $X$ must intersect $A$.

Theorem 2
Let $X$ be a topological space. The following conditions are equivalent:

1. $X$ is a Baire space, i.e., the intersection of countably many dense open sets is dense in $X$.
2. Every nonempty open subset of $X$ is of second category in $X$.

The above theorems can be verified by appealing to the relevant definitions, especially the observation $(**)$. Theorems 2 and 1a indicate that any Baire space is of second category in itself. The converse is not true (see the space $T=[0,1] \cup (\mathbb{Q} \cap [2,3])$ discussed above).

___________________________________________________________________________________

Dense G delta Subsets of a Baire Space

In answering the question stated at the beginning, we have shown that $\mathbb{Q}$ cannot be a $G_\delta$ set. Being a set of first category, $\mathbb{Q}$ cannot be a dense $G_\delta$ set. In fact, it can be shown that in a Baire space, any dense $G_\delta$ subset is also a Baire space.

Theorem 3
Let $X$ be a Baire space. Then any dense $G_\delta$ subset of $X$ is also a Baire space.

Proof
Let $Y=\bigcap \limits_{n=0}^\infty U_n$ where each $U_n$ is open and dense in $X$. We show that $Y$ is a Baire space. In light of Theorem 2, we show that every nonempty open set of $Y$ is of second category in $Y$.

Suppose that there is a nonempty open subset $U \subset Y$ such that $U$ is of first category in $Y$. Then $U=\bigcup \limits_{n=0}^\infty W_n$ where each $W_n$ is nowhere dense in $Y$. It can be shown that each $W_n$ is also nowhere dense in $X$.

Since $U$ is open in $Y$, there is an open set $U^* \subset X$ such that $U^* \cap Y=U$. Note that for each $n$, $F_n=X-U_n$ is closed and nowhere dense in $X$. Then we have:

$\displaystyle (1) \ \ \ \ \ U^*=\bigcup \limits_{n=0}^\infty (F_n \cap U^*) \cup \bigcup \limits_{n=0}^\infty W_n$

$(1)$ shows that $U^*$ is the union of countably many nowhere dense sets in $X$, contracting that every nonempty open subset of $X$ is of second category in $X$. Thus we can conclude that every nonempty open subset of $Y$ is of second category in $Y$. $\blacksquare$

Reference

1. Engelking, R., General Topology, Revised and Completed edition, 1989, Heldermann Verlag, Berlin.
2. Willard, S., General Topology, 1970, Addison-Wesley Publishing Company.

Revised July 3, 2019

# A note on basic set theory

This is a short note listing some basic facts on set theory and set theory notations, mostly about cardinality of sets. The discussion in this note is useful for proving theorems in topology and in many other areas. For more information on basic set theory, see [2].

Let $A$ and $B$ be sets. The cardinality of the set $A$ is denoted by $\lvert A \lvert$. A function $f:A \rightarrow B$ is said to be one-to-one (an injection) if for $x,y \in A$ with $x \ne y$, $f(x) \ne f(y)$. A function $f:A \rightarrow B$ is said to map $A$ onto $B$ (a surjection) if $B=\left\{f(x): x \in A\right\}$, i.e. the range of the function $f$ is $B$. If the function $f:A \rightarrow B$ is both an injection and a surjection, then $f$ is called a bijection, in which case, we say both sets have the same cardinality and we use the notation $\lvert A \lvert = \lvert B \lvert$. When the function $f:A \rightarrow B$, we denote this condition by $\lvert A \lvert \le \lvert B \lvert$. The Cantor–Bernstein–Schroeder theorem states that if $\lvert A \lvert \le \lvert B \lvert$ and $\lvert B \lvert \le \lvert A \lvert$ then $\lvert A \lvert = \lvert B \lvert$ (see 1.12 in [2]).

For the functions $f:X \rightarrow Y$ and $g:Y \rightarrow Z$, we define the function $g \circ f$ by $(g \circ f)(x)=g(f(x))$ for each $x \in X$. The function $g \circ f$ is denoted by $g \circ f:X \rightarrow Z$ and is called the composition of $g$ and $f$.

We use the notation $B^A$ to denote the set of all functions $f:A \rightarrow B$. It follows that if $\lvert A \lvert \le \lvert B \lvert$ then $\lvert A^C \lvert \le \lvert B^C \lvert$. To see this, suppose we have a one-to-one function $f:A \rightarrow B$. We define a one-to-one function $H: A^C \rightarrow B^C$ by $H(h)=f \circ h$ for each $h \in A^C$. Since $f:A \rightarrow B$, it follows that $H$ is one-to-one.

By $\omega$, we mean the first infinite ordinal, which can be viewed as the set of all nonnegative intergers. By $\omega_1$ we mean the first uncountable ordinal. The notation $2^\omega$ has dual use. With $2=\left\{0,1\right\}$, the set $2^\omega$ denotes all functions $f:\omega \rightarrow 2$. It can be shown that $2^\omega$ has the same cardinality as the real line $\mathbb{R}$ and the unit interval $[0,1]$ and the middle third Cantor set (see The Cantor set, I). Thus we also use $2^\omega$ to denote continuum, the cardinality of the real line.

If $\lvert A \lvert=2^\omega$, then the set $\lvert A^{\omega} \lvert=2^\omega$ where $A^{\omega}$ is the set of all functions from $\omega$ into $A$. Since $\omega_1$ is the first uncountable ordinal, we have $\omega_1 \le 2^\omega$. The Continuum Hypothesis states that $\omega_1 = 2^\omega$, i.e. the cardinality of the real line is the first uncountable cardinal number.

The union of $2^\omega$ many sets, each of which has cardinality $2^\omega$, has cardinality $2^\omega$. Furthermore, the union of $\le 2^\omega$ many sets, each of which has cardinality $\le 2^\omega$, has cardinality $\le 2^\omega$.

Reference

1. Kunen, K. Set Theory, An Introduction to Independence Proofs, 1980, Elsevier Science Publishing, New York.
2. Willard, S., General Topology, 1970, Addison-Wesley Publishing Company.

# Closed uncountable subsets of the real line

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.

# Perfect sets and Cantor sets, II

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 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 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 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 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, $p 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$.

# Perfect sets and Cantor sets, I

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

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

# The Cantor bus tour

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.

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