%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% exercise set 3 - solutions %%% due september 21, 2009 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \documentclass{amsart} \usepackage{graphicx} \usepackage{amssymb} \usepackage{epstopdf} \usepackage{nicefrac} \DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png} % \input hw.sty \textwidth = 6 in \textheight = 8.5 in \oddsidemargin = 0.0 in \evensidemargin = 0.0 in \topmargin = 0.0 in \headheight = 0.0 in \headsep = 0.0 in \parskip = 6pt \parindent = 0.0in % \hoffset=-.7in % \voffset=-.7in \newcommand{\mN}{{\mathbb N}} \newcommand{\mQ}{{\mathbb Q}} \newcommand{\mR}{{\mathbb R}} \newcommand{\mZ}{{\mathbb Z}} \begin{document} \parskip=4pt \begin{center} Math 445, Fall 2009 \hfill Exercise Set \#3 \hfill Solutions \end{center} \bigskip {\bf 1.} [\#11, page 70] ~ Let $D_1$ and $D_2$ be metrics on a single space $M$. Which of the following are metrics on $M$: $D_1 + D_2$, $\max \{D_1 , D_2\}$, $\min \{D_1, D_2\}$? \proof In all three examples, the Non-degenerate and Symmetry conditions are essentially automatic. In building new metrics from old, it is always a question of whether the Triangle Inequality holds. Example 1) $D = D_1 + D_2$ : We have three things to check. \underline{Non-degenerate}: $D(x,y) = 0$ then both $D_1(x,y) = 0$ and $D_2(x,y) = 0$ so $x = y$ as both $D_1(x,y) \geq 0$ and $D_2(x,y) \geq 0$. Then $D_1$ (or use $D_2$) is a metric implies $x=y$. \underline{Symmetry}: $D(x,y) = D(y,x)$ as both $D_1(x,y) = D_1(y,x)$ and $D_2(x,y) = D_2(y,x)$. \underline{Triangle}: Use the triangle inequality for $D_1$ and $D_2$ \begin{eqnarray*} D(x,z) = D_1(x,z) + D_2(x,z) & \leq & \left( D_1(x,y) + D_1(y,z) \right) + \left( D_2(x,y) + D_2(y,z) \right) \\ & = & \left( D_1(x,y) + D_2(x,y) \right) + \left( D_1(y,z) + D_2(y,z) \right)\\ & = & D(x,y) + D(y,z) \end{eqnarray*} So $D = D_1 + D_2$ is a metric. \medskip Example 2) $D = \max \{D_1 , D_2\}$ : We have three things to check. \underline{Non-degenerate}: $D(x,y) = 0$ then $\max\{ D_1(x,y), D_2(x,y)\} = 0$ so both $D_1(x,y) = D_2(x,y) = 0$. Then $D_1$ (or use $D_2$) is a metric implies $x=y$. \underline{Symmetry}: $D(x,y) = \max \{D_1(x,y) , D_2(x,y)\} = \max \{D_1(y,x) , D_2(y,x)\} = D(y,x)$ as $D_1(x,y) = D_1(y,x)$ and $D_2(x,y) = D_2(y,x)$. \underline{Triangle}: We want to use the triangle inequality for $D_1$ and $D_2$ to show $$D(x,z) = \max\{ D_1(x,z), D_2(x,z)\} ~ \leq ~ \max\{ (D_1(x,y), D_2(x,y) \} + \max \{D_1(y,z), D_2(y,z)) \} ???$$ The strategy is to show that $D_1(x,z) \leq D(x,y) + D(y,z)$ and the same for $D_2(x,z)$. By the triangle inequality for $D_1$ $$D_1(x,z) \leq D_1(x,y) + D_1(y,z) \leq \max\{ (D_1(x,y), D_2(x,y) \} + \max \{D_1(y,z), D_2(y,z)) \}$$ because $ D_1(x,y) \leq \max\{ (D_1(x,y), D_2(x,y) \}$ and $ D_1(y,z) \leq \max\{ (D_1(y,z), D_2(y,z) \}$. Likewise, $$D_2(x,z) \leq D_2(x,y) + D_2(y,z) \leq \max\{ (D_1(x,y), D_2(x,y) \} + \max \{D_1(y,z), D_2(y,z)) \}$$ Since we have the same expression on the right hand side in both inequalities, we get $$ \max\{ D_1(x,z), D_2(x,z)\} ~ \leq ~ \max\{ (D_1(x,y), D_2(x,y) \} + \max \{D_1(y,z), D_2(y,z)) \}$$ So $D = \max \{D_1 , D_2\}$ is a metric. \medskip Example 3) $D = \min \{D_1 , D_2\}$ : Again, Non-degenerate and Symmetry are true. \underline{Non-degenerate}: $D(x,y) = \min\{ D_1(x,y), D_2(x,y)\} = 0$ implies either $D_1(x,y) = 0$ or $D_2(x,y) = 0$. Then $D_1(x,y) = 0$ or $D_2(x,y) = 0$ which implies $x=y$. \underline{Symmetry}: $D(x,y) = \min \{D_1(x,y) , D_2(x,y)\} = \min \{D_1(y,x) , D_2(y,x)\} = D(y,x)$ as $D_1(x,y) = D_1(y,x)$ and $D_2(x,y) = D_2(y,x)$. \underline{Triangle}: The proof of the triangle inequality above for the metric $D = \max \{D_1 , D_2\}$ suggests that for $D(x,y) = \min \{D_1(x,y) , D_2(x,y)\} $ we should look for an example where the two estimates for $D_1(x,z)$ and $D_2(x,z)$ are realized by the minima so combining them does not work. \vfill \eject Here is an example: Let $M = \mR^2$ be the $2$-plane, but give it the distance functions, stretched by $2$ along the $x$-axis in the first case, and the $y$-axis in the second. $$D_1(\vec{x}, \vec{y}) = \sqrt{ 4(x_1 -y_1)^2 + (x_2 - y_2)^2} \quad , \quad D_2(\vec{x}, \vec{y}) = \sqrt{ (x_1 -y_1)^2 + 4(x_2 - y_2)^2} $$ Consider the triangle inequality for the three points $\vec{x} = (1,0)$, $\vec{y} = (0,0)$ and $\vec{z} = (0,1)$. Then $$D_1(\vec{x}, \vec{y}) = 2 ~, ~ D_1(\vec{y}, \vec{z}) = 1 ~, ~ D_1(\vec{x}, \vec{z}) = \sqrt{4+4} = \sqrt{8}$$ $$D_2(\vec{x}, \vec{y}) = 1 ~, ~ D_2(\vec{y}, \vec{z}) = 2 ~, ~ D_2(\vec{x}, \vec{z}) = \sqrt{4+4} = \sqrt{8}$$ So $D(\vec{x}, \vec{z}) = \sqrt{8}$, but $D(\vec{x}, \vec{y}) = 1$ and $D(\vec{y}, \vec{z}) = 1$, so $\sqrt{8} \not\leq 1 + 1$. This is not a metric. \endproof \bigskip {\bf 2.} [\#14, page 71] ~ Let $M$ be a metric space in which the distance function assumes only the values $0,1,3$. Define $x \sim y$ to means $D(x,y) \leq 1$. Prove that $\sim$ is an equivalence relation on $M$. Show also that $\sim$ determines the metric $D$. \proof First we show this is an equivalence relation. a) For $x \in M$: $D(x,x) = 0 \leq 1~ \Longrightarrow ~ x \sim x$. b) For $x,y \in M$: $x \sim y ~ \Longleftrightarrow ~ D(x,y) \leq 1 ~ \Longleftrightarrow ~ D(y,x) \leq 1 ~ \Longleftrightarrow ~ y \sim x $ c) For $x,y,z \in M$: $x \sim y ~ \& ~ y \sim z ~ \Longrightarrow ~ D(x,y) \leq 1 ~ \& ~ D(y,z) \leq 1 ~ \Longrightarrow ~ D(x,z) \leq 2$. But $D(x,z) \leq 2$ implies that $D(x,z) \leq 1$ as the metric does not take the value $2$, hence $x \sim z$. \medskip Conversely, we define $D$ given $\sim$. First, set $D(x,x) = 0$ as this must be true for all metrics. Next, if $x \not\sim y$ then set $D(x,y) = 3$. Finally, if $x \ne y$ but $x \sim y$ then set $D(x,y) = 1$. Then $D$ is non-degenerate, as the only case when $D(x,y) = 0$ is for $x = y$. Symmetry, $D(x,y) = D(y,x)$, follows from symmetry of $\sim$. Finally, to show the Triangle Inequality for a triple of points $x,y,z \in M$, break it down into cases: $x \sim y \sim z$, $x \sim y \not\sim z$ and its permutations, and $x \not\sim y \not\sim z \not\sim z$. Then plug in and check. \endproof \bigskip {\bf 3.} [\#1, page 74] ~ Let $M, D$ be a metric space. Prove that: a) For every $x \in M$, the complement $V_x = M- \{x\}$ is open. [Points are closed.] b) For any set $X \subset M$, then $X$ is the intersection of open sets. [The problem is to find enough open sets. A finite number will not suffice, unless $X$ is itself open.] \proof a) We must show that $V_x = M- \{x\}$ is open. Let $y \in V_x$ then $x \ne y$ so $D(x,y) > 0$. Let $R = D(x,y)/2$. Then $x \not\in B(y,R)$ by definition, so $B(y,R) \subset V_x$. This shows that every point of $V_x$ contains an open ball neighborhood in $V_x$ which implies that $V_x$ is open. b) Let $X \subset M$, then we want to find open sets $U_{\alpha}$ such that $\displaystyle X = \bigcap ~ V_{\alpha}$. The hint in class was that for $V_x = M- \{x\}$ and $V_y = M- \{y\}$ then $V_x \cap V_y = M - \{x,y\}$. So, take the intersection of all open sets $V_z$ for $z \not\in X$, to get $\displaystyle X = \bigcap_{z \in M -X} ~ V_z $. \endproof \bigskip {\bf 4.} [\#2, page 74] ~ Let $x, y \in M$ be distinct points in a metric space $M, D$. Prove that there exists disjoint open sets $U, V \subset M$ with $x \in U$ and $y \in V$. \proof Given $x \ne y$ then $D(x,y) > 0$. Set $R = D(x,y)/2 > 0$. Then $B(x,R) \cap B(y,R) = \emptyset$. \endproof \bigskip {\bf 5.} [\#5, page 74] ~ Let $M = \mR$ be the real line, with the metric $D(x,y) = |x-y|$. Prove that there are no isolated points in $\mR$. [A point $x \in M$ is \emph{isolated} if there exists an open set $U$ such that $U \cap M = \{x\}$.] \proof Let $x \in \mR$ and let $U \subset \mR$ be an open set with $x \in U$. Then there exists some $\delta > 0$ such that $B(x,\delta) \subset U$ as $U$ is open. The set $B(x,\delta)$ is just the interval $(x-\delta, x+ \delta)$. Consider the open interval $(x, x+ \delta)$ then there exists a real number [or rational number, or irrational number] between $x$ and $x + \delta$, so $U$ contains some point besides $x$. [This also shows that no point in the rational numbers $\mQ$ is isolated, and ditto for the irrational numbers.] \endproof \bigskip {\bf 6.} [\#8, page 74] ~ Let $x$ be a point of as metric space $M$. Prove that the following two statements are equivalent: a) $x$ is not isolated. b) Every neighborhood of $x$ contains an infinite number of points of $M$. \proof First we show $a) \Longrightarrow b)$. Let $U \subset M$ be a neighborhood of $x$. Then there exists some $\delta > 0$ such that $B(x,\delta) \subset U$. Assuming that $x$ is not isolated, then the open ball $B(x,\delta)$ contains some point $y_1$ other than $x$. So $y_1 \in B(x,\delta) - \{x\}$. Let $\delta_1 = D(x, y_1) > 0$. Then the open ball $D(x,\delta_1)$ is an open neighborhood of $X$, and $y_1 \not\in B(x, \delta_1)$ by the choice of $\delta_1$. So there exists $y_2 \in B(x,\delta_1)$ with $y_2 \ne x$, and also $y_2 \ne y_1$. This gives an inductive procedure: Assume points $\{y_1, y_2, \ldots , y_n\}$ have been chosen, which satisfy: \begin{enumerate} \item $\delta_{\ell} = D(x,y_{\ell}) > 0$ for $1 \leq \ell \leq n$ \item $\delta > \delta_1 > \delta_2 > \cdots > \delta_n$ \end{enumerate} Then $\{y_1, \ldots , y_n \} \cap B(x, \delta_n) = \emptyset$ and $x$ not isolated implies there exists $y_{n+1} \in B(x, \delta_n) $ with $y_{n+1} \ne x$. Set $\delta_{n+1} = D(x, y_{n+1})$ and the induction proceeds. The collection $\{y_1, y_2, \ldots\} \subset B(x,\delta) \subset U$ is an infinite set of distinct points of $M$. \medskip Next we show $b) \Longrightarrow a)$. Let $U \subset M$ be any open neighborhood of $x$. Then by $b)$ it contains an infinite number of points, so contains some point of $M$ besides $x$. Thus, $x$ is not isloated. \endproof \vfill \eject {\bf 7.} [\#9, page 74] ~ Let $M$ be an infinite metric space. Prove that $M$ contains an open set $U$ such that both $U$ and its complement $M - U$ are infinite. \proof We consider two cases. Suppose that all points of $M$ are isolated. Then every point of $M$ is an open set, so any collection of points if open. Since $M$ is an infinite set, there is a countably infinite subset of distinct points, $\{x_1, x_2,x_3, \ldots\}$. Let $U = \{x_2,x_4, x_6, \ldots\}$ be the subset of all points in the list with even index. This is open, and the complement has an infinite number of points. The test case gives an idea - look for a countable sequence of disjoint non-empty open balls, instead of just isolated points, then take the union of the even balls in the sequence. Suppose that $M$ has a non-isolated point $x \in M$. Pick $\delta_0 > 0$, then the construction used above in the proof of Problem~6, $a) \Longrightarrow b)$, gives an infinite subset of distinct points $\{y_1, y_2, \ldots\} \subset B(x,\delta_0)$ whose distances $\delta_{\ell} = D(x, y_{\ell})$ satisfy $$\delta_0 > \delta_1 > \delta_2 > \cdots > \delta_n > \cdots $$ For each $n \geq 1$, let $\lambda_n = \min\{ (\delta_{n-1} - \delta_n) , (\delta_n - \delta_{n+1})\}$. This number is chosen so that $$B(y_n, \lambda_n) \cap \{y_1, y_2, \ldots\} = \{y_n\} ~ {\rm for ~ all} ~ n \geq 1$$ [Draw a picture - it follows by Triangle Inequality.] Each disk $B(y_n, \lambda_n)$ is an open subset of $M$, so the union of any collection of them is also an open set. Take $U$ to be the union of all the open balls with even index, $$U = B(y_2, \lambda_2) \cup B(y_4, \lambda_4) \cup \cdots \cup B(y_{2\ell}, \lambda_{2\ell}) \cup \cdots$$ This is open, and the complement contains the infinite set $\{y_1, y_3, \ldots, y_{2\ell -1}, \ldots \}$. \endproof \medskip \vfill \end{document}