# Is for every ultrahomogenous structure M the theory Th(M) model complete?

A structure M is ultrahomogenous if every isomorphism between finitely generated substructures of M can be extended to an automorphism of M.

A theory is model complete if every embedding between models of the theory is elementary.

I can't think of any ultrahomogenous structure, which doesn't have a model complete theory. Is there such a structure?

Thank you!!

• Doesn't the theory of an ultrahomogeneous structure have quantifier elimination? Jun 30, 2014 at 18:36
• Do you want every isomorphism between any substructures to be extended to $M$ or just isomorphisms between substructures of cardinality $< |M|$? Jun 30, 2014 at 23:36
• I don't understand the downvotes... this is a good question. Jul 1, 2014 at 4:09
• @LevonHaykazyan and Vicky: The usual definition of ultrahomogeneous (as opposed to homogeneous or strongly homogeneous) is that every isomorphism between finitely generated substructures extends to an automorphism. Jul 1, 2014 at 4:09
• Thank you Alex, I corrected the definition. Jul 1, 2014 at 12:24

It is a standard result that every ultrahomogeneous structure in a finite relational language is $\aleph_0$-categorical and admits quantifier elimination, hence has a model complete theory. More generally, this holds whenever there are only finitely many quantifier-free $n$-types realized in $M$ for each $n\in \omega$, for example if the language is finite and the class of finitely generated substructures of $M$ is uniformly locally finite (see Theorem 6.4.1 in Hodges' A Shorter Model Theory).

However, the $\aleph_0$-categoricity, quantifier elimination, and model completeness can easily fail when there are infinitely many quantifier-free $n$-types realized in $M$ for some $n$, even in a relational language.

Example: Let $L$ be a language with two sorts, $X$ and $Y$. Let $\{P_i\subseteq X \mid i\in\mathbb{N}\}$ be a set of countably many unary relation symbols. Let $R\subseteq X\times Y$ be a binary relation.

Let $M$ be the following structure: The relations $P_i$ on $X^M$ pick out disjoint infinite sets, and there are also infinitely many elements which do not satisfy any $P_i$. For each of these elements not in any $P_i$, and only these elements, there is exactly one $y\in Y^M$ with $M\models R(x,y)$.

Now $M$ is obviously ultrahomogeneous. Finitely generated substructures are just finite subsets, and each of the sets picked out by the $P_i$ as well as the set $Y$ can be freely permuted (though any permutation of $Y$ must be mirrored by the elements of $X$ which are rigidly tied to $Y$ by $R$). The full types of tuples from $M$ are determined by their quantifier-free types, but the point is that the formula $\exists (y\in Y)\,R(x,y)$ is not equivalent to a single quantifier-free formula, but rather a conjunction of infinitely many.

Let $T = \text{Th}(M)$. By compactness, there is a countable model $N\models T$ containing an element in $X^N$ realizing the type $p(x) = \{\lnot P_i(x)\mid i\in\mathbb{N}\}\cup\{\lnot (\exists y\in Y)\,R(x,y)\}$.

But we can embed $N$ into a model $M'\cong M$ by simply adding one element $b_a$ to $Y$ for each element $a$ realizing $p(x)$, and setting $M'\models R(a,b_a)$ for each $a$. This embedding is not elementary, since if $a$ is some realization of $p$ in $N$, $N\models \lnot (\exists y\in Y)\,R(a,y)$, but $M'\models \exists (y\in Y)\,R(a,y)$.

Edit: If you want an example in a finite language (which must therefore have function symbols), you can adjust the example above as follows. Discard the symbols $P_i$, and add a unary function $f:X\rightarrow X$.

For each element $a$ of the sort $X$ in $M$, if $a$ used to satisfy $P_i$, replace $a$ by $i$ elements $\{a_1,\dots,a_i\}$, and set $f(a_j) = a_{j+1}$ for $j<i$ and $f(a_i) = a_1$.

On the other hand, if $a$ didn't satisfy any $P_i$, replace $a$ by infinitely many elements $\{a_i\mid i\in \mathbb{Z}\}$, and set $f(a_j) = a_{j+1}$ for all $j\in \mathbb{Z}$. Just as before, these are exactly the elements which are connected to the sort $Y$ by $R$. If you don't want any relations in the language, feel free to replace $R$ by a function $g:Y\rightarrow X$ (it's already a functional relation!).

Now in the argument above, just replace each instance of a predicate $P_i(x)$ with the formula $f^i(x) = x$.

• Thank you Alex! Very good example! Your structure doesn't admit quantifier elimination. How about an ultrahomogenous structure WITH qe but without model completeness? Do you think that's possible? Jul 1, 2014 at 12:13
• It's not possible: quantifier elimination implies model completeness! On the other hand, it might be possible to get an example which has model completeness but not QE... Jul 1, 2014 at 15:55
• Okay, I can get model completeness but not QE: Adjust the example so that for each $x$ not in any $P_i$, $x$ is attached to every $y$ in $Y$ by $R$. Now the formula $(\exists y\in Y)R(x,y)$ is equivalent to $(\forall y\in Y)R(x,y)$, and neither are equivalent to a quantifier-free formula (so no QE). But we can't flip the type $p$ on and off the way we could before: If an element $a$ realizes $p$, there is some (every) element of $y\in Y$ such that $\lnot R(a,y)$, and so $\lnot (\forall y\in Y)R(x,y)$ and hence $\lnot (\exists y\in Y)R(x,y)$ holds of $a$ in every extension. Jul 1, 2014 at 16:07
• yes that's what I meant! sorry. So if a structure has a model complete theory but doesn't admit qe, that means the universell part of the theory does not have the amalgamation property, right? (In: Chang & Keisler). Can you explain why your example doesn't have it? Jul 1, 2014 at 18:17
• Yes: Let $A$ be a structure with just one element, $a\in X$, $a$ satisfies no $P_i$. Let $B_1$ and $B_2$ be structures containing $A$. $B_1$ has a second element $b_1\in Y$ with $R(a,b_1)$. $B_2$ has a second element $b_2\in Y$ with $\lnot R(a,b_2)$. All three of these structures are substructures of models of $T$, hence they are models of $T_\forall$, but the embeddings of $A$ into $B_1$ and $B_2$ can't be amalgamated over $A$. Jul 1, 2014 at 18:27