Return to Answer

EDIT3: With the help of Dap's answer to my question here I have finally convinced myself that it does always work for countably type-definable equivalence relations. The proof (especially the proof of uniform convergence) is difficult enough that I think it's worth writing down.

EDIT4: It has come to my attention that this result is implicit in the proofs leading up to Theorem 2.20 in the paper 'Uncountable dense categoricity in cats' by Ben Yaacov.

EDIT3: With the help of Dap's answer to my question here I have finally convinced myself that it does always work for countably type-definable equivalence relations. The proof (especially the proof of uniform convergence) is difficult enough that I think it's worth writing down.

EDIT2: There is a serious problem with this argument in the step regarding the amalgamation property, i.e. the amalgamation procedure described fails to work in all cases. If I can resolve this I'll post an edit.

EDIT: It's actually not even true for countable theories. Here is a counterexample.

Let $\mathcal{L}=\{P_i\}_{i<\omega}$ be a countable sequence of binary predicates and let $\Sigma$ be the $\mathcal{L}$-theory consisting of the following for each $i<\omega$:

• $\forall x P_i(x,x)$
• $\forall xy(P_i(x,y)\leftrightarrow P_i(y,x))$
• $\forall xyz(P_{i+1}(x,y)\wedge P_{i+1}(y,z) \rightarrow P_i(x,z))$

Note that these imply $\forall xy(P_{i+1}(x,y) \rightarrow P_{i}(x,y))$.

Let $E(x,y)$ be the partial type given by the formulas $\{P_i(x,y)\}_{i<\omega}$. It's clear that in any model of $\Sigma$, $E$ gives a type-definable equivalence relation.

Let $\mathcal{K}$ be the class of finite models of $\Sigma$. First of all I claim that this class contains only countably many isomorphism types. To see this note that for any $\mathfrak{A} \in \mathcal{K}$ and any $a,b\in \mathfrak{A}$, the quantifier free type of $ab$ is uniquely determined by the quantity $Q(x,y)=2^{-i}$ where $\mathfrak{A} \models P_i(x,y)\wedge \neg P_{i+1}(x,y)$ or $Q(x,y)=0$ if $\mathfrak{A} \models E(x,y)$. This has countably many values and the isomorphism type of a model of $\mathcal{K}$ is uniquely determined by the values of $Q$ on its pairs of elements.

Also since $\Sigma$ is a universal theory $\mathcal{K}$ is closed under substructures.

I claim that $\mathcal{K}$ has the amalgamation property. To see this let $\mathfrak{A}\subset \mathfrak{B}$ and $\mathfrak{A} \subset \mathfrak{C}$ with $\mathfrak{A}$, $\mathfrak{B}$, and $\mathfrak{C}$ all models of $\Sigma$. We can give an amalgamation $\mathfrak{D}$ whose universe is $B\cup C$ and where for any $b \in B \setminus A$ and $c \in C \setminus A$ we set $Q(b,c) = \min(1,2 \min_{a \in A}\max(Q(b,a),Q(a,c)))$. In other words we introduce only the $P_i$ relationships that are absolutely necessary according to $\Sigma$.

So we have that $\mathcal{K}$ is a Fraïssé class and we can find a Fraïssé limit $\mathfrak{F}$. Let $T=\mathrm{Th}(\mathfrak{F})$. Since the automorphism type of every finite tuple in $\mathfrak{F}$ is entirely determined by its quantifier free type and since every quantifier free type consistent with $T$ occurs in $\mathfrak{F}$, $T$ admits quantifier elimination.

Let $\mathcal{L}^\prime$ be a continuous language with a single binary $[0,1]$-valued predicate symbol $Q$. Interpret $\mathfrak{F}$ as an $\mathcal{L}^\prime$-structure $\mathfrak{F}^\prime$ using the definition of $Q$ given above. It's clear that $\mathfrak{F}$ and $\mathfrak{F}^\prime$ are interdefinable and more than that interdefinable in a quantifier free way. In particular I claim that $T^\prime = \mathrm{Th}(\mathfrak{F}^\prime)$ eliminates quantifiers in the sense of continuous logic. In particular this implies that the $2$-type of any pair $ab$ is entirely determined by the value of $Q(a,b)$. Also note that by construction we have that $\mathfrak{F} \models E(a,b)$ if and only if $\mathfrak{F}^\prime \models Q(a,b)$ (i.e. that it is $0$).

