7
$\begingroup$

Classical (i.e., discrete) logic is well positioned to study imaginaries in part because the $T^{eq}$ construction allows us to treat imaginary sorts as we would treat any other sort. With hyperimaginaries, on the other hand, classical logic has no such luck. The ability to apply a $T^{eq}$-like construction to the study of hyperimaginaries motivated, in part, the study of positive model theory, a thematic precursor to the modern approach to continuous logic.

Despite that history, I've been unable to convince myself that continuous logic's $T^{eq}$ construction, when applied to a classical theory, includes sorts for the classical hyperimaginaries (even finitary ones) in the case of an uncountable theory. (The $T^{eq}$ construction I'm using is the one that adds canonical parameters for continuous logic formulas, such as in Chapter 11 of Model Theory for Metric Structures.)

Folklore as I've heard it says that the construction does include all the classical finitary hyperimaginaries, but I've been unable to find a citation for that fact, and haven't yet produced a clear proof or counterexample. Can anyone point me in the right direction?

$\endgroup$
4
$\begingroup$

In general a $T^{eq}$ construction in continuous logic, as it's typically defined, can only possibly add hyperimaginaries corresponding to equivalence relations defined by countable partial types. If you consider the uncountable discrete theory $T$ with unary predicates $P_i$ for each $i<\omega_1$ where for each pair of disjoint finite sets $X,Y\subset \omega_1$ $T$ contains an axiom $\exists x\bigwedge_{i\in X}P_i(x)\wedge \bigwedge_{i\in Y} \neg P_i(x)$. Then if you look at the type definable equivalence relation $E(x,y)=\{P_i(x) \leftrightarrow P_i(y) : i<\omega_1\}$ the hyperimaginary where you quotient out by $E$ is not equivalent to any continuous imaginary of $T$, because any continuous formula is definable over some countable set of $P_i$'s.

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.


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.

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.

$\endgroup$

Your Answer

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