4
$\begingroup$

The following result holds for relational structures:

If $A$ is a countable structure, with an $\omega$−categorical theory $Th(A)$, that admits quantifier elimination, then $A$ is ultrahomogeneous.

I am looking for an algebraic counterexample. So: an algebraic structure with an $\omega-$categorical theory, that admits QE , but is not ultrahomogenous.

(Maybe some abelian group??)

Thank you for any help!

$\endgroup$

1 Answer 1

3
$\begingroup$

Think about the proof of this fact that you know for relational structures. Does it use the fact that the language is relational? If so, is this use essential?

When thinking about Fraïssé limits and ultrahomogeneous structures, the benefit to working in a finite relational language is that there are only finitely many possible quantifier-free types in $n$ variables for each $n$. When you move to a language with function symbols, this is no longer true, since a structure generated by $n$ elements can be arbitrarily large or even infinite. This is the main difference: there can be infinitely many quantifier-free types in $n$ variables for a fixed $n$. For this reason, working with a language with function symbols is very much like working with an infinite relational language.

To regain the benefits of a finite relational language, one often assumes uniform local finiteness: a finite bound on the size of substructures generated by $n$ elements will ensure only finitely many quantifier-free types in $n$ variables, as long as your language is finite.

However, if you assume $\aleph_0$-categoricity of the countable structure at the outset, then there are only finitely many complete types, hence only finitely many quantifier-free types! In this case, whether the language is finite or infinite or has function symbols or not is fairly irrelevant.

$\endgroup$
4
  • $\begingroup$ One more question, that is close related to that one: Is there an ultrahomogenous algebraic structure in a finite language, that is not $\omega$-categorical, hence doesn't admit QE? Because I also read that the result ultrahomogeneous + finite language $\Rightarrow$ $\omega-$categorical only holds in relational structures. But maybe in that case the function symbols are irrelevant aswell. $\endgroup$
    – Vicky
    Jul 18, 2014 at 18:20
  • $\begingroup$ Maybe a counterexample could be the Fra\"{i}ss\'{e}-limit of finite groups? (see: math.stackexchange.com/questions/88169/…) $\endgroup$
    – Vicky
    Jul 18, 2014 at 18:26
  • 1
    $\begingroup$ Consider the Fraïssé class of finitely generated (not finite) fields of characteristic $0$. The Fraïssé limit is the algebraic closure of $\mathbb{Q}$. This theory is not $\aleph_0$-categorical. However, it does have QE (you have your implication backwards: ultrahomogeneous and $\aleph_0$-categorical implies QE, but there's no reason why an ultrahomogeneous but not $\aleph_0$-categorical structure can't have QE! $\endgroup$ Jul 19, 2014 at 0:26
  • $\begingroup$ If you want an example of a structure in a finite language which is ultrahomogeneous but doesn't have QE, look at the edit I'm about to make to my answer to your question here. $\endgroup$ Jul 19, 2014 at 0:27

You must log in to answer this question.

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