Hyperimaginaries, pseudometrics, and uniform spaces
On one hand, there’s a well-known correspondence between pseudometrics and uniform structures; on the other hand, the type defining a type-definable equivalence relation looks like a collection of entourages defining a uniformity. Indeed, passing through the correspondence, type-definable equivalence relations are precisely the distance-0-apart equivalence relation of their corresponding pseudometric, and this is how one can treat hyperimaginaries on equal footing with imaginary sorts (by viewing a discrete first-order structure as a continuous first-order structure.) Apparently, this was one of the motivations for IBY to develop continuous logic.
At some point, I was interested in this, and wrote it down to understand it. What follows are my notes.
The classic reference for uniform structures is Bourbaki’s Topologie Générale, Chapter II, which we will closely follow.
Definition. A pseudometric on a set \(X\) is a function \(X \times X \overset{f}{\to} \overline{\mathbb{R}}\) from \(X \times X\) to the extended real line \(\overline{R} = \mathbb{R} \cup \{+\infty\}\) which satisfies all the properties of a metric (symmetric, positivity, triangle inequality) except that \(f(x,y) = 0\) does not necessarily imply that \(x = y\).
Definition. Let \(X\) be a set. A uniform structure, or uniformity, on \(X\) consists of a collection \(\Phi\) of reflexive relations \(U \subseteq X \times X\) satisfying the following conditions:
\(\Phi\) is a filter.
If \(U \in \Phi\), then there is a \(V \in \Phi\) such that \[V \circ V \overset{\operatorname{df}}{=} \{(x,z) \operatorname{\big{|}} \exists y \in X \text{ s.t. } (x,y) \in V \land (y,z) \in V\}.\]
The members \(U\) of the uniformity \(\Phi\) are sometimes called entourages. Every uniformity \(\Phi\) can be given a filter base consisting of symmetric \(U\)’s.
Families of pseudometrics induce uniformities:
Proposition. (Section 9.2 in Topologie Générale) Let \(f\) be a pseudometric on a set \(X\). For each \(a > 0\), set \(U_{a} \overset{\operatorname{df}}{=} f^{-1}([0,a])\). Then the collection \((U_a)_{a \in \mathbb{R}^+}\) forms a filter base for a uniform structure \(\mathscr{U}\) on \(X\).
Proof. Let \(U'\) contain \(U_a\) and \(U''\) contain \(U_b\). Then \(U' \cap U''\) contains \(U_a \cap U_b = U_{\min(a,b)}\). By definition \(\mathscr{U}\) is also upwards-closed. By the triangle inequality, \(U_a\) contains \(U_{\frac{a}{2}} \circ U_{\frac{a}{2}}\). \(\square\)
Definition. (9.2.2 in ) Given a pseudometric \(f\) on a set \(X\), the uniformity defined by \(f\) is the uniformity on \(X\) which has a filter base of entourages the family of sets \(f^{-1}([0,a])\) where \(a \in \mathbb{R}^+\).
(This amounts to taking the inverse image under \(f\) of the neighborhood filter of \(0\) in the subspace \([0, +\infty)\) of \(\mathbb{R}\).)
We say that two pseudometrics on \(X\) are equivalent if they define the same uniformity.
Definition. (9.2.3 in Topologie Générale) If \((f_i)_{i \in I}\) is a family of pseudometrics on a set \(X\), then the least upper bound of the set of uniformities defined on \(X\) by the pseudometrics \(f_i\) is called the uniformity defined by the family \((f_i)\).
Two families of pseudometrics are said to be equivalent if they define the same uniformity on \(X\).
Remark. (9.3 in Topologie Générale) Let \(\mathscr{U}\) be generated by the family of pseudometrics \((f_i)\). \(\mathscr{U}\) is Hausdorff if and only if every pair of points \((x,y)\) is separated by some \(f_i\).
Every uniformity is induced by some family of pseudometrics
Importantly, any uniform structure can be realized as the uniformity induced by a family of pseudometrics.
Lemma. (9.4.2 in Topologie Générale) If a uniformity \(\mathscr{U}\) on \(X\) has a countable filter base, then there is a pseudometric \(f\) on \(X\) such that \(\mathscr{U}\) is identical with the uniformity defined by \(f\).
Proof. Let \((V_n)\) be a countable filter base for \(\mathscr{U}\). Define inductively a sequence \((U_n)\) of symmetric entourages of \(\mathscr{U}\) such that
\(U_1 \subset V_1\), and
\(U_{n+1} \circ U_{n+1} \circ U_{n+1} \subset U_n \cap V_n\).
(How? Take \(U_{n+1}\) to be the entourage \(V\) such that \(V \circ V \subset V'\), where \(V'\) is the entourage such that \(V' \circ V' \subseteq U_n \cap V_n \in \mathscr{U}\).)
Claim. This \((U_n)\) again is a filter base for a uniformity which coincides with \(\mathscr{U}\).
Proof.
Each member of \(U_n\) clearly contains the diagonal.
Since the \(U_n\) were symmetric, any the reverse \(U'^{-1}\) of any \(U'\) containing \(U_i\) again contains \(U_i\).
If \(U' \subseteq U_n\), and \(U_n\) contains \(U_{n+1} \circ U_{n+1} \circ U_{n+1}\), then it is easy to check that this must also contain \(U_{n+1} \circ U_{n+1}\).
Why is the filter generated by \((U_n)\) again \(\mathscr{U}\)? It suffices to check that each \(U \in \mathscr{U}\) contains some \(U_n\). Let \(U \in \mathscr{U}\). Since \(\mathscr{U}\) is generated by the countable filter base \((V_n)\), \(U\) contains \(V_k\) for some \(k\), and by construction \(V_k\) contains \(V_k \cap U_k\), which contains \(U_{k + 1} \circ U_{k + 1} \circ U_{k+1} \supset U_{k+1}\).
\(\square\)
Now, we have obtained in place of the countable filter base \((V_n)\) of \(\mathscr{U}\) an equivalent countable filtration \((U_n)\) which is also a filter base of \(\mathscr{U}\).
We can therefore associate a natural valuation \(v(x,y)\) to every pair \((x,y) \in X \times X\), defined by \[v(x,y) \overset{\operatorname{df}}{=} n - 1,\] where \(n\) is the index of the first \(U_n\) such that \((x,y) \not \in U_n\).
In case \((x,y) \in \bigcap_n U_n\), we say that \(v(x,y) = \infty\).
Define as follows the real-valued function \(g\) on \(X \times X\), by \[g(x,y) \overset{\operatorname{df}}{=} 2^{-v(x,y)},\] so in case \((x,y) \in \bigcap_{n} U_n\), \(g(x,y) = 1\).
\(g\) is symmetric because each \(U_k\) was, positive by definition, and \(g^{-1}(\{0\})\) contains the diagonal relation \(\Delta_X \subseteq X \times X\) because every \(V \in \mathscr{U}\) contained \(\Delta_X\).
\(g\) does not a priori satisfy the triangle inequality. (If it did, then for each \(x,y,\) and \(z\) and each value \(c - 1\) for \((x,y)\) there would only be finitely many values \(a - 1\) and \(b - 1\) for \((x,z)\) and \((z,y)\), which is quite strong.)
However, we can build something out of \(g\) which does. Define as follows the real-valued function \(f\) by
\[f(x,y) = \inf \left\{\sum_{i = 0}^{p - 1} g(z_i. z_{i + 1}) \right\},\] (where the inf is taken over over all finite sequences \((z_i)_{0 \leq i \leq p}\), \(p \in \mathbb{N}\), with \(z_0 = x, z_p = y\))
Claim. \(f\) is a pseudometric which satisfies the inequalities \[\frac{1}{2} g(x,y) \leq f(x,y) \leq g(x,y).\]
Proof.
(Symmetry.) If \(f(y,x) = a\) is approximated by a sequence of finite sequences \((z_j \leq p_i)_{i \in I}\), then by reversing the sequences and using the symmetry of \(g\), \(a = f(x,y)\) also.
(Positivity.) \(f(x,y)\) is an inf of sums of nonnegative numbers.
(Triangle inequality.) Let \(x,y,z \in X\). When we write e.g. “\(x \to z\)” we mean to index finite paths starting at \(x\) and ending at \(z\). We have: \[\inf_{x \to z} \left\{ \sum_{i = 0}^{p-1} g(z_i. z_{i + 1}) \right\} + \inf_{z \to y} \left\{ \sum_{i = 0}^{p - 1} g(z_i. z_{i + 1})\right\}\] \[= \inf_{x \to z \to y} \left\{ \sum_{i = 0}^{p-1} g(z_i. z_{i+1}) \right\} \geq \inf_{x \to y} \left\{ \sum_{i = 0}^{p-1} g(z_i. z_{i+1})\right\} = f(x,y),\] where the latter inequality holds because the infimum on the right is being computed over at least all the paths the infimum on the left is being computed over, and the former equality holds because the two infima are independent (the paths \(x \to z \to y\) split into the product \((x \to z) \times (z \to y)\)).
(Fiber over \(0\) contains the diagonal.) By definition, \(f(x,x) \leq g(x,x) = 0\).
(\(\frac{1}{2} g(x,y) \leq f(x,y) \leq g(x,y)\).) Let’s verify that \(\frac{1}{2} g(x,y) \leq f(x,y).\) We proceed by induction on the length \(p + 1\) of a finite path \(x \to y\) to prove that \[\frac{1}{2} g(x,y) \leq \sum_{ i = 0}^{p-1} g(z_i, z_{i+1}).\] If \(p = 1\), then certainly \(g(x,y) \geq \frac{1}{2} g(x,y)\), so the base case is proved.
If we set \(a \overset{\operatorname{df}}{=} \displaystyle \sum_{i = 0}^{p-1} g(z_i, z_{i + 1})\), then the equation is true if \(a \geq \frac{1}{2}\), since \(g(x,y) \leq 1\). Suppose then that \(a < \frac{1}{2}\). Let \(h\) be the first index \(k\) such that \[\sum_{i < k}^{p- 1} g( z_i, z_{i+1}) \geq \frac{a}{2}.\]
Note that by choice of \(h\), \(\sum_{i < h - 1} g (z_i, z_{i + 1}) < \frac{a}{2}\), and \(\sum_{i > h -1} g(z_i, z_{i + 1}) \leq \frac{a}{2}\).
By the induction hypothesis, \[\frac{1}{2} g(x, z_{h-1}) \leq f(x,z_{h-1}) = \inf \left\{sum_{i < h} g(z_i, z_{i + 1}) \right\} < \frac{a}{2}.\] Therefore, \(\frac{1}{2} g(x, z_{h-1}) \leq \frac{a}{2}\), which implies that \(g(x, z_{h - 1}) \leq a\). Similarly, \(g(z_h, y) \leq a\).
If \(k\) is the integer such that \(\frac{1}{2^k}\) is the closest dyadic lower bound on \(a\) (with \(k \geq 2\) since \(a < \frac{1}{2}\)), then since \(g\) takes dyadic values, \[g(x,z_{h-1}) \leq \frac{1}{2^k} \hspace{2mm} \text{ and } \hspace{2mm} g(z_h, y) \leq \frac{1}{2^k}.\] Since \(\frac{1}{2^{(k + 1)-1}}\), then by how \(g\) was defined, \((x,z_{h - 1})\) and \((z_h,y)\) are in \(U_k\). Since evidently \(g(z_{h - 1}, z_h) \leq a\), \((z_{h - 1}, z_h) \in U_k\) as well. Since \(U_k \circ U_k \circ U_k \subseteq U_{k - 1}\), \((x,y) \in U_{k - 1}\).
Now, \[g(x,y) \leq \dfrac{1}{2^{k- 1}} = 2 \cdot \dfrac{1}{2^k} \leq 2a.\]
Therefore, \(\frac{1}{2} g(x,y) \leq a\). Taking infima, conclude \[\frac{1}{2} g(x,y) \leq f(x,y),\] and the claim is proved.
\(\square\)
Now we show that the uniformity \(\mathscr{U}(f)\) generated by \(f\) coincides with the uniformity \(\mathscr{U}\). \(f^{-1}([0,a])\) contains \(U_k\) if \(2^{-k} < a\), so \(\mathscr{U}(f)\) is certainly coarser than \(\mathscr{U}\). On the other hand, each \(U_k\) from \((U_n)\) contains the set of all points \((x,y)\) such that \(f(x,y) \leq \frac{1}{2^{k + 1}}\), which means that \(\frac{1}{2} g(x,y) \leq \frac{1}{2^{k + 1}}\) amd therefore \(g(x,y) \leq \frac{1}{2^k}\), so this says that each such \((x,y)\) is inside \(U_k\), so \(f^{-1}([0, \frac{1}{2^{k + 1}}])\). Since every member of a filter base for \(\mathscr{U}(f)\) contains a member of a filter base for \(\mathscr{U}\) and vice-versa, they must generate the same uniformity \(\mathscr{U}\). \(\square\)
Theorem. (9.4.1 in Topologie Générale Given a uniformity \(\mathscr{U}\) on a set \(X\), there is a family of pseudometrics on \(X\) such that the uniformity defined by this family is identical with \(\mathscr{U}\).
Proof. For every \(V \in \mathscr{U}\), inductively define a filtration of symmetric entourages \((U_n)\) such that \(U_1 \subseteq V\) and \(U_{n + 1} \circ U_{n + 1} \subset U_n\) for all \(n \geq 1\).
Claim. The sequence \((U_n)\) is a filter base for a uniformity \(\mathscr{U}_V\) coarser than \(\mathscr{U}\).
Proof.
If \(U'\) contains a \(U_i\), then \(U_i \supseteq \Delta_X\) by definition, so \(U'\) contains \(\Delta_X\) also.
If \(U'\) contains \(U_i\), then since \(U_i\) was symmetric, \(U'^{-1}\) also contains \(U_i\).
If \(U'\) contains \(U_i\), then since \(U_i \supseteq U_{i+1} \circ U_{i+1}\), \(U'\) contains \(U_{i+1} \circ U_{i + 1}\) also.
\(\mathscr{U}_V\) is coarser than \(\mathscr{U}\) because the filter base for \(\mathscr{U}_V\) is contained inside \(\mathscr{U}\).
\(\square\)
Furthermore, \(\mathscr{U}\) is the least upper bound of all the uniformities \(U_V\) for \(V\) running through \(\mathscr{U}\). Therefore it suffices to induce each countably-based uniformity \(\mathscr{U}_V\) by a pseudometric, and we have already shown that this is possible. \(\square\)
Hyperimaginary sorts and uniform structures
A uniformity on a set \(X\) given by a filter \(\Phi\) of entourages looks suspiciously like a type-definable equivalence relation. Indeed, the intersection \(\bigcap \Phi\) is an equivalence relation on \(X\), and in the case when \(\Phi\) was induced by a pseudometric, \(\bigcap \Phi\) is the equivalence relation of points distance \(0\) from each other.
More importantly, any type-definable equivalence relation on a model \(X\) is the filter base for a uniformity on \(X\):
Proposition. Let \(E = \bigcap \Phi\) be a type-definable equivalence relation on \(X\). Then for every \(\varphi_i(x,y) \in \Phi\), there exists another \(\varphi_j(x,y) \in \Phi\) such that \[\models \left(\exists z\hspace{1mm} \varphi_j(x,z) \land \varphi_j(z,y) \right) \rightarrow \varphi_i(x,y).\]
Proof. This is just compactness: \[\exists z \hspace{1mm}\Phi(x,z) \land \Phi(z,y) \models \varphi_i(x,y),\] hence \[\left(\exists z \hspace{1mm} \Phi(x,z) \land \Phi(z,y) \right) \land \neg \varphi_i(x,y)\] is inconsistent. Compactness tells us this inconsistency is finitely supported, and since \(\Phi\) can be assumed to be closed under finite conjunctions, there is a single \(\varphi_j(x,y)\) such that \[\left(\exists z \hspace{1mm} \varphi_j(x,z) \land \varphi(z,y) \right) \land \neg \varphi_i(x,y)\] is inconsistent. Since the above is only a finite conjunction of formulas, saying it is inconsistent is the same as saying that its negation holds, but then by material implication, we have therefore shown \[\models \left(\exists z \varphi_j(x, z) \land \varphi(z,y) \right) \rightarrow \varphi_i(x,y).\] \(\square\)
Therefore, in light of the fact that every uniformity is induced by a family of pseudometrics, to every type-definable equivalence relation \(E\) on a model \(M\) we can associate a family of pseudometrics \((f_i^E)\). In light of the fact that every countably-based uniformity is induced by a single pseudometric, when \(E\) is equivalent to a countable conjunction of formulas we can then associate to \(E\) a single pseudometric \(f^E\).
