Question on the Proof to the Pseudometrization Lemma for (Quasi) Uniform Spaces

I am reading the proof to the following theorem from Cobzas "Functional Analysis in Asymmetric Normed Spaces" (this also appears in Kelley's General Topology), and there is a step of the proof I am having a hard time justifying:

$$\mathbf{ Definition}$$: If $$X$$ is a nonempty set, say a map $$d: X \times X \rightarrow [0, \infty)$$ is a quasi-pseudometric if it satisfies the triangle inequality and $$d(x,x)=0$$ for all $$x \in X$$.

$$\mathbf{ Theorem}$$: Let $$X$$ be a nonempty set, and let $$(U_n)_n$$ be a sequence of nonempty subsets of $$X \times X$$ such that $$U_0= X \times X$$, and $$U_{n+1} \circ U_{n+1} \circ U_{n+1} \subseteq U_n$$ for every $$n$$. Suppose further that each $$U_n$$ contains the diagonal $$\triangle$$. Then, there is a quasi-pseudometric $$d$$ on $$X$$ such that for every $$n$$ $$U_{n+1} \subseteq \{(x,y) | d(x,y) < 2^{-n} \} \subseteq U_n.$$ Moreover, if the $$U_n$$ are assumed to be symmetric, $$d$$ can be taken to be a pseudometric.

For convenience, I replicate the argument (omitting some details and adding some details where they were omitted in the argument in Cobzas) up to the step I am having trouble justifying.

Partial proof. One immediately observes $$U_{n+1} \subseteq U_n$$ for all $$n$$. Put $$f:X \times X \rightarrow [0, \infty), (x,y) \mapsto 2^{-n}$$ if $$(x,y) \in U_n \setminus U_{n+1}$$, and $$(x,y) \mapsto 0$$ if $$(x,y) \in \bigcap_k U_k$$. Define $$d: X \times X \rightarrow [0, \infty)$$, $$d(x,y) = \inf \sum_{i=0}^n f(x_i, x_{i+1}),$$ where the infimum is taken over all finite sequences $$(x_j)_{j=0, \ldots, n+1}$$ with $$x=x_0, x_{n+1}=y$$. Then, it is readily seen $$d$$ is a quasi-pseudometric (give yourself an epsilon of room to prove the triangle inequality, coining Tao's phrase). By considering sequences of length two, we have $$d(x,y) \leq f(x,y)$$ for every $$x,y$$. Moreover, one verifies $$f(x,y) \leq 2^{-l}$$ if and only if $$(x,y) \in U_l$$. We have the following claim:

$$\mathbf{Claim}$$: For every finite sequence $$(x_j)_{j=0, \ldots, n+1}$$ in $$X$$, we have $$f(x_0, x_{n+1}) \leq 2 \sum_{i=0}^{n} f(x_i, x_{i+1}).$$ The proof is by induction on $$n$$. The base case is trivial, and suppose the claim holds for $$0 \leq m . Put $$a=\sum_{i=0}^n f(x_i, x_{i+1})$$. We make two reductions: we assume $$a \neq 0$$ and that $$f(x_i, x_{i+1}) \neq a$$ for any $$0 \leq i \leq n$$.

Indeed, let us prove the claim for $$a=0$$. In this case, $$f(x_i, x_{i+1})=0$$ for every $$0 \leq i \leq n$$, so that $$(x_i, x_{i+1}) \in \bigcap_k U_k$$. By induction hypothesis, $$f(x_0, x_n) \leq 2 \sum_{i=0}^{n-1} f(x_i, x_{i+1}) = 0.$$ Moreover, $$f(x_n, x_{n+1})=0$$. If $$f(x_0, x_{n+1})$$ is nonzero - say, $$f(x_0, x_{n+1}) = 2^{-l}$$ for some $$l$$ - then $$(x_0, x_{n+1}) \in U_l \setminus U_{l+1}$$. But $$(x_0, x_n), (x_n, x_{n+1}) \in U_{l+2}$$ since they lie in every $$U_k$$; thus $$(x_0, x_{n+1}) \in U_{l+2}^2 \subseteq U_{l+2}^3 \subseteq U_{l+1}$$. This is a contradiction, so $$f(x_0, x_{n+1})=0$$.

The case when $$f(x_i, x_{i+1})=a$$ for some $$0 \leq i \leq n$$ is proven using a similar technique.

Thus it is safe to make the reductions mentioned above. Now here is the part of the proof I am having trouble justifying:

let $$k$$ be the greatest integer between $$0$$ and $$n$$ such that $$\sum_{i=0}^k f(x_i, x_{i+1}) \leq a/2$$. My question then is: why should there exist some $$0 \leq l < n$$ such that $$\sum_{i=0}^l f(x_i, x_{i+1}) \leq a/2$$? I was thinking it may have to do with the reduction that $$f(x_i, x_{i+1}) \neq a$$ for every $$i$$, though I am not sure how to deduce the existence of such an $$l$$ from this. (The reduction $$a \neq 0$$ is used later in the proof to take some $$m$$ such that $$2^{-m} \leq a$$).

Thanks for taking the time to read the question.

• I think it has to do with the fact that all values of $f$ are of the form $\frac{1}{2^n}$.. – Henno Brandsma Apr 1 at 5:57
• (Comment part 1) I suspect it does too, though I'm not sure how to fully flesh out the argument. Let us say $f(x_i, x_{i+1})= 2^{-j_i}$ for some $j_i \in \mathbb N_0 \cup \{\infty\}$, with the notational convention that $2^{-j_i}$ is interpreted as $0$ if $j_i = \infty$. Moreover, the claim that there is an $l$, $0 \leq l < n$, with $\sum_0^l f(x_i, x_{i+1}) \leq a/2$ is equivalent to showing $f(x_0, x_1) \leq a/2$ since $f$ is nonnegative. In other words, $2^{-j_0} \leq \frac{1}{2} \sum_{i=0}^n 2^{-j_i}$; this is equivalent to $1 \leq \sum_{i=0}^n 2^{j_0-j_i-1}$. – LinearOperator32 Apr 1 at 6:32
• (Comment part 2) In other words, $1 \leq \frac{1}{2} + \sum_{i=1}^n 2^{j_0-j_i-1}.$ It seems to me that if the $j_i$ for $1\leq i \leq n$ are very large, this inequality does not hold. – LinearOperator32 Apr 1 at 6:36

It is false. Here is an example. Let $$X = [0,1]$$ and $$U_n = \{ (x,y) \mid \lvert x - y \rvert \le 3^{-n} \}$$. Let $$x_0 = 1, x_1 = 1/2, x_2 = 1/4$$. Then $$(x_0,x_1) \in U_0 \setminus U_1, (x_1,x_2) \in U_1 \setminus U_2$$. Hence $$f(x_0,x_1) = 1, f(x_1,x_2) = 1/2, a = 3/2$$. But $$f(x_0,x_1) > a/2$$.

So what can be done? I do not know the proof, but you certainly have $$f(x_0,x_1) \le a/2$$ or $$f(x_{n-1},x_n) \le a/2$$. Perhaps in the second case you can work with the smallest integer $$k$$ between $$0$$ and $$n$$ such that $$\sum_{i=k}^n f(x_{i-1} ,x_i) \le a/2$$. In other words, consider the reverse sequence $$x'_i = x_{n-i}$$. This should give you a proof.

• Yes, I just went through your suggestion and it works. Also: nice counterxample; I tried coming up with one last night but didn’t get to work out all the details. I will most likely edit my answer later with a full proof or perhaps I might add it as an answer, whatever’s more convenient I guess. – LinearOperator32 Apr 1 at 17:06
• In my opinion it would be better to write an answer. – Paul Frost Apr 2 at 10:52

As promised, here is a full proof based on Paul Frost's suggestion. (The first part of the proof will be identical to the one in my question; I write it in full for convenience of the reader). The argument is based on the one from Cobzas' Functional Analysis in Asymmetric Normed Spaces.

$$\mathbf{ Theorem}$$: Let $$X$$ be a nonempty set, and let $$(U_n)_n$$ be a sequence of nonempty subsets of $$X \times X$$ such that $$U_0= X \times X$$, and $$U_{n+1} \circ U_{n+1} \circ U_{n+1} \subseteq U_n$$ for every $$n$$. Suppose further that each $$U_n$$ contains the diagonal $$\triangle$$. Then, there is a quasi-pseudometric $$d$$ on $$X$$ such that for every $$n$$ $$U_{n+1} \subseteq \{(x,y) | d(x,y) < 2^{-n} \} \subseteq U_n.$$ Moreover, if the $$U_n$$ are assumed to be symmetric, $$d$$ can be taken to be a pseudometric.

Proof. One immediately observes $$U_{n+1} \subseteq U_n$$ for all $$n$$. Put $$f:X \times X \rightarrow [0, \infty), (x,y) \mapsto 2^{-n}$$ if $$(x,y) \in U_n \setminus U_{n+1}$$, and $$(x,y) \mapsto 0$$ if $$(x,y) \in \bigcap_k U_k$$. Define $$d: X \times X \rightarrow [0, \infty)$$, $$d(x,y) = \inf \sum_{i=0}^n f(x_i, x_{i+1}),$$ where the infimum is taken over all finite sequences $$(x_j)_{j=0, \ldots, n+1}$$ with $$x=x_0, x_{n+1}=y$$. Then, it is readily seen $$d$$ is a quasi-pseudometric (give yourself an epsilon of room to prove the triangle inequality, coining Tao's phrase). By considering sequences of length two, we have $$d(x,y) \leq f(x,y)$$ for every $$x,y$$. Moreover, one verifies $$f(x,y) \leq 2^{-l}$$ if and only if $$(x,y) \in U_l$$. We have the following claim:

$$\mathbf{Claim}$$: For every finite sequence $$(x_j)_{j=0, \ldots, n+1}$$ in $$X$$, we have $$f(x_0, x_{n+1}) \leq 2 \sum_{i=0}^{n} f(x_i, x_{i+1}).$$ The proof is by induction on $$n$$. The base case is trivial, and suppose the claim holds for all $$0 \leq m . Put $$a=\sum_{i=0}^n f(x_i, x_{i+1})$$. We will need to assume $$a \neq 0$$, so we deal with that case first.

In this case, $$f(x_i, x_{i+1})=0$$ for every $$0 \leq i \leq n$$, so that $$(x_i, x_{i+1}) \in \bigcap_k U_k$$. By induction hypothesis, $$f(x_0, x_n) \leq 2 \sum_{i=0}^{n-1} f(x_i, x_{i+1}) = 0.$$ Moreover, $$f(x_n, x_{n+1})=0$$. If $$f(x_0, x_{n+1})$$ is nonzero - say, $$f(x_0, x_{n+1}) = 2^{-l}$$ for some $$l$$ - then $$(x_0, x_{n+1}) \in U_l \setminus U_{l+1}$$. But $$(x_0, x_n), (x_n, x_{n+1}) \in U_{l+2}$$ since they lie in every $$U_k$$; thus $$(x_0, x_{n+1}) \in U_{l+2}^2 \subseteq U_{l+2}^3 \subseteq U_{l+1}$$. This is a contradiction, so $$f(x_0, x_{n+1})=0$$.

We assume $$a$$ is nonzero now. Next, we either have $$f(x_0, x_1) \leq a/2$$ or $$f(x_n, x_{n+1}) \leq a/2$$; for otherwise, one has by the nonnegativity of $$f$$ and the fact that $$n\geq 1$$ that $$a=\sum_{i=0}^n f(x_i, x_{i+1}) \geq f(x_0, x_1) + f(x_n, x_{n+1}) > a/2+a/2=a$$. There are two cases now; suppose $$f(x_0, x_1) \leq a/2$$ first. Let $$0 \leq k \leq n$$ be the greatest integer such that $$\sum_{i=0}^k f(x_i, x_{i+1}) \leq a/2$$. Necessarily $$k because $$a$$ is nonzero. Two situations can happen:

If $$0\leq k < n-1$$, then $$\sum_{i=k+2}^n f(x_i, x_{i+1}) \leq a/2$$ because the maximality of $$k$$ implies $$\sum_{i=0}^{k+1} f(x_i, x_{i+1}) > a$$. The induction hypothesis then implies $$f(x_{k+2}, x_{n+1}) \leq 2 \sum_{i=k+2}^n f(x_i, x_{i+1}) \leq 2 \cdot a/2 = a$$. We certainly have $$f(x_{k+1}, x_{k+2}) \leq a$$, and we also have by another application of the inductive hypothesis that $$f(x_0, x_{k+1}) \leq 2 \sum_{i=0}^k f(x_i, x_{i+1}) \leq 2 \cdot a/2 = a$$. By taking the minimal $$l$$ such that $$2^{-l} \leq a$$, we see that $$f(x_0, x_{k+1}), f(x_{k+1}, x_{k+2}), f(x_{k+2}, x_{n+1}) \leq 2^{-l}$$ because $$\text{im} f \subseteq \{0\} \cup \{2^{-m}\}_{m \in \mathbb N}$$. So, $$(x_0, x_{k+1}), (x_{k+1}, x_{k+2}), (x_{k+2}, x_{n+1}) \in U_l$$. This implies $$(x_0, x_{n+1}) \in U_l^3 \subseteq U_{l-1}$$, which means $$f(x_0, x_{n+1}) \leq 2^{-(l-1)} = 2 \cdot 2^{-l} \leq 2 a = 2 \sum_{i=0}^n f(x_i, x_{i+1}).$$

Next, if $$k=n-1$$, the inductive hypothesis gives $$f(x_0, x_n) \leq 2\sum_{i=0}^{n-1} f(x_i, x_{i+1}) \leq 2 \cdot a/2 = a$$. We also have $$f(x_n, x_{n+1}) \leq a$$ by the definition of $$a$$ and nonnegativity of $$f$$. In other words, $$f(x_0, x_n), f(x_n, x_{n+1}) \leq a$$, and by taking the minimal nonnegative integer $$l$$ such that $$2^{-l} \leq a$$, one obtains as before that $$(x_0, x_n), (x_n, x_{n+1}) \in U_l$$. So, because each $$U_m$$ contains the diagonal, one observes that by assumption, one has $$U_l^2 \subseteq U_l^3 \subseteq U_{l-1}$$. Thus, $$(x_0, x_{n+1}) \in U_{l-1}$$, and the same reasoning as above shows $$f(x_0, x_{n+1}) \leq 2a$$.

The second case when $$f(x_n, x_{n+1}) \leq a/2$$ is entirely analogous to the argument above, but we include it for the sake of completeness. Let $$0 \leq k \leq n$$ be the minimal integer such that $$\sum_{i=k}^n f(x_i, x_{i+1}) \leq a/2$$. Necessarily $$k>0$$ since $$a \neq 0$$. First suppose $$1 \leq k \leq n$$. Then, $$\sum_{i=0}^{k-2} f(x_i, x_{i+1}) \leq a/2$$, so by inductive hypothesis $$f(x_0, x_{k-1}) \leq a$$. The inductive hypothesis also gives $$f(x_k, x_{n+1}) \leq a$$, and one has $$f(x_{k-1}, x_k) \leq a$$. So, there is $$l \in \mathbb N$$ such that $$(x_0, x_{k-1}), (x_{k-1}, x_k), (x_k, x_{n+1}) \in U_l$$ and $$2^{-l} \leq a$$. Hence $$f(x_0, x_{n+1}) \leq 2a$$ as above.

Finally, if $$k=1$$, then one concludes from the inductive hypothesis that $$f(x_1, x_{n+1}) \leq 2a$$, and $$f(x_0, x_1) \leq a$$ is also true; so as has been argued three times now, $$f(x_0, x_{n+1}) \leq 2a$$, which proves the claim.

To conclude the proof, we only need to show $$U_{n+1} \subseteq \{(x,y) \in X^2 | d(x,y) <2^{-n} \} \subseteq U_n$$ for every $$n$$; the first inclusion follows immediately from the inequality $$d(x,y) \leq f(x,y)$$ for every $$x,y$$. For the second inequality, for $$x,y$$ such that $$d(x,y) <2^{-n}$$ and for $$0< \varepsilon < 2^{-n} - d(x,y)$$, one can find a finite sequence $$x=x_0, \ldots, x_{m+1} =y$$ such that $$\sum_{i=0}^m f(x_i, x_{i+1}) < d(x,y) + \varepsilon < 2^{-n}.$$ By the claim, $$f(x,y) \leq 2 \sum_{i=0}^m f(x_i, x_{i+1}) < 2^{-n+1}$$; because the image of $$f$$ (excluding 0) consists of only rationals of the form $$2^{-l}$$, one sees that $$f(x, y) \leq 2^{-n}$$. So, $$(x,y) \in U_n$$. $$\blacksquare$$

Remark: It seems to me that the reduction made in the proof of the claim in my original question (and also the reduction in Cobzas' proof of the claim) that $$f(x_i, x_{i+1}) \neq a$$ for any $$0 \leq i \leq n$$ is not needed, and so I've omitted this reduction. It seems unnecessary, but perhaps I have missed a detail and it is required somewhere in the argument.