0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I think it has to do with the fact that all values of $f$ are of the form $\frac{1}{2^n}$.. $\endgroup$ – Henno Brandsma Apr 1 at 5:57
  • $\begingroup$ (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}$. $\endgroup$ – LinearOperator32 Apr 1 at 6:32
  • $\begingroup$ (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. $\endgroup$ – LinearOperator32 Apr 1 at 6:36
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – LinearOperator32 Apr 1 at 17:06
  • $\begingroup$ In my opinion it would be better to write an answer. $\endgroup$ – Paul Frost Apr 2 at 10:52
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.