Let $(X, d)$ be a [[Metric Space|metric space]] and $A, C \in \pow{X}$, then the **Hausdorff distance** $H_D$ between $A$ and $C$ is $ D_H(A, C) = \max\paren{\sup_{x \in A}\inf_{y \in C} d(x, y), \sup_{y \in C}\inf_{x \in A}d(x, y)} $ # Part A $ D_H(A, C) = \inf\bracs{r \ge 0: A \subseteq C_r, C \subseteq A_r} $ where $ A_r = \bigcup_{x \in A}B(x, r) $ *Proof*. Denote $ d_H(A, C) = \inf \bracs{r \ge 0: A \subseteq C_r, C \subseteq A_r} $ to differentiate the definitions. Let $r > D_H(A, C)$, then $ r > \sup_{x \in A} \inf_{y \in C}d(x, y) \quad r > \sup_{y \in C}\inf_{x \in A}d(x, y) $ meaning that $ \begin{align*} r &> \inf_{y \in C}d(x, y) \forall x \in A \\ r &> \inf_{x \in C}d(x, y) \forall y \in C \end{align*} $ so $ \begin{align*} \forall x \in A, \exists y \in C: d(x, y) &< r \Leftrightarrow x \in B(y, r)\\ \forall y \in C, \exists x \in A: d(x, y) &< r \Leftrightarrow y \in B(x, r) \end{align*} $ implying that $ A \subseteq C_r, C \subseteq A_r $ and $ r \in \bracs{r \ge 0: A \subseteq C_r, C \subseteq A_r} \forall r > D_H(A, C) $ which gives $ D_H(A, C) \ge \inf \bracs{r \ge 0: A \subseteq C_r, C \subseteq A_r} = d_H(A, C) $ $D_H$ cannot be strictly less than $d_H$, otherwise $d_H$ is not the infimum. Now let $r > d_H(A, C)$, then $A \subseteq C_r, C \subseteq A_r$ (otherwise $d_H$ is not the infimum). This means that $ \begin{align*} \forall x \in A, \exists y \in C: x \in B(y, r) \Leftrightarrow d(x, y) &< r \\ \forall y \in C, \exists x \in A: y \in B(x, r) \Leftrightarrow d(x, y) &< r \end{align*} $ and that $ \begin{align*} r &\ge \inf_{y \in C}d(x, y) \forall x \in A \\ r &\ge \inf_{x \in A}d(x, y) \forall y \in C \end{align*} $ so $ r \ge \sup_{x \in A} \inf_{y \in C}d(x, y) \quad r \ge \sup_{y \in C}\inf_{x \in A}d(x, y) $ and $r \ge D_H(A, C)$ ($D_H$ is a lower bound). Therefore $ D_H(A, C) \le \inf \bracs{r \ge 0: A \subseteq C_r, C \subseteq A_r} = d_H(A, C) $ # Part B Let $A = \bracs{0}$ and $C = (0, \infty)$, then $ \begin{align*} \sup_{y \in C}\inf_{x \in A}d(x, y) &= \sup \bracs{\inf_{x \in A}d(x, y): y \in C} \\ &= \sup \bracs{d(0, y): y \in (0, \infty)} \\ &= \sup \bracs{y: y \in (0, \infty)} \\ &= \sup (0, \infty) = \infty \end{align*} $ Let $A, C \subseteq \real$, then if $A, C$ are bounded, $D_H(A, C) < \infty$. Since $A, C$ are bounded, $ \exists M_A : B(0, M_A) \supseteq A \quad \exists M_C: B(0, M_C) \supseteq C $ Let $M = \max(M_A, M_C)$, then $B(0, M) \supseteq A, C$ and $ d(a, c) < d(a, 0) + d(0, c) < 2M \quad \forall a \in A, c \in C $ so we have $ \begin{align*} \sup_{x \in A}\inf_{y \in C} d(x, y) &\le \sup_{x \in A} 2M = 2M < \infty \\ \sup_{y \in C}\inf_{x \in A} d(x, y) &\le \sup_{y \in C} 2M = 2M < \infty \end{align*} $ and therefore $D_H(A, C) < \infty$. # Part C Let $A, C \subseteq X$, then $D_H(A, C) = 0 \Leftrightarrow \overline{A} = \overline{C}$. *Proof*. First suppose that $D_H(A, C) = 0$, then $ A \subseteq C_r, C \subseteq A_r \quad \forall r > 0 $ This means that $ \forall r > 0, B(a, r) \cap C \ne \emptyset, B(c, r) \cap A \ne \emptyset, \forall a \in A, c \in C $ therefore $A \subseteq \overline{C} \Rightarrow \overline{A} \subseteq \overline{C}$, $C \subseteq \overline{A} \Rightarrow \overline{C} \subseteq \overline{A}$. Now suppose that $\overline{A} = \overline{C}$. Then $ \forall r > 0, B(a, r) \cap C \ne \emptyset, B(c, r) \cap A \ne \emptyset, \forall a \in A, c \in C $ which means that $ A \subseteq C_r, C \subseteq A_r \quad \forall r > 0 $ therefore $D_H(A, C) = \inf(0, \infty) = 0$. # Part D Let $d(x, A) = \inf \bracs{d(x, a): a \in A}$, then $ d(x, C) \le d(x, A) + D_H(A, C) $ *Proof*. $ \begin{align*} d(x, C) &= \inf\bracs{d(x, c): c \in C} \\ &\le \inf\bracs{d(x, a) + d(a, c): c \in C} &\forall a \in A\\ &\le d(x, a) + d(a, C) &\forall a \in A \\ &\le d(x, a) \end{align*} $ a $ \begin{align*} d(x, A) + D_H(A, C) &= d(x, A) \\&+ \max\paren{\sup_{x \in A}\inf_{y \in C} d(x, y), \sup_{y \in C}\inf_{x \in A}d(x, y)} \\ &= d(x, A) + \max\paren{\sup_{a \in A}d(a, C), \sup_{c \in C}d(c, A)} \\ &\ge d(x, A) + \sup d(a, C) \\ &\ge d(x, A) + d(a, C) \quad \forall a \in A \\ \end{align*} $ Now we know that $ \forall \varepsilon > 0, \exists a \in A: d(x, A) \le d(x, a) < d(x, A) + \varepsilon $ which means that $\forall \varepsilon > 0, \exists a \in A:$ $ \begin{align*} d(x, a) + d(a, C) &< d(x, A) + d(a, C) + \varepsilon \\ d(x, a) + \inf\bracs{d(a, c): c \in C} &< d(x, A) + d(a, C) + \varepsilon \\ \inf\bracs{d(x, a) + d(a, c): c \in C} &< d(x, A) + d(a, C) + \varepsilon \\ \inf\bracs{d(x, c): c \in C} &< d(x, A) + d(a, C) + \varepsilon \\ d(x, C) &< d(x, A) + d(a, C) + \varepsilon \end{align*} $ Since $d(x, C) < d(x, A) + d(a, C) + \varepsilon$ for any $\varepsilon > 0$, we can conclude that $ d(x, C) \le d(x, A) + d(a, C) \le d(x, A) + D_H(A, C) $