These problems are meant only to provide practice; they do not necessarily reflect the difficulty level of the problems in the exam. The actual exam problems are likely to be easier because of the time constrains.

1. Let $\mathcal{F}$ be a collection of some subsets of $\mathbb{R}^{k}$, and let $S=\bigcup_{A \in \mathcal{F}} A$ and $T=\bigcap_{A \in \mathcal{F}} A$. For each of the following statements, either give a proof or provide a counterexample.

(a) If $p$ is a limit point of $T$, then $p$ is a limit point of each $A \in \mathcal{F}$.

(b) If $p$ is a limit point of $S$, then $p$ is a limit point of at least one set $A \in \mathcal{F}$.

2. Consider the function $d: \mathbb{R}^{2} \times \mathbb{R}^{2} \rightarrow \mathbb{R}$ defined by the formula

$$

d(\mathbf{x}, \mathbf{y})=\max \left(\left|x_{1}-y_{1}\right|,\left|x_{2}-y_{2}\right|\right),

$$

where $\mathbf{x}=\left(x_{1}, x_{2}\right)$ and $\mathbf{y}=\left(y_{1}, y_{2}\right)$.

(a) Show that $d$ defines a metric on $\mathbb{R}^{2}$. This is called the Manhatten metric.

- Positive definiteness. Clearly $d(\mathbf{x}, \mathbf{y}) \geq 0$ for all $\mathbf{x}$ and $\mathbf{y}$. Suppose $d(\mathbf{x}, \mathbf{y})=0$. Then $\left|x_{1}-y_{1}\right|=0$ and $\left|x_{2}-y_{2}\right|=0$ or $x_{1}=y_{1}$ and $x_{2}=y_{2}$. So $d(\mathbf{x}, \mathbf{y})=0 \Longrightarrow$ $\mathbf{x}=\mathbf{y}$.
- Symmetry. Clearly $d(\mathbf{x}, \mathbf{y})=d(\mathbf{y}, \mathbf{x})$ since $|\cdot|$ is symmetric.
- Triangle inequality. It is enough to show the triangle inequality with $\mathbf{u}=$ $\left(u_{1}, u_{2}\right), \mathbf{v}=\left(v_{1}, v_{2}\right)$ and $\mathbf{0}=(0,0)$ ie. $$d(\mathbf{u}, \mathbf{v}) \leq d(\mathbf{u}, \mathbf{0})+d(\mathbf{v}, \mathbf{0}) $$ This is because if $\mathbf{x}, \mathbf{y}, \mathbf{z}$ are three points, then $d(\mathbf{x}, \mathbf{y})=d(\mathbf{x}-\mathbf{z}, \mathbf{y}-\mathbf{z}), d(\mathbf{x}, \mathbf{z})=$ $d(\mathbf{x}-\mathbf{z}, \mathbf{0})$ and $d(\mathbf{y}, \mathbf{z})=d(\mathbf{y}-\mathbf{z}, \mathbf{0})$. So then the above inequality applied to $\mathbf{u}=\mathbf{x}-\mathbf{z}$ and $\mathbf{v}=\mathbf{y}-\mathbf{z}$, we obtain $$ d(\mathbf{x}, \mathbf{y}) \leq d(\mathbf{x}, \mathbf{z})+d(\mathbf{y}, \mathbf{z}) . $$ Now we prove inequality (1). Note that $d(\mathbf{u}, \mathbf{0})=\max \left(\left|u_{1}\right|,\left|u_{2}\right|\right)$ and $d(\mathbf{v}, \mathbf{0})=$ $\max \left(\left|v_{1}\right|,\left|v_{2}\right|\right)$. In particular for $i=1,2,\left|u_{i}\right| \leq d(\mathbf{u}, \mathbf{0})$, and we have a similar inequality for coordinates of $\mathbf{v}$. By the usual triangle inequality for the absolute value, $$ \left|u_{1}-v_{1}\right| \leq\left|u_{1}\right|+\left|v_{1}\right| \leq d(\mathbf{u}, \mathbf{0})+d(\mathbf{v} \cdot \mathbf{0}) $$ and similarly $$ \left|u_{2}-v_{2}\right| \leq\left|u_{2}\right|+\left|v_{2}\right| \leq d(\mathbf{u}, \mathbf{0})+d(\mathbf{v} . \mathbf{0}) \text {. }

