\documentclass[11pt,letterpaper]{article}
\usepackage{amsmath,amsfonts}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{8.9in}
\setlength{\parskip}{0.4em}
\parindent0mm
\def\Q{\mathbb{Q}}
\def\R{\mathbb{R}}
\def\Z{\mathbb{Z}}
\def\C{\mathbb{C}}
\begin{document}
\begin{center}
{\bf \Large Math 112 Homework 2 Solutions}\medskip
\end{center}

{\bf Problem 1.} 

Given an integer $N$, let $E_N$ be the set of equations of the form 
$a_0z^n+a_1z^{n-1}+\cdots
+a_n=0$, where $n\ge 0$ is an integer, $a_0,\dots,a_n$ are integers (not
all zero), and $n+|a_0|+\cdots+|a_n|=N$.
For a given value of $n$, there exist only finitely many tuples
of integers $(a_0,\dots,a_n)$ such that $|a_0|+\cdots+|a_n|=N-n$
(because each $a_i$ can take at most $2(N-n)+1$ values). Allowing $n$ to
vary from $1$ to $N$, we get that $E_N$ is the union of $N$ finite sets,
and therefore a finite set.

Next, let $A_N\subset\mathbb{R}$ be the set of solutions to the equations
in $E_N$. Since an equation of degree $n$ has at most $n$ solutions, to each 
element of $E_N$ correspond at most $N$ elements of $A_N$; therefore, the
finiteness of $E_N$ implies that of $A_N$.

Observe that each set $A_N$ is contained in the set
of algebraic numbers. Conversely, let $z$ be an algebraic number,
satisfying an equation $a_0z^n+a_1z^{n-1}+\dots+a_n=0$, and let
$N=n+|a_0|+\dots+|a_n|$: then $z\in A_N$. Therefore the set of algebraic 
numbers is exactly $A=\bigcup_{N=1}^{\infty} A_N$.
Since $A$ is the union of countably many finite sets $A_N$, it is at most
countable. Moreover it is infinite (since $\Z\subset A$), thus $A$ is
countable.
\medskip

{\bf Problem 2.}

1) $d_1$ is not a metric because it violates the triangle inequality:
for example, $d_1(0,1)=|1-0|^2=1$, $d_1(1,2)=|2-1|^2=1$,
$d_1(0,2)=|2-0|^2=4>d_1(0,1)+d_1(1,2)$.

2) $d_2$ is not a metric because it does not satisfy the property that
$d(x,y)>0$ whenever $x\neq y$: for example, $d_2(-1,1)=|1-1|=0$.

3) $d_3$ is a metric because it satisfies the three axioms of Definition
2.15:

\ a) If $x\neq y$, then $|x-y|>0$, so $d_3(x,y)=\dfrac{|x-y|}{1+|x-y|}>0$.
Moreover $d_3(x,x)=0$.

\ b) Clearly $d_3(x,y)=d_3(y,x)$.

\ c) Let $x,y,z\in\R$, and let $\alpha=|x-y|$, $\beta=|y-z|$,
$\gamma=|x-z|$. By the triangle inequality for the usual distance we have
$\alpha+\beta\ge\gamma$. We get:
$$d_3(x,y)+d_3(y,z)=\dfrac{\alpha}{1+\alpha}+\dfrac{\beta}{1+\beta}\ge
\dfrac{\alpha}{1+\alpha+\beta}+\dfrac{\beta}{1+\alpha+\beta}=\dfrac{\alpha+
\beta}{1+\alpha+\beta}\ge \dfrac{\gamma}{1+\gamma}=d_3(x,z),$$
where in the last inequality we have used the fact that the function $t\mapsto
\dfrac{t}{1+t}$ is increasing.
\medskip

{\bf Problem 3.}

(a) We show that $d_\infty$ satisfies the three axioms of Definition 2.15:

\ a) If $p\neq q$ then there exists $i\in\{1,\dots,n\}$ such that $p_i\neq
q_i$, so $d_\infty(p,q)\ge |p_i-q_i|>0$. Moreover $d_\infty(p,p)=0$ clearly.

\ b) $d_\infty(q,p)=d_\infty(p,q)$ because $|q_i-p_i|=|p_i-q_i|$ $\forall i$.

\ c) Let $p,q,r\in\R^n$: then for every $i\in\{1,\dots,n\}$ we have
$|p_i-q_i|\le |p_i-r_i|+|r_i-q_i|\le d_\infty(p,r)+d_\infty(r,q)$. So
$d_\infty(p,r)+d_\infty(r,q)$ is an upper bound for
$\{|p_i-q_i|,\ i=1,\dots,n\}$. Therefore $d_\infty(p,r)+d_\infty(r,q)\ge
\sup\{|p_i-q_i|\}=d_\infty(p,q)$.
\medskip

(b) Assume $E$ is open in $(\R^n,d)$, and consider any point $p\in E$. 
By definition $E$ contains a neighborhood of $p$ for the metric $d$, 
i.e.\ we have $\{q\in\R^n,\ d(p,q)<r\}\subset E$ for some $r>0$. Consider 
a point $q\in\R^n$ such that $d_\infty(p,q)<n^{-1/2}r$: then we have
$|p_i-q_i|<n^{-1/2}r$ for all $i$, so that $d(p,q)=(\sum |p_i-q_i|^2)^{-1/2}
<r$, and therefore $q\in E$. It follows that $E$ contains the neighborhood
$\{q\in\R^n,\ d_\infty(p,q)<n^{-1/2}r\}$ of $p$ for the metric $d_\infty$.
Since $E$ contains a neighborhood of each of its points, it is an open
subset of $(\R^n,d_\infty)$.