Let $\rho(x,y)$ be a $\varnothing$-definable $[0,1]$-valued pseudo-metric such that $\mathfrak{F} \models E(a,b)$ implies $\mathfrak{F}^\prime \models \rho(a,b)$. By quantifier elimination there must be some continuous function $\alpha:[0,1]\rightarrow[0,1]$ such that $\rho(x,y)=\alpha(Q(x,y))$. Now for each $i<\omega$ consider the finite $\mathcal{L}$-structure $\mathfrak{A}$ with $A=\{a,b,c\}$ such that $Q(a,b)=0$, $Q(a,c)=2^{-i}$, and $Q(b,c)=2^{-i-1}$. Note that the third axiom schema for $\Sigma$ translates to $Q(x,z)\leq 2 \max(Q(x,y),Q(y,z))$, so in particular $\mathfrak{A}$ is a model of $\Sigma$. Therefore it embeds into $\mathfrak{F}$ with some map $f:\mathfrak{A}\rightarrow \mathfrak{F}$. Since $Q(f(a),f(b))=0$ we must have that $\rho(f(a),f(b))=0$. Since $\rho$ is a pseudo-metric this implies that $\rho(f(a),f(c))=\rho(f(b),f(c))$. Therefore we have that $\alpha(2^{-i})=\alpha(2^{-i-1})$. Since this is true for any $i<\omega$, we have that $\alpha$ is constant on the set $\{2^{-i}\}_{i<\omega}$. It must be the case that $\alpha(0)=0$ since $\mathfrak{F} \models E(a,b)$ implies $\mathfrak{F}^\prime \models \rho(a,b)$, therefore by continuity $\alpha(r)=0$ for all $r\in[0,1]$ and $\rho$ is the trivial pseudo-metric. On the other hand $E$ is clearly a non-trivial equivalence relation because there is a finite model of $\Sigma$ in which there are two elements with $\neg E(a,b)$.

So we have a theory with a countably type-definable non-trivial equivalence relation (definable over $\varnothing$) in which the only $\varnothing$-definable pseudo-metric that is at least as coarse as it is the trivial pseudo-metric.

I'm not sure if allowing more parameters for the pseudo-metric can save it but I'm not very hopeful.

EDIT3: There is a sense in which general hyperimaginaries are realized in a continuous $T^{eq}$. Specifically any type-definable equivalence relation is the intersection of a family of countably type-definable equivalence relations. It follows from this and the result below that any hyperimaginary that is just a quotient by a type-definable equivalence relation is the direct limit of some directed family of imaginaries. This is as opposed to the situation is discrete logic, where this only holds IIRC if the theory eliminates hyperimaginaries. So to put it another way continuous logic is better suited for studying hyperimaginaries in the sense that every theory, when considered as a continuous theory, eliminates hyperimaginaries.

EDIT3: With the help of Dap's answer to my question here I have finally convinced myself that it does always work for countably type-definable equivalence relations. The proof (especially the proof of uniform convergence) is difficult enough that I think it's worth writing down.

Proposition. If $T$ is a countinuous first-order theory and $P(x,y)$ is some definable predicate in $T$ such that $P$'s zeroset $[P]$ is an equivalence relation, then there is a definable pseudo-metric $\rho(x,y)$ in $T$ such that $[\rho]=[P]$ (i.e. $\rho$ and $P$ have the same zeroset).

Proof. By replacing $P(x,y)$ with $P(x,y) + P(y,x)$ we may assume that $P(x,y)=P(y,x)$. Also by scaling we may assume that $P(x,y)$ takes values in $[0,1]$.

Let $\varepsilon_0 = 1$. For each $k<\omega$, given $\varepsilon_k$, find $\varepsilon_{k+1}>0$ such that for any $x,y,z,w$, if $P(x,y),P(y,z),P(z,w) \leq \varepsilon_{k+1}$ then $P(x,w) < \varepsilon_k$. Such an $\varepsilon_{k+1}$ must exist by compactness, since $[P]$ is an equivalence relation. Also choose so that $\varepsilon_{k+1} < \frac{1}{2}\varepsilon_k$, which is clearly possible (this ensures that $\varepsilon_k \rightarrow 0$ as $k\rightarrow \infty$).

Now find a continuous, non-decreasing function $\alpha:[0,1]\rightarrow[0,1]$ such that $\alpha(\varepsilon_k)=2^{-k/2}$ for every $k<\omega$ (this is always possible). Let $Q(x,y)=\alpha(P(x,y))$.

Clearly $Q(x,x)=0$, $Q(x,y)=Q(y,x)$, and $0\leq Q(x,y) \leq 1$.

Claim: For any $x,y,z,w$, $Q(x,w) \leq 2 \max(Q(x,y),Q(y,z),Q(z,w))$.

