Countable structure with qe and not ultrahomogeneous

Question

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

I gave an example of an uncountable structure, that is not ultrahomogeneous but has quantifier elimination. Now I am looking for a countable (relational) structure with qe but not ultrahomog. Of course the structure can't be $\omega$-categorical. And we need an infinite signature.

I think I have to look for a structure, where I can find two n-tuples $\bar{a} \bar{b}$, that have the same type, but there is no automorphism carrying $\bar{a}$ to $\bar{b}$. (And then I add a new predicate to the language for each formula that is valid to get qe). But I don't know how to construct such structure. Maybe you could help.. Thank you!!

Answer 1

(I finally post my comment as an answer. I encourage you to continue working on your own counterexample, post it and accept it, so that you can make your own intuition on what happens.)

Let us consider the structure whose domain is $\mathbb Z \times\{0,1\}$, with a countable number of binary relation symbols $<_p$ ($p\in\mathbb Z$) whose interpretation in the structure is $\{((a,0),(b,0))\mid a<b+p\}\cup\{((a,1),(b,1))\mid a<b+p\}\cup\{((a,0),(b,1))\mid a,b\in\mathbb Z\}$.

This structure has quantifier elimination, and $(0,0)$ and $(0,1)$ have the same type (because there is only one $1$-type). However, an automorphism $\alpha$ of this structure maps any $(a,1)$ to a $(b,1)$ in the same copy, for we have $(0,0)<_p (a,1)$ for all $p\in\mathbb Z$, so that $\alpha(0,0) <_p \alpha(a,1)$ for all $p\in\mathbb Z$ and this is only possible if $\alpha(a,1)\in\mathbb Z\times\{1\}$. Thus no automorphism maps $(0,1)$ to $(0,0)$, and the structure is not homogeneous.

Answer 2

Consider two disjunct copies of the ordered natural numbers $(\mathbb{N}, \leq)$ and $(\mathbb{N^\star}, \leq^\star)$. Then we add a disjunct copy of the ordered integers $(\mathbb{Z}', \leq ')$ on top of $(\mathbb{N}, \leq)$.

So the domain of our structure $\mathcal{A}$ is: $A= \mathbb{N} \cup \mathbb{N}^\star \cup \mathbb{Z}'$, with $\mathbb{N} \cap \mathbb{N}^\star = \mathbb{Z}' \cap \mathbb{N} = \mathbb{Z}' \cap \mathbb{N}^\star = \emptyset$ and the signature $L$ consists of one binary relation symbol $R := \leq^\star \cup \leq^*$, whereas $\leq^* := \leq \cup \leq' \cup (\mathbb{N} \times \mathbb{Z'})$.

Now we know, that the type $p(x)= \lbrace R(n,x) x| n\in \mathbb{N} \rbrace$ is not realised in ($\mathbb{N}, \leq$), but it is realised in $\mathcal{A}$ (because: $ \mathcal{A} \models p(0')$ for $0' \in \mathbb{Z'}$). And we know, that $(\mathbb{N}, \leq)$ is an elementary substructure of $\mathcal{A}$. It follows that $p(x)$ can't be isolated in $\mathcal{A}$ as isolated types are realised in elementary substructures.

The two elements $0^\star \in \mathbb{N}^\star$ and $0 \in \mathbb{N}$ have the same type (as the theories $Th(\mathbb{N^\star}, R)$ and $Th(\mathbb{N} \cup \mathbb{Z'}, R)$ are elementary equivalent) but because of the non-isolated type $p(x)$ there is no automorphism $f$ with $f(0) = 0^\star$. Hence $\mathcal{A}$ is not ultrahomogenous.

To get quantifier elimination we finally add for each formula $\varphi$ in n free variables with $\mathcal{A} \models \varphi$ an $n$-ary relationsymbol to the signature.