6
$\begingroup$

Here's Theorem 2.43 in the book Principles of Mathematical Analysis by Walter Rudin, 3rd edition:

Let $P$ be a non-empty perfect set in $\mathbb{R}^k$. Then $P$ is uncountable.

Here's the definition of a perfect set:

Let $(X,d)$ be a metric space, and let $P \subset X$. Then $P$ is perfect if it is closed (i.e. it contains all of its limit points) and every point of $P$ is also a limit point of $P$.

Now here's the proof Rudin gives:

Since $P$ has limit points, $P$ must be infinite. Suppose $P$ is countable, and denote the points of $P$ by $x_1, x_2, x_3, \ldots$. We shall construct a sequence $\{V_n\}$ of neighborhoods as follows:

Let $V_1$ be any neighborhood of $x_1$. If $V_1$ consists of all $y \in \mathbb{R}^k$ such that $\vert y - x_1 \vert < r$, the closure $\overline{V_1}$ of $V_1$ is the set of all $y \in \mathbb{R}^k$ such that $\vert y - x_1 \vert \leq r$.

Supose $V_n$ has been constructed, so that $V_n \cap P$ is not empty. Since every point of $P$ is a limit point of $P$, there is a neighborhood $V_{n+1}$ such that (i) $\overline{V_{n+1}} \subset V_n$, (ii) $x_n \not\in \overline{V_{n+1}}$, (iii) $V_{n+1} \cap P$ is not empty. By (iii), $V_{n+1}$ satisfies our induction hypothesis, and the construction can proceed.

Put $K_n = \overline{V_n} \cap P$. Since $\overline{V_n}$ is closed and bounded, $\overline{V_n}$ is compact. Since $x_n \not\in K_{n+1}$, no point of $P$ lies in $\cap_1^\infty K_n$. Since $K_n \subset P$, this implies that $\cap_1^\infty K_n$ is empty. But each $K_n$ is non-empty, by (iii), and $K_n \supset K_{n+1}$, by (i); this contradicts the Corollary to Theorem 2.36.

Finally, here's Theorem 2.36:

If $\{K_\alpha\}$ is a collection of compact subsets of a metric space $X$ such that the intersection of every finite subcollection of $\{K_\alpha\}$ is nonempty, then $\cap K_\alpha$ is nonempty.

And, here's the Corollary to Theorem 2.36:

If $\{K_n\}$ is a sequence of nonempty compact sets such that $K_n \supset K_{n+1}$ ($n=1, 2, 3, \ldots$), then $\cap_1^\infty K_n$ is not empty.

Now my question is, what exactly is the induction hypothesis that Rudin refers to in the proof? For $V_1$, he only says that it is any neighborhood of the point $x_1$.

What is the induction hypothesis? Please also proceed from $V_1$ to $V_2$, and then from $V_2$ to $V_3$ for the sake of illustration.

After reading David's comment, I've modified my proof as follows:

Since $P$ is nonempty, it has a point $a$, which is also a limit point of $P$ since $P$ is perfect. But no finite set in a metric space can have a limit point. So $P$ must be infinite. Suppose that $P$ is countable, and let's denote the points of $P$ by $x_1, x_2, x_3, \ldots$.

We shall construct a sequence $V_n$ of neighborhoods such that, for each $n \in \mathbb{N}$, the intersection $V_n \cap P$ is non-empty and $x_n \not\in V_{n+1}$.

Let $V_1$ be any neighborhood of $x_1$. Then we can show that if $$V_1 = \left\{ \ y \in \mathbb{R}^k \ \colon \ \vert y - x_1 \vert < \epsilon_1 \ \right\},$$ where $\epsilon_1$ is some positive real number, then the closure $\overline{V_1}$ of $V_1$ is given by $$ \overline{V_1} = \left\{ \ y \in \mathbb{R}^k \ \colon \ \vert y - x_1 \vert \leq \epsilon_1 \ \right\}.$$

Since $x_1$ is a limit point of set $P$, the nieghborhood $V_1$ of $x_1$ contains a point, say, $y_1$ of $P$ other than the point $x_1$ itself.

