5
$\begingroup$

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!!

$\endgroup$
5
  • $\begingroup$ Doesn't the theory of an ultrahomogeneous structure have quantifier elimination? $\endgroup$
    – Asaf Karagila
    Jun 30, 2014 at 18:36
  • $\begingroup$ Do you want every isomorphism between any substructures to be extended to $M$ or just isomorphisms between substructures of cardinality $< |M|$? $\endgroup$ Jun 30, 2014 at 23:36
  • 2
    $\begingroup$ I don't understand the downvotes... this is a good question. $\endgroup$ Jul 1, 2014 at 4:09
  • $\begingroup$ @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. $\endgroup$ Jul 1, 2014 at 4:09
  • $\begingroup$ Thank you Alex, I corrected the definition. $\endgroup$
    – Vicky
    Jul 1, 2014 at 12:24

1 Answer 1

5
$\begingroup$

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$.

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – Vicky
    Jul 1, 2014 at 12:13
  • 1
    $\begingroup$ 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... $\endgroup$ Jul 1, 2014 at 15:55
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 1, 2014 at 16:07
  • $\begingroup$ 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? $\endgroup$
    – Vicky
    Jul 1, 2014 at 18:17
  • 1
    $\begingroup$ 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$. $\endgroup$ Jul 1, 2014 at 18:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .