4
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ 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!) $\endgroup$
    – Alex Kruckman
    Aug 3, 2014 at 19:13
  • 1
    $\begingroup$ 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). $\endgroup$
    – Alex Kruckman
    Aug 3, 2014 at 19:16
  • $\begingroup$ 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). $\endgroup$
    – Alex Kruckman
    Aug 3, 2014 at 19:21

1 Answer 1

Reset to default
4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ What about the other direction? Is there an uncountable ultrahomogenous structure with $\omega-$categorical theory, that doesn't admit qe? $\endgroup$
    – Vicky
    Jul 1, 2014 at 20:20
  • $\begingroup$ Thank you! Your proof is very clear. One more question: Is the cardinality of the language important? $\endgroup$
    – Vicky
    Jul 2, 2014 at 8:43
  • $\begingroup$ 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. $\endgroup$
    – Alex Kruckman
    Jul 2, 2014 at 18:35

You must log in to answer this question.

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