Proof of claim: Pick $x,y,z,w$. Find $k<\omega$ maximal such that $\max(Q(x,y),Q(y,z),Q(z,w)) \leq 2^{-k/2}$. By construction this implies that $\max(P(x,y),P(y,z),P(z,w)) \leq \varepsilon_k$, so we also have $P(x,w) < \varepsilon_{k-1} $ if $k>0$ and $P(x,w)\leq 1$ if $k=0$ in any case. Therefore since $\alpha$ is non-decreasing we have that $Q(x,w) \leq 2^{-(k-1)/2}$ if $k>0$ and $Q(x,w) \leq 1$ if $k=0$. Since $k$ was chosen to be maximal, we have that $\max(Q(x,y),Q(y,z),Q(z,w)) > 2^{-(k+1)/2}$. Therefore $$Q(x,w) \leq 2^{-(k-1)/2} = 2\cdot 2^{-(k+1)/2} < 2\max(Q(x,y),Q(y,z),Q(z,w))$$ if $k>0$ and $$Q(x,w) \leq 1 < 2\cdot 2^{-1/2} < 2\max(Q(x,y),Q(y,z),Q(z,w))$$ if $k=0$.

So in any case $Q(x,w) \leq 2 \max(Q(x,y),Q(y,z),Q(z,w))$. End of proof of claim.

Let $Q_1(x,y)=Q(x,y)$ and for every $1<k<\omega$ let $$Q_k(x,y)=\inf_{z_1,\dots,z_{k-1}}Q(x,z_1)+Q(z_1,z_2)+\dots+Q(z_{k-1},y).$$ The predicate $Q(x,y)$ satisfies the conditions of my question, so by the results there the sequence $Q_k$ converges uniformly to some definable pseudo-metric $\rho(x,y)$ satisfying $\frac{1}{2} Q(x,y) \leq \rho(x,y) \leq Q(x,y)$. By this we have that $[\rho]=[Q]$ and clearly $[Q]=[P]$, so we have that $[\rho]=[P]$, as required. $\Box$

Now since any countable partial type is the zeroset of some definable predicate we get the required result for coutably definable hyperimaginaries in discrete theories.

EDIT2: There is a serious problem with this argument in the step regarding the amalgamation property, i.e. the amalgamation procedure described fails to work in all cases. If I can resolve this I'll post an edit.

EDIT: It's actually not even true for countable theories. Here is a counterexample.

Let $\mathcal{L}=\{P_i\}_{i<\omega}$ be a countable sequence of binary predicates and let $\Sigma$ be the $\mathcal{L}$-theory consisting of the following for each $i<\omega$:

• $\forall x P_i(x,x)$
• $\forall xy(P_i(x,y)\leftrightarrow P_i(y,x))$
• $\forall xyz(P_{i+1}(x,y)\wedge P_{i+1}(y,z) \rightarrow P_i(x,z))$

Note that these imply $\forall xy(P_{i+1}(x,y) \rightarrow P_{i}(x,y))$.

Let $E(x,y)$ be the partial type given by the formulas $\{P_i(x,y)\}_{i<\omega}$. It's clear that in any model of $\Sigma$, $E$ gives a type-definable equivalence relation.

Let $\mathcal{K}$ be the class of finite models of $\Sigma$. First of all I claim that this class contains only countably many isomorphism types. To see this note that for any $\mathfrak{A} \in \mathcal{K}$ and any $a,b\in \mathfrak{A}$, the quantifier free type of $ab$ is uniquely determined by the quantity $Q(x,y)=2^{-i}$ where $\mathfrak{A} \models P_i(x,y)\wedge \neg P_{i+1}(x,y)$ or $Q(x,y)=0$ if $\mathfrak{A} \models E(x,y)$. This has countably many values and the isomorphism type of a model of $\mathcal{K}$ is uniquely determined by the values of $Q$ on its pairs of elements.

Also since $\Sigma$ is a universal theory $\mathcal{K}$ is closed under substructures.

I claim that $\mathcal{K}$ has the amalgamation property. To see this let $\mathfrak{A}\subset \mathfrak{B}$ and $\mathfrak{A} \subset \mathfrak{C}$ with $\mathfrak{A}$, $\mathfrak{B}$, and $\mathfrak{C}$ all models of $\Sigma$. We can give an amalgamation $\mathfrak{D}$ whose universe is $B\cup C$ and where for any $b \in B \setminus A$ and $c \in C \setminus A$ we set $Q(b,c) = \min(1,2 \min_{a \in A}\max(Q(b,a),Q(a,c)))$. In other words we introduce only the $P_i$ relationships that are absolutely necessary according to $\Sigma$.

So we have that $\mathcal{K}$ is a Fraïssé class and we can find a Fraïssé limit $\mathfrak{F}$. Let $T=\mathrm{Th}(\mathfrak{F})$. Since the automorphism type of every finite tuple in $\mathfrak{F}$ is entirely determined by its quantifier free type and since every quantifier free type consistent with $T$ occurs in $\mathfrak{F}$, $T$ admits quantifier elimination.