Conversely, assume $E$ is open in $(\R^n,d_\infty)$, and consider $p\in E$.
By definition $E$ contains a neighborhood of the form $\{q\in\R^n,\ d_\infty
(p,q)<r\}$ for some $r>0$. Consider a point $q\in\R^n$ such that $d(p,q)<r$:
then $|p_i-q_i|<r$ for all $i$, so that $d_\infty(p,q)<r$ and therefore
$q\in E$. It follows that $E$ contains the neighborhood $\{q\in\R^n,
\ d(p,q)<r\}$ of $p$ for the metric $d$. Since $E$ contains a neighborhood
of each of its points, it is an open subset of $(\R^n,d)$.
\medskip

{\bf Problem 4.}

We verify the various axioms to show that $d$ is a metric:

-- by definition $d(p,q)=1>0$ if $p\neq q$, and $d(p,p)=0$; moreover
$d(p,q)=d(q,p)$. 

-- let $p,q,r\in X$: if $p=q$ then $d(p,q)=0\le d(p,r)+d(r,q)$. If $p\neq
q$ then either $r=p$, in which case $d(p,q)=d(r,q)\le d(p,r)+d(r,q)$, or
$r\neq p$, in which case $d(p,q)=1=d(p,r)\le d(p,r)+d(r,q)$.

Therefore $d$ is a metric. We now show that {\it every} subset $E\subset X$ 
is open and closed. 

-- let $E\subset X$, and let $p\in E$: by definition, we have
$\{q\in E,\ d(p,q)<\frac{1}{2}\}=\{p\}\subset E$, so $E$ contains a
neighborhood of $p$. Therefore $E$ is open.

-- let $E\subset X$, and let $p\in X$: by definition, the neighborhood
$\{q\in E,\ d(p,q)<\frac{1}{2}\}=\{p\}$ does not contain any point $q\neq
p$; therefore $p$ is not a limit point of $E$. So $E$ has no limit points,
and is therefore closed (every limit point belongs to $E$). 

(another way to prove that $E$ is closed is to observe that $E^c$ is open --
or vice versa).
\medskip

{\bf Problem 5.}

Let $x$ be a limit point of $E'$: we want to show that $x\in E'$, 
i.e.\ that $x$ is a limit point of $E$. Fix $r>0$: since $x$ is a limit
point of $E'$, there exists $y\in E'$ such 
that $y\neq x$ and $d(x,y)<\frac{r}{2}$. However, by definition $y$ is a
limit point of $E$, so there exists $z\in E$ such that $z\neq y$ and
$d(y,z)<d(x,y)<\frac{r}{2}$. By the triangle inequality we have $d(x,z)\le
d(x,y)+d(y,z)<\frac{r}{2}+\frac{r}{2}=r$. Moreover $x\neq z$ (because
$d(z,y)<d(x,y)$). Therefore every neighborhood of $x$ contains a point of
$E$ distinct from $x$, i.e.\ $x$ is a limit point of $E$, or equivalently
$x\in E'$. Since every limit point of $E'$ belongs to $E'$, we conclude that
$E'$ is closed.
\medskip

{\bf Problem 6.}

a) For every $i$, we have $A_i\subset \bigcup_{i=1}^n A_i=B_n\subset 
\bar{B}_n$. Therefore $\bar{B}_n$ is a closed set containing $A_i$,
and so by Theorem 2.27(c) in Rudin we get that $\bar{A}_i\subset\bar{B}_n$.
Since this holds for every $i$, we get that $\bigcup_{i=1}^n
\bar{A}_i\subset \bar{B}_n$. 

Conversely, since the sets $\bar{A}_i$ are
closed, by Theorem 2.24(d) the set $\bigcup_{i=1}^n \bar{A}_i$ is closed;
moreover, since $\bar{A}_i\supset A_i$ we get that $\bigcup_{i=1}^n
\bar{A}_i\supset B_n$. So applying again Theorem 2.27(c) we conclude that
$\bigcup_{i=1}^n\bar{A}_i\supset\bar{B}_n$, and therefore $\bigcup_{i=1}^n
\bar{A}_i=\bar{B}_n$.

b) Same argument as in a): since $A_i\subset B\subset \bar{B}$,
$\bar{B}$ is a closed set containing $A_i$ and therefore $\bar{A_i}\subset
\bar{B}$. Since this holds for every $i$, we get that
$\bigcup_{i=1}^\infty \bar{A}_i\subset \bar{B}$.

However the converse inclusion no longer holds in general: for example if
$A_i=[\frac{1}{i},1]\subset \R$, then $B=\bigcup_{i=1}^\infty A_i=(0,1]$,
so $\bar{B}=[0,1]$ while $\bigcup_{i=1}^\infty
\bar{A}_i=\bigcup_{i=1}^\infty A_i=(0,1]$.
\end{document}
