2
$\begingroup$

Is there an $\omega$-categorical theory without quantifier elimination? The way I normally prove $\omega$-categoricity (with back-and-forth) immediately gives me QE as a corollary of the test Theorem 13.7 (see picture).

QE test

My definition of local isomorphism is:

Definition of local isomorphism

$\endgroup$
5
  • 1
    $\begingroup$ You should probably include the definition of "local isomorphism" in your question as well, because I do not think this is really a standard definition. At least, I think it is easily confused with a partial elementary map (which it is not). $\endgroup$
    – Mark Kamsma
    Jun 20, 2019 at 15:58
  • $\begingroup$ @MarkKamsma I've added my working definition. What is your definition? $\endgroup$
    – Ibrahim
    Jun 20, 2019 at 16:57
  • $\begingroup$ Personally I know these notes, so I knew what this definition was. It's just that most people might expect it to mean "partial elementary embedding", which is the same definition but then it should preserve all formulas. This is really something different: we can always extend a partial elementary embedding (on a set of cardinality $<\kappa$) into a $\kappa$-saturated structure by one more element (exercise!) $\endgroup$
    – Mark Kamsma
    Jun 20, 2019 at 17:01
  • $\begingroup$ @MarkKamsma The exercise is a lemma in the notes :) . If I had not known it by heart I would surely be a good exercise, so thanks! I didn't know Benno's notes were in use in Utrecht. But now that I think about it, it makes a lot of sense. $\endgroup$
    – Ibrahim
    Jun 20, 2019 at 18:29
  • 1
    $\begingroup$ They weren't, I just followed a few courses at the UvA ;) $\endgroup$
    – Mark Kamsma
    Jun 20, 2019 at 18:51

1 Answer 1

Reset to default
2
$\begingroup$

One example is the theory of an equivalence relation with infinitely many classes of size $1$ and infinitely many classes of size $2$.

Another example is the theory of an infinite graph with a single edge.

$\endgroup$
3
  • $\begingroup$ That is a lot easier than I thought! The crucial observation is that for back-and-forth you can choose the order of extension, whereas in the test you cannot. I missed that. $\endgroup$
    – Ibrahim
    Jun 20, 2019 at 18:33
  • $\begingroup$ @AlexKruckman Theorem. Let $T$ be omega-categorical and let $M$ be the countable model of $T$. $M$ is homogeneous iff $Th(M)$ has Q.E. An infinite graph with a single edge is homogeneous, isn't it? $\endgroup$
    – Alice.H
    Jun 8, 2021 at 7:16
  • 1
    $\begingroup$ @Alice.H No, it's not homogeneous. Let $v$ be an endpoint of the single edge, and let $w$ be any element which is not an endpoint of the single edge. Then the substructures $\{v\}$ and $\{w\}$ are isomorphic, but there is no automorphism of the model moving $v$ to $w$. $\endgroup$
    – Alex Kruckman
    Jun 8, 2021 at 12:05

You must log in to answer this question.

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