Now $y_1 \in V_1$ and $V_1$ is an open set in the metric space $\mathbb{R}^k$. So there is a positive real number $\delta_1$ such that $N_{\delta_1} (y_1) \subset V_1$, where $$N_{\delta_1} (y_1) \colon= \left\{ \ y \in \mathbb{R}^k \ \colon \ \vert y - y_1 \vert < \delta_1 \ \right\}.$$ Let $$\epsilon_2 \colon= \frac 1 2 \min \left( \delta_1, \vert x_1 - y_1 \vert \right).$$ Then $\epsilon_2 > 0$. Let $$V_2 \colon= \left\{ \ y \in \mathbb{R}^k \ \colon \ \vert y - y_1 \vert < \epsilon_2 \ \right\}.$$ Then $$\overline{V_2} = \left\{ \ y \in \mathbb{R}^k \ \colon \ \vert y - y_1 \vert \leq \epsilon_2 \ \right\}.$$ Thus, $V_2$ is a neighborhood such that $ y_1 \in V_2 \cap P$ so that $V_2 \cap P$ is non-empty, $\overline{V_2} \subset V_1$, but $x_1 \not\in \overline{V_2}$.

If $ y_1 \not= x_2$, then let $$\epsilon_3 \colon= \frac 1 2 \min \left( \epsilon_2 , \vert p - x_2 \vert \right).$$ Then $\epsilon_3 > 0$. Let $$V_3 \colon= \left\{ \ y \in \mathbb{R}^k \ \colon \ \vert y - y_1 \vert < \epsilon_3 \ \right\}.$$ Then $$\overline{V_3} = \left\{ \ y \in \mathbb{R}^k \ \colon \ \vert y - y_1 \vert \leq \epsilon_3 \ \right\}.$$ Thus, $y_1 \in V_3 \cap P$, and so $V_3 \cap P$ is non-empty; moreover, $\overline{V_3} \subset V_2$ and $x_2 \not\in \overline{V_3}$.

On the other hand, if $y_1 = x_2$, then since $y_1$ is a limit point of set $P$, and $V_2$ is a neighborhood of $y_1$, this neighborhood $V_2$ contains a point $y_2$, say, of $P$ other than the point $y_1 = x_2$ itself.

Now as $y_2 \in V_2$ and $V_2$ is an open set in $\mathbb{R}^k$, so there is some positive real number $\delta_2 > 0$ such that $$N_{\delta_2 } (y_2) \subset V_2.$$ So if we take $$\epsilon_3 \colon= \frac 1 2 \min \left( \delta_2 - \vert y_2 - x_2 \vert , \ \vert y_2 - x_2 \vert \right),$$ then $\epsilon_3 > 0$.

Let
$$V_3 \colon= \left\{ \ y \in \mathbb{R}^k \ \colon \ \vert y - y_2 \vert < \epsilon_3 \ \right\}.$$ Then $$\overline{V_3} \colon= \left\{ \ y \in \mathbb{R}^k \ \colon \ \vert y - y_2 \vert \leq \epsilon_3 \ \right\}.$$ Thus, $y_2 \in V_3 \cap P$ and so $V_3 \cap P$ is non-empty; moreover, $\overline{V_3} \subset V_2$, and $x_2 \not\in V_3$.

Thus, in either case we have obtained a neighborhood $V_3$ such that $V_3 \cap P$ is non-empty, $\overline{V_3} \subset V_2$, but $x_2 \not\in V_3$.

The step from $V_2$ to $V_3$ is redundant in the formal presentation of the proof, but this step perhaps more vividly illustrates how to proceed.

Now suppose that a neighborhood $V_n$ ($n= 3, 4, 5, \ldots$) has been constructed such that $x_{n-1} \not\in \overline{V_n}$, $\overline{V_n} \subset V_{n-1}$, and $V_n \cap P$ is non-empty. Let $$V_n \colon= \left\{ \ y \in \mathbb{R}^k \ \colon \ \vert y - p \vert < \epsilon \ \right\},$$ where $\epsilon$ is some positive real number and $p$ is some point in $\mathbb{R}^k$.

We now construct $V_{n+1}$ such that $V_{n+1} \cap P$ is non-empty, $\overline{V_{n+1}} \subset V_n$, and $x_n \not\in \overline{V_{n+1}}$.

Suppose that $q \in V_n \cap P$. As $q \in V_n$ and $V_n$ is open, there is some positive real number $\delta_n$ such that $$N_{\delta_n} (q) \subset V_n,$$ where $$N_{\delta_n} (q) \colon= \left\{ \ y \in \mathbb{R}^k \ \colon \ \vert y - q \vert < \delta_n \ \right\}.$$

