# The connection between quantifier elimination, $\omega$-categorical and ultrahomogenous

A relational structure $A$ with an $\omega-$categorical theory $Th(A)$ is ultrahomogenous iff $Th(A)$ admits quantifier elimination. (*)

I was wondering wether the structure $A$ has to be countable...

Think of the following example:

We have the set $A= (0,1)_\mathbb Q \cup (1,2)_\mathbb{R}$ and one binary relation $<$ (the linear order). I think $A$ admits quantifier elimination, is $\omega-$categorical (because the theory is that of a dense linear order) but NOT ultrahomogenous as $\mathbb{Q}$ and $\mathbb{R}$ are not isomorph.

What do you think?

Thank you in advance for any help!

Supplement

I haven’t had much time to do modeltheory the last weeks, but today I tried to proof the other direction of *. And I would appreciate some help again!

Claim: If a countable structure $A$ has an $\omega$-categorical theory and admits QE, then it is ultrahomogeneous.

Proof: Assume $Th(A)$ admits quantifier elimination, $\bar{a}, \bar{b} \in A^n$ and $f: \bar{a} \mapsto \bar{b}$ is an isomorphism. We have to show: there exists an automorphism $f’$ so that $f'(\bar{a}) = \bar{b}$.

As $Th(A)$ is $\omega-$categorical and admits QE, there exists a quantifier-free formular $\varphi(\bar{x})$, that isolates tp($\bar{a}$). And because of the isomorphism $f$ we get: $A \models \varphi( \bar{b})$, hence tp($\bar{a}$)=tp($\bar{b}$). At this point I don't know how to argue, that whenever two n-tuples have the same complete type, there exists an automorphism between them. Do you have an idea? Thank you!

• Since the supplement is really a new question, it's better to ask it as a new question. Especially since this question already has an accepted answer - there's no guarantee that anyone will notice your edit. (Of course, I've been rather obsessively answering model theory questions on this site recently, but hopefully that won't always be the case!) Aug 3, 2014 at 19:13
• But since I'm here: The property of a model $M$ that you're looking for is called $\omega$-strongly homogeneous. That is, whenever $\overline{a}$ and $\overline{b}$ are finite tuples in $M$ and $\text{tp}(\overline{a}) = \text{tp}(\overline{b})$, then there is an automorphism of $M$ moving $\overline{a}$ to $\overline{b}$. It's true that all countable atomic models are $\omega$-strongly homogeneous, as are all countable saturated models, as are all countable models of $\omega$-categorical theories (being both atomic and saturated). Aug 3, 2014 at 19:16
• These facts follow easily from Theorem 2.3.3 and Theorem 2.3.9 in Chang and Keisler after adding some constants into the language ($(M,\overline{a})\equiv (M,\overline{b})$, so they're isomorphic). Aug 3, 2014 at 19:21

You're right, the theorem is only true with the additional hypothesis that $A$ is countable.

In your example, the structure $A$ is not ultrahomogeneous, because the $2$-element substructure $\{\frac{1}{3},\frac{2}{3}\}$ is isomorphic to the $2$-element substructure $\{\frac{4}{3},\frac{5}{3}\}$, but this isomorphism doesn't extend to an automorphism of $A$, since the interval $(\frac{1}{3},\frac{2}{3})$ is countable, while the interval $(\frac{4}{3},\frac{5}{3})$ is uncountable.

In response to your comment: The converse holds even for uncountable structures. However, the notion of ultrahomogeneity is really most relevant for countably infinite structures.

Claim: If a structure of any cardinality is ultrahomogeneous and has an $\aleph_0$-categorical theory, then it admits quantifier elimination.

Proof: Let $M$ be our ultrahomogeneous structure. It suffices to show that whenever two tuples $\overline{a}$ and $\overline{b}$ in any model of $T$ realize the same quantifier-free type, they realize the same complete type. Suppose not, so we have $\overline{a}$ and $\overline{b}$ in some model $N$ with $p(\overline{x}) = \text{tp}(\overline{a}) \neq q(\overline{x}) = \text{tp}(\overline{b})$, but $\text{tp}^\text{qf}(\overline{a}) = \text{tp}^\text{qf}(\overline{b})$.

But $\aleph_0$-categoricity of $T$, there are only finitely many formulas in $n$ free variables up to equivalence, so every type is isolated (equivalent to a formula). Hence $p$ and $q$ are realized in $M$, say by $\overline{a}'$ and $\overline{b}'$. But now $\overline{a}'$ and $\overline{b}'$ realize the same quantifier-free type, so they generate isomorphic substructures of $M$, and by ultrahomogeneity, there is an automorphism of $M$ moving $\overline{a}'$ to $\overline{b}'$. Hence $\text{tp}(\overline{a}) = \text{tp}(\overline{b})$, contradiction.

• What about the other direction? Is there an uncountable ultrahomogenous structure with $\omega-$categorical theory, that doesn't admit qe? Jul 1, 2014 at 20:20
• Thank you! Your proof is very clear. One more question: Is the cardinality of the language important? Jul 2, 2014 at 8:43
• No. Note that if a theory in an uncountable language is $\aleph_0$-categorical, there are only finitely many formulas in $n$-free variables for each $n$, hence only countably many atomic formulas in any number of variables, so the theory proves that the language is equivalent to a countable one. Jul 2, 2014 at 18:35