$$ Taking the max of both the above inequalities we obtain the inequality (1).

$$

B_{1}(\mathbf{0}):=\left\{\left(x_{1}, x_{2}\right)|| x_{1}|,| x_{2} \mid<1\right\} .

$$

This is clearly the open square with edges $x_{1}=-1, x_{1}=1, x_{2}=-1$ and $x_{2}=1$.

(c) Are closed and bounded sets compact with this new metric? If so, give a proof. If not, give an example of a closed and bounded set (in this new metric) which is not compact.

It follows that $F$ is closed with respect to $d$ if and only if it closed with respect to the Euclidean metric $d_{E}$.

Now let $K$ be a closed and bounded subset with respect to the metric $d$. And let $\left\{U_{\alpha}\right\}$ be an open cover where $U_{\alpha}$ is an open set with respect to the metric $d$. Then by the above arguments, $K$ is also a closed and bounded with respect to the Euclidean metric, and hence is compact with respect to the Euclidean metric. By the above each $U_{\alpha}$ is also an open set with respect to the metric $d_{E}$. So there exists $\alpha_{1}, \cdots, \alpha_{n}$ such that

$$

K \subset \bigcup_{k=1}^{n} U_{\alpha_{k}} .

$$

So we have managed to extract a finite sub-cover, and hence $K$ is compact even with respect to the metric $d$.

3. Let $\left\{a_{n}\right\}$ be a sequence of real numbers such that $\left|a_{n}\right| \leq 2$, and

$$

\left|a_{n+2}-a_{n+1}\right| \leq \frac{1}{8}\left|a_{n+1}^{2}-a_{n}^{2}\right|

$$

for all $n \geq 1$. Show that $a_{n}$ converges. Hint. Show that the sequence is Cauchy. You might have to use the fact that

$$

\sum_{k=0}^{\infty} \frac{1}{4^{k}}=\frac{4}{3} .

$$

$$

\left|a_{n+2}-a_{n+1}\right| \leq \frac{1}{8}\left|a_{n+1}^{2}-a_{n}^{2}\right|=\frac{1}{8}\left|a_{n+1}-a_{n}\right|\left|a_{n+1}+a_{n}\right| \leq \frac{1}{4}\left|a_{n+1}-a_{n}\right| .

$$

Inductively we can see that

$$

\left|a_{n+2}-a_{n+1}\right|<\frac{1}{4^{n}}\left|a_{2}-a_{1}\right|

$$

From this, it follows by triangle inequality that for any $n<m$,

$$

\begin{aligned}

\left|a_{m}-a_{n}\right| & \leq\left|a_{m}-a_{m-1}\right|+\left|a_{m-1}-a_{m-2}\right|+\cdots\left|a_{n+1}-a_{n}\right| \\

& \leq\left(\frac{1}{4^{m-2}}+\frac{1}{4^{m-3}}+\cdots \frac{1}{4^{n-1}}\right)\left|a_{2}-a_{1}\right| \\

& \leq 4^{-(n-1)}\left(\frac{1}{4^{m-n-1}}+\frac{1}{4^{m-n-2}}+\cdots 1\right)\left|a_{2}-a_{1}\right| \\

& \leq 4^{-(n-1)}\left|a_{2}-a_{1}\right| \sum_{k=0}^{\infty} \frac{1}{4^{k}} \\

&=4^{-(n-1)}\left|a_{2}-a_{1}\right| \frac{4}{3}

\end{aligned}

$$