If $q \not= x_n$, then let's take $$\epsilon_{n+1} \colon= \frac 1 2 \min \left( \delta_n , \vert q - x_n \vert \right).$$ So $\epsilon_{n+1} > 0$, and let $$V_{n+1} \colon= \left\{ \ y \in \mathbb{R}^k \ \colon \ \vert y - q \vert < \epsilon_{n+1} \ \right\}.$$ Then $$\overline{V_{n+1}} \colon= \left\{ \ y \in \mathbb{R}^k \ \colon \ \vert y - q \vert \leq \epsilon_{n+1} \ \right\}.$$

Thus, $V_{n+1}$ is a neighborhood such that $q \in V_{n+1} \cap P$ so that $V_{n+1} \cap P$ is non-empty, $\overline{V_{n+1}} \subset V_n$, and $x_n \not\in \overline{V_{n+1}}$.

On the contrary, if $q = x_n$, then since $q$ is a limit point of $P$, the neighborhood $N_{\delta_n} (q)$ contains a point $b$, say, of $P$ other than the point $q = x_n$ itself.

Now if we take $$\epsilon_{n+1} \colon= \frac 1 2 \min \left( \delta_n - \vert b - x_n \vert, \ \vert b - x_n \vert \right),$$ then $\epsilon_{n+1} > 0$. Let $$V_{n+1} \colon= \left\{ \ y \in \mathbb{R}^k \ \colon \ \vert y - b \vert < \epsilon_{n+1} \ \right\}.$$ Then $$\overline{V_{n+1}} = \left\{ \ y \in \mathbb{R}^k \ \colon \ \vert y - b \vert = \epsilon_{n+1} \ \right\}.$$ So, $b \in V_{n+1} \cap P$, which implies that $V_{n+1} \cap P$ is non-empty, $\overline{V_{n+1}} \subset V_n$, and $x_n \not\in \overline{V_{n+1}}$.

Thus, from $V_n$, in either case, we have constructed a neighborhood $V_{n+1}$ such that $V_{n+1} \cap P$ is non-empty, $\overline{V_{n+1}} \subset V_n$, but $x_n \not\in \overline{V_{n+1}}$.

Thus, we have inductively obtained a sequence $\{V_n\}_{n \in \mathbb{N}}$ of neighborhoods such that, for each $n \in \mathbb{N}$, the intersection $V_n \cap P$ is non-empty, $\overline{V_{n+1}} \subset V_n$, and $x_n \not\in \overline{V_{n+1}}$.

Put $K_n \colon= \overline{V_n} \cap P$ for each $n \in \mathbb{N}$.

Let $n \in \mathbb{N}$ be arbitrary. Now $\overline{V_n}$, being a closed and bounded subset of $\mathbb{R}^k$, is compact. Moreover, as both $P$ and $\overline{V_n}$ are closed, so is $K_n$. Thus, $K_n$, being a closed subset of the compact set $\overline{V_n}$, is also compact. Since $V_n \cap P$ is non-empty, so $K_n$ is also non-empty. Moreover, as $$\overline{V_{n+1}} \subset V_n \subset \overline{V_n},$$ so we have $K_{n+1} \subset K_n$. Finally, as $$P = \left\{ \ x_1, x_2, x_3, \ldots \ \right\}$$ and as $x_n \not\in \overline{V_{n+1}}$, so $x_n \not\in K_{n+1}$ and hence $$x_n \not\in K_1 \cap K_2 \cap K_3 \cap \ldots,$$ which implies that this intersection is empty.

Let $m_1, m_2, \ldots, m_r \in \mathbb{N}$, and let's take $$m \colon= \max \left( m_1, \ldots, m_r \right).$$ Then $$K_{m_1} \cap \ldots \cap K_{m_r} = K_m,$$ which is non-empty.

Thus, $\{K_n\}_{n\in\mathbb{N}}$ is a sequence of non-empty compact sets in the metric space $\mathbb{R}^k$ such that the intersection of any finitely many of these sets is non-empty but the intersection $\cap_{n \in \mathbb{N}} K_n$ is empty.

But this cannot hold in any metric space, by Theorem 2.36 in Rudin. So our suppose that $P$ is a non-empty perfect set in $\mathbb{R}^k$ and $P$ is also countable is wrong. Hence Theorem 2.43 in Rudin holds.

Is the above proof correct?

