Pushouts of uniform embeddings

Proof. Since each $V_{n+1}$ contains the diagonal, we have $V_{n+1} \subseteq V_{n+1} \circ V_{n+1} \circ V_{n+1} \subseteq V_n$. Thus, the sequence is decreasing, i.e. $V_{n'} \subseteq V_n$ for $n' \geq n$.

We prove the claim by strong induction on $k$, simultaneously for all $M$. If $k = 0$, then $(s_0,s_k) = (s_0,s_0) \in \Delta_S \subseteq V_M$. If $k = 1$, then $2^{-m_1} \leq 2^{-M}$ means $m_1 \geq M$, and hence $(s_0,s_1) \in V_{m_1} \subseteq V_M$.

Now let $k \geq 2$, and let $\sigma \coloneqq \sum_{l=1}^{k} 2^{-m_l}$. Since $0 < \sigma \leq 2^{-M}$, there is a largest integer $N$ with $\sigma \leq 2^{-N}$, and we have $N \geq M$. Since $V_N \subseteq V_M$, it suffices to show that $(s_0,s_k) \in V_N$. By the maximality of $N$, we have $\sigma > 2^{-(N+1)}$. Since $k \geq 2$ and all summands are positive, each summand is strictly smaller than $\sigma$, so $2^{-m_l} < 2^{-N}$, i.e. $m_l \geq N+1$ for all $l$.

Let $p \in \{0,\dotsc,k\}$ be the largest index with $\sum_{l=1}^{p} 2^{-m_l} \leq 2^{-(N+1)}$. Since $\sigma > 2^{-(N+1)}$, we have $p < k$. We split the chain into three parts:

• The chain $s_0,\dotsc,s_p$ has $p < k$ steps and total length at most $2^{-(N+1)}$. By the induction hypothesis, $(s_0,s_p) \in V_{N+1}$.
• The single step satisfies $(s_p,s_{p+1}) \in V_{m_{p+1}} \subseteq V_{N+1}$, since $m_{p+1} \geq N+1$.
• The chain $s_{p+1},\dotsc,s_k$ has $k-p-1 < k$ steps. By the maximality of $p$, we have $\sum_{l=1}^{p+1} 2^{-m_l} > 2^{-(N+1)}$, and therefore its total length satisfies $$\sum_{l=p+2}^{k} 2^{-m_l} = \sigma - \sum_{l=1}^{p+1} 2^{-m_l} < 2^{-N} - 2^{-(N+1)} = 2^{-(N+1)}.$$ By the induction hypothesis, $(s_{p+1},s_k) \in V_{N+1}$.

It follows that $(s_0,s_k) \in V_{N+1} \circ V_{N+1} \circ V_{N+1} \subseteq V_N$. $\square$

Proof. Let $\Phi$ be the set of all subsets of $P \times P$ that contain some $W_n$. Since the sequence is decreasing, $\Phi$ is closed under finite intersections, and it is clearly closed under taking larger subsets. Every element of $\Phi$ contains $\Delta_P$. If $S \in \Phi$ contains $W_n$, then $S^{\op}$ contains $W_n^{\op} = W_n$, and $W_{n+1} \in \Phi$ satisfies $W_{n+1} \circ W_{n+1} \subseteq S$. Thus, $\Phi$ is a uniform structure on $P$. By assumption, $j$ and $u$ are uniform with respect to $\Phi$. Since $P$ carries the finest such uniform structure, $\Phi$ is contained in the uniform structure of $P$. In particular, every $W_n$ is an entourage of $P$. $\square$

Proof. Recall that every entourage of a uniform space contains a symmetric entourage $E$ with $E \circ E \circ E$ contained in the given entourage. Thus, we can choose symmetric entourages $U_n$ of $Y$ with $U_0 \subseteq U$ and $U_{n+1} \circ U_{n+1} \circ U_{n+1} \subseteq U_n$ for all $n \geq 0$.

Since $f$ is uniform, $(f \times f)^*(U_n)$ is an entourage of $A$. Since $i$ is a uniform embedding, there is an entourage $V'_n$ of $X$ with $(i \times i)^*(V'_n) = (f \times f)^*(U_n)$. We now choose symmetric entourages $V_n$ of $X$ recursively: let $V_0$ be a symmetric entourage contained in $V'_0$, and let $V_{n+1}$ be a symmetric entourage with $V_{n+1} \circ V_{n+1} \circ V_{n+1} \subseteq V_n \cap V'_{n+1}$. Since $V_{n+1}$ contains the diagonal, we have $V_{n+1} \subseteq V'_{n+1}$. Thus, for all $n \geq 0$, we have $V_{n+1} \circ V_{n+1} \circ V_{n+1} \subseteq V_n$ and $V_n \subseteq V'_n$. The latter implies $(i \times i)^*(V_n) \subseteq (i \times i)^*(V'_n) = (f \times f)^*(U_n)$, which is precisely the last statement of the claim. $\square$

Proof. We verify the assumptions of Claim 1:

• $W_n$ contains $\Delta_P$, using chains with $k = 0$.
• $W_n$ is symmetric, since each $Q_m$ is symmetric, so that we can reverse chains.
• $W_{n+1} \subseteq W_n$, since $2^{-(n+1)} \leq 2^{-n}$.
• $W_{n+1} \circ W_{n+1} \subseteq W_n$, since the concatenation of two chains of length at most $2^{-(n+1)}$ is a chain of length at most $2^{-n}$.
• We have $Q_n \subseteq W_n$, using chains with $k = 1$ and $m_1 = n$. Therefore, $(j \times j)^*(W_n)$ contains $U_n$ and is an entourage of $Y$. Likewise, $(u \times u)^*(W_n)$ contains $V_n$ and is an entourage of $X$.

Hence, Claim 1 shows that every $W_n$ is an entourage of $P$. $\square$

Proof. Each step $(z_{l-1},z_l)$ of the chain lies in $Q_{m_l} = (j \times j)_*(U_{m_l}) \cup (u \times u)_*(V_{m_l})$, i.e. it comes from a pair in $U_{m_l}$ or from a pair in $V_{m_l}$ (or both). We distinguish two cases.

Case 1: Every step comes from a pair in $V_{m_l}$, i.e. $(z_{l-1},z_l) \in (u \times u)_*(V_{m_l})$ for all $1 \leq l \leq k$. Then for each $1 \leq l \leq k$, we can choose $(x'_l,x''_l) \in V_{m_l}$ with $u(x'_l) = z_{l-1}$ and $u(x''_l) = z_l$. For $0 < l < k$, the point $z_l \notin j(Y)$ has exactly one preimage $x_l$ under $u$ by fact 3, so that $x''_l = x_l = x'_{l+1}$. Let $x_0 \coloneqq x'_1$ and $x_k \coloneqq x''_k$. Then $x_0,\dotsc,x_k$ are points of $X$ with $$(x_{l-1},x_l) \in V_{m_l} \quad \text{for } 1 \leq l \leq k.$$ By Lemma 1 applied to the sequence $(V_n)$, we get $(x_0,x_k) \in V_M$. Since $u(x_0) = z_0 = j(y) \in j(Y)$, we have $x_0 = i(a)$ for some $a \in A$ by fact 2. Then $j(f(a)) = u(i(a)) = z_0 = j(y)$, so $f(a) = y$ by fact 1. Likewise, $x_k = i(a')$ for some $a' \in A$ with $f(a') = y'$. Since $(i(a),i(a')) \in V_M$, Claim 2 shows that $$(y,y') = (f(a),f(a')) \in U_M.$$

Case 2: Some step comes from a pair in $U_{m_l}$, i.e. $(z_{l-1},z_l) \in (j \times j)_*(U_{m_l})$ for some $1 \leq l \leq k$. Then both $z_{l-1}$ and $z_l$ lie in $j(Y)$. Since $z_0$ and $z_k$ are the only points of the chain in $j(Y)$, this means $l = 1$ and $k = 1$. So the chain consists of the single step $(z_0,z_1) \in (j \times j)_*(U_{m_1})$. Since $z_0 = j(y)$, $z_1 = j(y')$, and $j$ is injective (fact 1), this means $(y,y') \in U_{m_1}$. Since $2^{-m_1} \leq 2^{-M}$, we have $m_1 \geq M$, and hence $(y,y') \in U_{m_1} \subseteq U_M$. $\square$

Proof. We use the notation from the previous section. Let $U$ be an entourage of $Y$, and let $U_n$, $V_n$, $W_n$ be as above. We need to show that $U = (j \times j)^*(W')$ for some entourage $W'$ of $P$. It suffices to show that $$(j \times j)^*(W_1) \subseteq U,$$ since $W_1$ is an entourage of $P$ by Claim 3. Indeed, then $W' \coloneqq W_1 \cup (j \times j)_*(U)$ is an entourage of $P$, and since $j$ is injective, we have $(j \times j)^*((j \times j)_*(U)) = U$ and therefore $(j \times j)^*(W') = (j \times j)^*(W_1) \cup U = U$.

So let $y,y' \in Y$ with $(j(y),j(y')) \in W_1$, and choose a chain from $j(y)$ to $j(y')$ of length at most $1/2$. That is, we choose points $z_0,\dotsc,z_k \in P$ with $z_0 = j(y)$ and $z_k = j(y')$, and integers $m_1,\dotsc,m_k \geq 0$, such that $$(z_{l-1},z_l) \in Q_{m_l} \quad \text{for all } 1 \leq l \leq k, \qquad \sum_{l=1}^{k} 2^{-m_l} \leq \frac{1}{2}.$$ Let $0 = l_0 < l_1 < \dotsc < l_r = k$ be the indices $l$ with $z_l \in j(Y)$. By fact 1, there are unique $y_s \in Y$ with $j(y_s) = z_{l_s}$ for $0 \leq s \leq r$, and we have $y_0 = y$ and $y_r = y'$.

For $0 \leq s < r$, the points $z_{l_s},\dotsc,z_{l_{s+1}}$ with the integers $m_{l_s+1},\dotsc,m_{l_{s+1}}$ form a chain from $j(y_s)$ to $j(y_{s+1})$ whose intermediate points do not lie in $j(Y)$. Let $$\sigma_s \coloneqq \sum_{l=l_s+1}^{l_{s+1}} 2^{-m_l}$$ be its length. Since $0 < \sigma_s \leq 1/2$, there is a largest integer $M_s$ with $\sigma_s \leq 2^{-M_s}$, and we have $M_s \geq 1$. By Claim 4, we have $(y_s,y_{s+1}) \in U_{M_s}$. By the maximality of $M_s$, we have $2^{-(M_s+1)} < \sigma_s$, i.e. $2^{-M_s} < 2\sigma_s$.

Thus, $y_0,\dotsc,y_r$ are points of $Y$ with $(y_s,y_{s+1}) \in U_{M_s}$ for $0 \leq s < r$. Since the parts of the chain do not overlap, we have $$\sum_{s=0}^{r-1} 2^{-M_s} \leq 2 \sum_{s=0}^{r-1} \sigma_s = 2 \sum_{l=1}^{k} 2^{-m_l} \leq 2 \cdot \frac{1}{2} = 1 = 2^{0}.$$ By Lemma 1 applied to the sequence $(U_n)$, we conclude that $(y,y') = (y_0,y_r) \in U_0 \subseteq U$. $\square$