Since $\left|a_{2}-a_{1}\right| \leq\left|a_{2}\right|+\left|a_{1}\right|<4$, we see that

$$

\left|a_{m}-a_{n}\right| \leq \frac{4^{-(n-3)}}{3} .

$$

Given $\varepsilon>0$, if we choose $N$ big enough so that $4^{-(N-3)}<3 \varepsilon$, then for any $n, m>N$ we will have $\left|a_{m}-a_{n}\right|<\varepsilon$, and so the sequence is Cauchy. Since $\mathbb{R}$ is complete, the sequence converges.

4. Let $2^{\mathbb{N}}$ denote the collection of subsets of $\mathbb{N}$. That is,

$$

2^{\mathbb{N}}=\{A \mid A \subset \mathbb{N}\} .

$$

Show that $2^{\mathbb{N}}$ is uncountable. Hint. Proceed by contradiction and use anx argument similar to Cantor diagonalization.

$$

A=\left\{k \in \mathbb{N} \mid k \notin A_{n}\right\} .

$$

We claim that $A \notin\left\{A_{1}, A_{2}, \cdots\right\}$. But this would be a contradiction since we are assuming that the list exhausts all possible subsets of $\mathbb{N}$. To see the claim, consider $A_{n}$. If $n \in A_{n}$, then $n \notin A$, and if $n \notin A_{n}$, then $n \in A$. So the set $A$ is not equal to $A_{n}$ for any $n \in \mathbb{N}$.

An alternate viewpoint. An alternative viewpoint is to think of subsets of $\mathbb{N}$ as an infinite string of 0 and 1 in the following way - For a subset $A \subset \mathbb{N}$ we associate the string $\left\{a_{n}\right\}_{n=1}^{\infty}$, where

$$

