How to prove the triangle inequality for this metric space

Question

Let $X = \prod_{k=1}^\infty \{0,1\}$ which can be viewed as the set of all sequences of binary digits. For $f,g \in X$, with $f \neq g$, define $m(f, g) = \min\{k : f(k) \neq g(k)\}$ and define $d : X \times X \to \mathbb{R}$ by

$$d(f, g) = \begin{cases}2^{-m(f,g)} & \text{if } f \neq g \\ 0 & \text{if }f = g.\end{cases}$$

The first three axioms have been given I imagine the first starting point is to prove that

$$m(a,c) \ge \min\{m(a,b), m(b,c)\}.$$

Followed by:

For $f \in X$, $n \in \mathbb{N}$, prove that $B(f, 2^{-n})$ consists of all $g \in X$ for which $$f(1) = g(1), f(2) = g(2), \ldots, \text{ and }f(n) = g(n).$$

This I think you must use the previous fact that $d(f,g) = 2^{-m(f,g)}$.

Followed by:

Show that for all $f \in X$, $r > 0$, either $B'(f,r) = B(f,r)$ or $B'(f,r) = B(f,2r)$.

This I believe must be a continuity using open sets problem.

Answer 1

Suppose $f \ne g \ne h \ne f.$ Let $a=m(f,g),\,b=m(g,h), \,c=m(f,h).$

Suppose $d(f,g)+d(g,h)<d(f,h).$

Then $ 2^{-a}+2^{-b}<2^{-c},$ which implies $(\,c<a \land c<b\,). $ But then $$ f(c)=g(c)\quad (\text { as }c<a=m(f,g)\,)$$ $$ \text {and } \quad g(c)=h(c)\quad (\text { as } c<b=m(g,h)\,)$$ so $f(c)=h(c),$ contrary to the def'n of $c=m(f,h).$ Contradiction.

Answer 2

If $a(i)$ agrees with $b(i)$ for all $i = 1, \ldots, m(a, b) - 1$. Similarly, $b(i)$ agrees with $c(i)$ for all $i = 1, \ldots, m(b, c) - 1$. So, we have $a(i) = b(i) = c(i)$ for all $i = 1, \ldots, k$, where $k = \min \{m(a, b), m(b, c)\} - 1$, as $k$ is a number smaller than both $m(a, b) - 1$ and $m(b, c) - 1$. Therefore, $m(a, c)$, the first $i$ such that $a(i) \neq c(i)$, must be at least $k + 1$. That is, $$m(a, c) \ge \min\{m(a, b), m(b, c)\}.$$

Thus, excluding the easy cases where $a, b, c$ are not pairwise distinct, \begin{align*} d(a, b) + d(b, c) &= 2^{-m(a, b)} + 2^{-m(b, c)} \\ &= 2^{-\max\{m(a, b), m(b, c)\}} + 2^{-\min\{m(a, b), (b, c)\}} \\ &\ge 2^{-\min\{m(a, b), (b, c)\}} \\ &\ge 2^{-m(a, c)} = d(a, c). \end{align*}

---

If $g \in B(f, 2^{-n})$, then either $f = g$ (in which case, the result is trivially true), or $$2^{-n} > d(f, g) = 2^{-m(a, b)} \implies m(a, b) > n.$$ So, the first point at which $f$ and $g$ disagree occurs past $n$, i.e. $f(i) = g(i)$ for $i = 1, \ldots, n$.

---

Note that the distance function $d(f, g)$ only takes countably many values: $$0, \frac{1}{2}, \frac{1}{4}, \ldots, \frac{1}{2^n}, \ldots$$ When $r$ is between these values, the ball $B(f; r)$ will not grow or shrink when you vary $r$ by a small amount. For example, for any $f \in X$, $$B\left(f, \frac{1}{3}\right) = B\left(f, \frac{1}{2}\right) = B'\left(f, \frac{1}{4}\right),$$ simply because a point that at most $\frac{1}{3}$ distance away from $f$, basically only rules out their distances being $\frac{1}{2}$.

This might give you an idea about how to go about attacking this third problem. I'll let you think about it. Let me know via comment if you need further help.

Answer 3

For any $a\in X$ and radius $r$, the closure of the open ball of radius $r$ around $a$ is the closed ball of radius $r$.

For any two distinct points $a,b$ in the space and any positive $\epsilon$, there is a point $c$ within $\epsilon$ of $b$, and closer to $a$ than $b$ is. That is, for every $a\neq b$ and $\epsilon\gt 0$, there is $c$ with $d(c,b)<\epsilon$ and $d(a,c)<d(a,b)$.

Proof. If the closed ball property holds, then fix any $a,b$ with $r=d(a,b)$. Since the closure of $B$ includes $b$, the second property follows. Conversely, if the second property holds, then if $r=d(a,b)$, then the property ensures that $b$ is in the closure of $B$, and so the closure of the open ball includes the closed ball