If so, is the presentation clear enough (or any clearer than Rudin's presentation)?

Where does this proof need improvement?

$\endgroup$
  • $\begingroup$ Please change "\oiverline" to "\overline". $\endgroup$ – robit Feb 5 '16 at 5:53
  • $\begingroup$ In your statement of the Corollary (last highlighted result), surely you mean $K_{n+1}\subset K_n$. You also quote the result in the last line of Rudin's proof, and you have it reversed there too. This might just interfere with your understanding of the induction — anyway, it can't help. $\endgroup$ – BrianO Feb 5 '16 at 5:54
  • $\begingroup$ @robit I've made some corrections to my post. Please have a look now. $\endgroup$ – Saaqib Mahmood Feb 5 '16 at 6:38
  • $\begingroup$ @BrianO please have a look at my post now. $\endgroup$ – Saaqib Mahmood Feb 5 '16 at 6:40
  • 1
    $\begingroup$ Your argument looks correct but can be simplified. First, I don't see the point of having two cases. Simply choose $q$ (or $y_{n+1}$) immediately to be a point in $V_n \cap P$ that is not $x_n$, after proving that such a point exists. Second, you don't need the argument with the maximum $m$ of a set of indices if you use the corollary to Theorem 2.36 rather than the theorem itself. Also, if you really want to improve on Rudin's presentation, don't talk about $V_2$ and $V_3$, although you probably know that. $\endgroup$ – David Feb 6 '16 at 9:29
1
$\begingroup$

I don't think this is actually a proof by induction, but rather a definition by induction of a sequence of open balls $V_n$ that have nonempty intersection with $P$.

The facts that are needed (once the sequence has been constructed) about the sets $V_n$ are read directly from the inductive step of the construction and do not need to be proved by induction.

However, the definition of $V_{n+1}$ would not make sense if it was not already known that $V_n \cap P \ne \varnothing$. Therefore it must be verified that $V_{n+1} \cap P \ne \varnothing$ in order for the construction to continue. (The verification is trivial because this results from (iii) in the choice of $V_{n+1}$.) This is what Rudin refers to as the "induction hypothesis."

On the other hand, points (i) and (ii) being true at step $n$ are not needed in order for the construction to continue at step $n+1$.

$\endgroup$
  • $\begingroup$ can you please have a look at my question now? I've added some detail. $\endgroup$ – Saaqib Mahmood Feb 5 '16 at 18:52
1
$\begingroup$

The idea of the whole process is to embed an uncountable set $2^\mathbb{N}$ i.e. the set of all binary functions into the set. Normally you do this by embedding a complete binary tree $2^{<\omega}$ (the logician's convention $\omega$ is the same as $\mathbb{N}$, the tree consists of finite binary strings, think of this as a finite approximation to the actual function) into it.

The inductive process of doing this is string $\sigma\in 2^{<\omega}$ suppose you already have an infinite open set $B_{\sigma}\subset P$. We want to define $B_{\sigma^\frown 0}$ and $B_{\sigma^\frown 1}$ such that each set is open non-empty and has closure contained in $B_{\sigma}$ completely. But this is easy to achieve, say pick two points in $B_\sigma$, and use two open sets (whose closures are contained in $B_\sigma$) to separate them. These two sets are infinite since we assume the set is perfect so as a result it has no isolated points.

The final embedding is defined by $f: 2^\omega\to P$ by $f(g)=\bigcap_{g\restriction n} B_{g\restriction n}$, non-emptiness comes from completeness of the metric (you might want to define these $B_\sigma$'s such that their diameters are shrinking so each intersection ends up with only one element).

The same proof works for any perfect subset of a complete metric space.

$\endgroup$
  • $\begingroup$ Very nice. I prefer the constructive proof of this result, and you explain it well. $\endgroup$ – BrianO Feb 5 '16 at 6:44
  • $\begingroup$ @Jing Zhand thanks for taking the time answer my question, my knowledge of mathematical logic is very limited indeed! So can you please have a look at my question now that I've added some detail and see if what I've done so far is correct? $\endgroup$ – Saaqib Mahmood Feb 5 '16 at 18:54
  • $\begingroup$ Jing Zhang can you please have a look at my question now and comment on my proof? $\endgroup$ – Saaqib Mahmood Feb 6 '16 at 10:28
1
$\begingroup$

I found the proof above verbose to the point of illegibility. Here is a more concise proof that constructs $V_{n+1}$ as the neighborhood of a point $p_{n+1} \not = x_n$.

Proof of Baby Rudin Theorem 2.43

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.