Quantifier elimination in uncountable elementary "Fraïssé classes"

Question

Let $\mathcal{L}$ be an infinite relation language (this question is trivial in a finite relational language). Suppose that $\mathcal{K}$ is the class of finite models of some $\mathcal{L}$-theory (since we're only concerned with finite models this is equivalent to saying that for each $n$ the class of structures in $\mathcal{K}$ of size $n$ is closed under ultraproducts). Furthermore suppose that $\mathcal{K}$ satisfies all of the properties of Fraïssé classes, except for the countability requirement, i.e. it satisfies the hereditary property, the joint embedding property, and the amalgamation property. Call such a class an uncountable elementary Fraïssé class.

Despite the fact that $\mathcal{K}$ does not in general have a unique countable generic structure associated to it, there is still a unique generic theory $T_\mathcal{K}$ associated to it which is formally analogous to the theory of a Fraïssé limit. If $\mathcal{L}$ is countable this theory can be described indirectly in terms of a game:

Let $X$ be a set of complete $\mathcal{L}$ theories. Player I picks a structure $\mathfrak{A}_0 \in \mathcal{K}$. Then the players alternate picking $\mathfrak{A}_{i+1}\supseteq \mathfrak{A}_i$ with $\mathfrak{A}_{i+1} \in \mathcal{K}$. Player II wins if $\mathrm{Th}\left(\bigcup_{i<\omega} \mathfrak{A}_i\right) \in X$ and player I wins otherwise.

$T_\mathcal{K}$ is the unique theory such that player II has a winning strategy when $X=\{T_\mathcal{K}\}$. Equivalently, $T_\mathcal{K}$ is the unique theory such that player II has a winning strategy if and only if $T_\mathcal{K} \in X$ and player I has a winning strategy if and only if $T_\mathcal{K} \notin X$. For an uncountable language this describes $T_\mathcal{K}$ 'locally' in each countable reduct of $\mathcal{L}$. (There might be a subtlety here in that the game needs to be played with structures in the full language and only victory is checked in the countable reduct.)

A more set theoretical way of constructing $T_\mathcal{K}$ is to force to make $\mathcal{K}$ countable. Then in the forcing extension $\mathcal{K}^V$ literally is a Fraïssé class and has a unique Fraïssé limit. You can show that the theory of this structure is independent of the generic, so in particular it's definable in the ground model. I think this should be basically the same as treating the normal construction of a Fraïssé limit as a forcing poset and building a generic model in some extension.

A less set theoretical but essentially equivalent way to get $T_\mathcal{K}$ is to construct an appropriate Kripke frame out of $\mathcal{K}$. Namely nodes are indexed by finite chains of members of $\mathcal{K}$ ordered by end extension. Each index $p = \{\mathfrak{A}_i\}_{i\leq n}$ has as an associated structure $\mathfrak{A}_n$. Then you argue that for any index $p = \{\mathfrak{A}_i\}_{i\leq n}$, any $\overline{a} \in \mathfrak{A}_n$, and any formula $\varphi(\overline{x})$, $p \Vdash \varphi(\overline{a})$ only depends on the isomorphism type of $\mathfrak{A}_n$, so that we can sensibly write $\mathfrak{A} \Vdash \varphi(\overline{a})$.

Then you argue that for any sentence $\varphi$, and any $\mathfrak{A},\mathfrak{B} \in \mathcal{K}$, if $\mathfrak{A} \Vdash \neg \varphi$ then $\mathfrak{B} \Vdash \neg \varphi$ (this follows from JEP alone). Furthermore for any sentence $\varphi$, by definition every $\mathfrak{A} \in \mathcal{K}$ either has $\mathfrak{A} \Vdash \neg \varphi$ or has an extension $\mathfrak{B} \supseteq \mathfrak{A}$ such that $\mathfrak{B} \Vdash \varphi$ and so a fortiori $\mathfrak{B} \Vdash \neg \neg \varphi$. Together these imply that for any sentence $\varphi$, either for every $\mathfrak{A} \in \mathcal{K}$, $\mathfrak{A}\Vdash \neg \varphi$ or for every $\mathfrak{A} \in \mathcal{K}$, $\mathfrak{A}\Vdash \neg \neg \varphi$. This implies that there is a unique consistent complete classical theory $T_\mathcal{K}$ whose double negation translation is forced by every node of the frame.

(As an aside this last construction of $T_\mathcal{K}$ only depends on the fact that $\mathcal{K}$ has JEP, so in particular the notion of $T_\mathcal{K}$ makes sense for any class of structures with the joint embedding property. The set theoretical argument gives you a generic model of $T_\mathcal{K}$ but in general this model is not going to be unique in the forcing extension, so you need to do more work to see that the theory is unique. This whole question was partially inspired by conversations with Noah Schweber relating to this fact and this question of his, although that question is concerned with structures rather than theories. I'm broadly curious about what is known about the theory $T_\mathcal{K}$ for arbitrary classes with JEP and would appreciate any references.)

---

Questions

I'm interested in the question of how 'nice' $T_\mathcal{K}$ is and more generally what's known about these theories. In particular I'm wondering

If $\mathcal{K}$ is an uncountable elementary Fraïssé class, does $T_\mathcal{K}$ admit quantifier elimination?

Recall that Fraïssé limits in finite relational languages always admit quantifier elimination. I have an idea for a (bad) proof of this but it has a couple holes: We pass to a forcing extension $V[G]$ in which $\mathcal{K}$ and $\mathcal{L}$ are countable. There we construct $\mathfrak{M}$, the Fraïssé limit of $\mathcal{K}^V$. I want to say that because $\mathcal{K}$ is an elementary class, $\mathfrak{M}$ is computably saturated (hole #1). This structure is homogeneous for quantifier free types, i.e. for any two tuples $\overline{a}$ and $\overline{b}$, if $\overline{a}$ and $\overline{b}$ have the same quantifier free type, then there is an automorphism taking $\overline{a}$ to $\overline{b}$. In general this property for a single model is not enough to witness that the theory has quantifier elimination but I want to say that if the model is computably saturated then this implies the theory has quantifier elimination (hole #2). Then quantifier elimination is absolute so it holds for $T_\mathcal{K}$ in the ground model as well.

Part of the problem is that all of the examples I can think of look something like this: Let $\mathcal{L}=\{E_i\}_{i<\omega}$ where each $E_i$ is a binary relation. Consider the class $\mathcal{K}$ of finite $\mathcal{L}$-structures in which each $E_i$ is a graph, but no other relations are imposed. The 'Fraïssé limit' of this is the 'random $2^\omega$-colored graph.' The theory of this structures does admit quantifier elimination but this is because it can be 'approximated' by finite reducts which are themselves bona fide Fraïssé limits. So every finite reduct of the theory admits quantifier elimination and therefore the whole theory does as well. So a related question is whether or not this always happens (and I seriously doubt it does but I don't know a counterexample):

If $\mathcal{K}$ is an uncountable elementary Fraïssé class, does there always exist a directed set $R \subseteq \mathcal{P}\mathrm(\mathcal{L})$ of sub-languages such that $\bigcup R = \mathcal{L}$ and for every $\mathcal{L}_0 \in R$, $T_\mathcal{K} \upharpoonright \mathcal{L}_0$ is the theory of a Fraïssé limit? Can the languages be required to be finite?

I suspect that by picking a carefully chosen subclass of the above $\mathcal{K}$ (or something similar) you can find an example showing that if $\mathcal{K}^\prime$ is not elementary then $T_{\mathcal{K}^\prime}$ may not have QE, but I haven't worked out an example yet.

EDIT: Here's a relatively simple counterexample when the class in question is not elementary. Let $\mathfrak{N}$ be the structure $(\mathbb{N},+,\cdot)$ where $+$ and $\cdot$ are taken as ternary relations. Also add predicates $P_n(x)$ such that $\mathfrak{N} \models P_n(a)$ if and only if $a=n$. Note that $\mathrm{Th}(\mathfrak{N})$ does not admit quantifier elimination. Let $\mathcal{K}_N$ be the class of finite substructures of $\mathfrak{N}$. Clearly the generic theory is just going to be $\mathrm{Th}(\mathfrak{N})$, which doesn't admit quantifier elimination. Strictly speaking this is a countable class, but we can make it 'uncountable Fraïssé class' by tacking on $2^\omega$-colored graphs: $\mathcal{K}_N^\prime$ is a class of structures in a language containing $+$, $\cdot$, $P_n$, $U$, and $E_n$. If $\mathfrak{A} \in \mathcal{K}_N^\prime$ then $U(\mathfrak{A})$ is a structure in the class $\mathcal{K}_N$ and $\neg U(\mathfrak{A})$ is a $2^\omega$-colored graph with edge relations among $E_n$. Now this is an uncountable Fraïssé class whose limiting theory does not admit quantifier elimination.

Answer 1

I'm thinking that a certain choice of "generalized metric space" should accomplish this, but it depends on if the "generic theory" ends up right.

First I'll describe the general setup. Let $S$ be a fixed subset of $\mathbb{Q}^{\geq 0}$. Assume $0\in S$. Let $L$ be a language with a binary relation symbol $d_s(x,y)$ for all $s\in S$. Any metric space has a canonical interpretation as an $L$-structure where $d_s(x,y)$ is "$d(x,y)\leq s$".

Let $\mathcal{K}$ be the class of finite metric spaces with distances in $S$. (This may not be the finite models of an elementary class. I'll get to this later.) Delhomme, LaFlamme, Pouzet, and Sauer showed that $\mathcal{K}$ is a Fraisse class if and only if for any $s_1,s_2,s_3,s_4\in S$, if there is some $t\in S$ such that $\{s_1,s_2,t\}$ and $\{s_3,s_4,t\}$ are "metric triangles" (i.e., any combination satisfies the triangle inequality), then there is some $u\in S$ such that $\{s_1,s_3,u\}$ and $\{s_2,s_4,u\}$ are metric triangles. In other words, this describes the amalgamation of two triangles $\{s_1,s_2,t\}$ and $\{s_3,s_4,t\}$ over the common distance $t$. In this case, we say that $S$ satisfies the four-values condition, and let $T$ be the theory of the Fraisse limit of $\mathcal{K}$.

Now I claim that there is a choice of $S$ so that $T$ does not have QE. Set $S:=([2,3)\cup(3,\infty))\cap\mathbb{Q}$. It can be checked that $S$ satisfies the four-values condition (cutting $S$ off below at $2$ is needed for this). We show that $T$ does not have quantifier elimination. Let $\varphi(x_1,x_2;y)$ be the formula $d_2(x_1,y)\wedge\neg d_5(x_2,y)$. Consider the types: $$ p(x_1,x_2)=\{d_s(x_1,x_2):s>3\}\cup\{\neg d_s(x_1,x_2):s<3\} $$ $$ p_1(x_1,x_2)=p(x_1,x_2)\cup\{\exists y\varphi(x_1,x_2;y)\} $$ $$ p_2(x_1,x_2)=p(x_1,x_2)\cup\{\neg\exists y\varphi(x_1,x_2;y)\} $$ We show that $p_1$ and $p_2$ are both consistent. Suppose $\pi(x_1,x_2)$ is some finite subset of $p_0(x_1,x_2)$. Let $s_1=\max\{s:\neg d_s(x_1,x_2)\in \pi\}$ and $s_2=\min\{s:d_s(x_1,x_2)\in \pi\}$. Then the metric space $\{a_1,a_2,b\}$ such that $d(a_1,a_2)=s_2$, $d(a_1,b)=2$, and $d(a_2,b)=2+s_2$ witnesses the consistency of $\pi(x_1,x_2)\cup\{\exists y\varphi(x_1,x_2;y)\}$. On the other hand, the metric space $\{a'_1,a'_2\}$, where $d(a'_1,a'_2)$ is an element of $S$ strictly between $s_1$ and $3$, witnesses that $\pi(x_1,x_2)\cup\{\neg\varphi(x_1,x_2;y)\}$ is consistent.

For most "reasonable" choices of $S$ (e.g., $S=\mathbb{Q}^{\geq 0}$), if $T$ exists then it has QE. But QE can be ruined by poking "holes" in $S$ like in the previous example.

---

Now I will discuss how to get a class of finite models of a theory. Let $S$ be arbitrary again (not necessarily satisfying four-values). Let $T_0$ be the universal theory consisting of:

• $\forall x\forall y(d_0(x,y)\leftrightarrow x=y)$
• for all $s\in S$, $$ \forall x\forall y(d_s(x,y)\leftrightarrow d_s(y,x)) $$
• for all $r,s,t\in S$ such that there is no $x\in S$ satisfying $t<x\leq r+s$, $$ \forall x\forall y\forall z((d_r(x,y)\wedge d_s(y,z))\rightarrow d_t(x,z)) $$
• if $S$ has a maximal element $s$, add $\forall x\forall y d_s(x,y)$.

We view $T_0$ as the theory of metric spaces with distances in $S$. Clearly, any metric space with distances in $S$ is a model of $T_0$ (using the interpretation as an $L$-structure described above). But the converse is not necessarily true. What is true is that any model of $T_0$ is a "generalized metric space" whose distances come from an ordered algebraic structure $\mathcal{S}^*$ containing $S$ (technically it's an ordered commutative magma). More precisely, $\mathcal{S}^*$ is a structure $(S^*,\oplus,\leq,0)$ where $(S^*,\leq,0)$ is a linear order with least element $0$, $\oplus$ is a commutative binary operation, which is weakly monotonic in $\leq$, and $S\subseteq S^*$. The order $(S^*,\leq,0)$ is constructed in two steps:

1. Extend $(S,\leq,0)$ to $(S^+,\leq,0)$ by adding a new symbol $s^+$ for any (non-maximal) $s\in S$ with no immediate successor in $S$, and order $s^+$ so that it is the immediate successor of $s$.
2. Extend $(S^+,\leq,0)$ to $(S^*,\leq,0)$ by adding a new symbol for any Dedekind cut in $S^+$.

The binary operation $\oplus$ is more annoying to describe explicitly. Instead, one can see that $S^*$ is naturally in bijection with the set of quantifier-free $2$-types (over $\emptyset$) consistent with $T_0$. Specifically, given $\alpha\in S^*$, we have $$ p_\alpha(x,y)=\{d_s(x,y):s\in S,\alpha\leq s\}\cup\{\neg d_s(x,y):s\in S,s<\alpha\} $$ Then, given $\alpha,\beta\in S^*$, $\alpha\oplus\beta$ is the supremum over the set of $\gamma\in S^*$ such that $p_\alpha(x,y)\cup p_\beta(y,z)\cup p_\gamma(x,z)$ is consistent with $T_0$. One can show that $\oplus$ extends $+$ on $S$ wherever it is defined.

Now there is a natural notion of an $\mathcal{S}^*$-metric space, and any $\mathcal{S}^*$-metric space is a model of $T_0$. Conversely, if $M\models T_0$ then for any $a,b\in M$ there is a unique $\alpha\in S^*$ such that $p_\alpha(a,b)$ holds, and setting $d(a,b)=\alpha$ defines an $\mathcal{S}^*$-metric on $M$.

Now let $\mathcal{K}^*$ be the class of finite models of $T_0$, i.e., finite $\mathcal{S}^*$-metric spaces. Then, by essentially the same argument from Delhomme, Laflamme, Pouzet, and Sauer, one can show that if $S$ satisfies the four-values condition then $\mathcal{K}^*$ is a Fraisse class. In fact, for many choices of $S$ (including the non-QE example above), the four-values condition is equivalent to associativity of $\oplus$ in $\mathcal{S}^*$. This is the key thing needed to generalize the usual amalgamation of metric spaces to metric spaces with distances in these kinds of "ordered magmas".

I would hope that the "generic theory" you've described is the same theory $T$ from above, but I haven't checked this. So we should be able to take the same non-QE set $S$ above. Note that, in this case, $\mathcal{S}^*$ is already uncountable and so $\mathcal{K}^*$ is uncountable.