a_{n}=\left\{\begin{array}{ll}

1, & n \in A \\

0, & n \notin A

\end{array} .\right.

$$

For instance the empty set will correspond to a string of all zeroes and the set $\mathbb{N}$ will correspond to a string of all ones. The subset of even numbers will correspond to a string with zeroes in odd places and ones in even places, and so on. The proof that the set of all infinite binary strings is uncountable is exactly our Cantor diagonalization argument. To go over it once more - Suppose $\left\{A_{1}, A_{2}, \cdots, A_{k}, \cdots\right\}$ is an exhaustive list of all such strings with $A_{k}=\left\{a_{k n}\right\}_{n=1}^{\infty}$. Consider the string

$$

a_{n}= \begin{cases}1, & a_{n n}=0 \\ 0, & a_{n n}=1 .\end{cases}

$$

Then $A$ differs from $A_{n}$ in the $n^{t h}$ spot, and so $A$ is not in the list $\left\{A_{1}, \cdots\right\}$ but $A$ itself is an infinite string of zeroes and ones. Contradiction!

5. Let $A$ and $B$ be disjoint closed subset of a metric space $(X, d)$. Show that there exist disjoint open sets $U$ and $V$ such that $A \subseteq U$ and $B \subseteq V$. Hint. First show that there is an open set $U$ containing $A$ such that $\bar{U}$ and $B$ are disjoint.

Claim. $U \cap V=\phi$.

Proof Suppose $x \in U \cap V$. Then there exists a $p \in A$ and $q \in B$ such that $d(x, p)<r_{p}$ and $d(x, q)<r_{q}$. By triangle inequality

$$

d(p, q) \leq d(p, x)+d(q, x)<r_{p}+r_{q} .

$$

Now suppose $r_{p} \leq r_{q}$, then $d(p, q)<2 r_{q}$, and so $p \in B_{2 r_{q}}(q) \cap A$. But by choice this intersection is empty since $B_{2 r_{q}}(q) \subset A^{c}$. So a contradiction. The other case $r_{p} \geq r_{q}$ is similar.

6. Let $(X, d)$ be a complete metric space.

(a) Suppose $\left\{E_{n}\right\}$ is a decreasing (ie. $E_{n+1} \subset E_{n}$ for all $n$ ) sequence of non-empty, closed and bounded sets with

$$

\lim _{n \rightarrow 0} \operatorname{diam}\left(E_{n}\right)=0,

$$

where for any subset $E$, the diameter is defined as $\operatorname{diam}(E)=\sup _{x, y \in E} d(x, y)$. Show that $\bigcap_{n=1}^{\infty} E_{n}$ consists of exactly one point.

Claim-1. The intersection $\cap E_{n}$ is non-empty.

Proof. Pick a point $x_{n} \in E_{n}$. Since $\operatorname{diam}\left(\mathrm{E}_{\mathrm{n}}\right) \rightarrow 0$, for any $\varepsilon>0$, there exists an $N$ such that $\operatorname{diam}\left(\mathrm{E}_{\mathrm{N}}\right)<\varepsilon$. But then if $n, m>N$, since $E_{n}, E_{m} \subset E_{N}$, by the definition of diameter, and our choice of points, we must have that $d\left(x_{n}, x_{m}\right)<\varepsilon$. This shows that the sequence $\left\{x_{n}\right\}$ is Cauchy, and hence must converge $(X$ is complete) to some $p \in X$. We claim that $p$ lies in the intersection. To see this, note that for any $N$, $x_{n} \in E_{N}$ if $n>N$. And so $p$ is a limit point of a sequence of points $\left\{x_{n}\right\}_{n=N}^{\infty}$ in $E_{N}$, and hence must belong to $E_{N}$ since $E_{N}$ is closed. This shows that $p \in E_{N}$ for all $N$, and so $p \in \bigcap_{n=1}^{\infty} E_{n}$.

Claim-2. $p$ is the uniques such point.

Proof. If not, then there is some $q$ which also lies in the intersection. Fix an $\varepsilon>0$, and choose $N$ such that $\operatorname{diam}\left(\mathrm{E}_{\mathrm{N}}\right)<\varepsilon$. Then since $p, q \in \bigcap_{n=1}^{\infty} E_{n}$, they both belong to $E_{N}$ in particular. But then $d(p, q)<\operatorname{diam}\left(\mathrm{E}_{\mathrm{N}}\right)<\varepsilon$. So for any $\varepsilon>0, d(p, q)<\varepsilon$, and hence $d(p, q)=0$ which means that $p=q$.

(b) If $\left\{G_{k}\right\}$ is a sequence of dense open subsets of $\mathbb{R}^{k}$, show that $\bigcap_{k=1}^{\infty} G_{k}$ is non-empty. Hint. Find a shrinking sequence of neighborhoods $E_{n}$ such that $\bar{E}_{n} \subset G_{n}$ and apply part (a).

- $E_{1} \supseteq E_{2} \supset \cdots$

- $\bar{E}_{n} \subset G_{n}$.

- $\operatorname{diam}\left(\mathrm{E}_{\mathrm{n}}\right)<2^{-(\mathrm{n}-1)} \operatorname{diam}\left(\mathrm{E}_{1}\right)$ Since $\left\{\bar{E}_{n}\right\}$ is a decreasing sequence of closed sets with diameter converging to zero, by part(a) $\cap \bar{E}_{n}$ is non-empty. But $\cap \bar{E}_{n} \subset \cap G_{n}$, and so the latter is also non-empty.

(c) From the above part show directly that if $\mathbb{R}^{k}=\bigcup_{k=1}^{\infty} F_{k}$ for closed subsets $F_{k}$, then at least one of $F_{k}$ has a non-empty interior. Hint. Argue by contradiction by considering $G_{k}=F_{k}^{c}$.

- $G_{k}$ is open and dense.

- $\cap G_{k}=\mathbb{R}^{k}-\cup F_{k}=\phi$.

But this contradicts part(c). Hence at least one of $F_{k}$ has a non-empty interior.