Let $\mathcal{L}^\prime$ be a continuous language with a single binary $[0,1]$-valued predicate symbol $Q$. Interpret $\mathfrak{F}$ as an $\mathcal{L}^\prime$-structure $\mathfrak{F}^\prime$ using the definition of $Q$ given above. It's clear that $\mathfrak{F}$ and $\mathfrak{F}^\prime$ are interdefinable and more than that interdefinable in a quantifier free way. In particular I claim that $T^\prime = \mathrm{Th}(\mathfrak{F}^\prime)$ eliminates quantifiers in the sense of continuous logic. In particular this implies that the $2$-type of any pair $ab$ is entirely determined by the value of $Q(a,b)$. Also note that by construction we have that $\mathfrak{F} \models E(a,b)$ if and only if $\mathfrak{F}^\prime \models Q(a,b)$ (i.e. that it is $0$).

Let $\rho(x,y)$ be a $\varnothing$-definable $[0,1]$-valued pseudo-metric such that $\mathfrak{F} \models E(a,b)$ implies $\mathfrak{F}^\prime \models \rho(a,b)$. By quantifier elimination there must be some continuous function $\alpha:[0,1]\rightarrow[0,1]$ such that $\rho(x,y)=\alpha(Q(x,y))$. Now for each $i<\omega$ consider the finite $\mathcal{L}$-structure $\mathfrak{A}$ with $A=\{a,b,c\}$ such that $Q(a,b)=0$, $Q(a,c)=2^{-i}$, and $Q(b,c)=2^{-i-1}$. Note that the third axiom schema for $\Sigma$ translates to $Q(x,z)\leq 2 \max(Q(x,y),Q(y,z))$, so in particular $\mathfrak{A}$ is a model of $\Sigma$. Therefore it embeds into $\mathfrak{F}$ with some map $f:\mathfrak{A}\rightarrow \mathfrak{F}$. Since $Q(f(a),f(b))=0$ we must have that $\rho(f(a),f(b))=0$. Since $\rho$ is a pseudo-metric this implies that $\rho(f(a),f(c))=\rho(f(b),f(c))$. Therefore we have that $\alpha(2^{-i})=\alpha(2^{-i-1})$. Since this is true for any $i<\omega$, we have that $\alpha$ is constant on the set $\{2^{-i}\}_{i<\omega}$. It must be the case that $\alpha(0)=0$ since $\mathfrak{F} \models E(a,b)$ implies $\mathfrak{F}^\prime \models \rho(a,b)$, therefore by continuity $\alpha(r)=0$ for all $r\in[0,1]$ and $\rho$ is the trivial pseudo-metric. On the other hand $E$ is clearly a non-trivial equivalence relation because there is a finite model of $\Sigma$ in which there are two elements with $\neg E(a,b)$.

So we have a theory with a countably type-definable non-trivial equivalence relation (definable over $\varnothing$) in which the only $\varnothing$-definable pseudo-metric that is at least as coarse as it is the trivial pseudo-metric.

I'm not sure if allowing more parameters for the pseudo-metric can save it but I'm not very hopeful.

EDIT: It's actually not even true for countable theories. Here is a counterexample.

Let $\mathcal{K}$ be the class of finite models of $\Sigma$. First of all I claim that this class contains only countably many isomorphism types. To see this note that for any $\mathfrak{A} \in \mathcal{K}$ and any $a,b\in \mathfrak{A}$, the quantifier free type of $ab$ is uniquely determined by the quantity $Q(x,y)=2^{-i}$ where $\mathfrak{A} \models P_i(x,y)\wedge \neg P_{i+1}(x,y)$ or $Q(x,y)=0$ if $\mathfrak{A} \models E(x,y)$. This has countably many values and the isomorphism type of an model of $\mathcal{K}$ is uniquely determined by the values of $Q$ on its pairs of elements.

EDIT2: There is a serious problem with this argument in the step regarding the amalgamation property, i.e. the amalgamation procedure described fails to work in all cases. If I can resolve this I'll post an edit.

EDIT: It's actually not even true for countable theories. Here is a counterexample.

Let $\mathcal{K}$ be the class of finite models of $\Sigma$. First of all I claim that this class contains only countably many isomorphism types. To see this note that for any $\mathfrak{A} \in \mathcal{K}$ and any $a,b\in \mathfrak{A}$, the quantifier free type of $ab$ is uniquely determined by the quantity $Q(x,y)=2^{-i}$ where $\mathfrak{A} \models P_i(x,y)\wedge \neg P_{i+1}(x,y)$ or $Q(x,y)=0$ if $\mathfrak{A} \models E(x,y)$. This has countably many values and the isomorphism type of a model of $\mathcal{K}$ is uniquely determined by the values of $Q$ on its pairs of elements.