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

Question

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 <n $. 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.

Answer 1

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.

Answer 2

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 <n $. 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<n$ 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.