# How can i prove that the theory of random graph has a vaughtian pair?

I'm searching for theories that have a vaughtian pair. I've been given a hint, that $T_{RG}$ has at least one. I have also found many theorems stating in which cases a theory has no vaughtian pair, but none the other way round.

1) Can you give me a (short) proof?

2) Do you know other theories that have a vaughtian pair (with(out) proof)?

Definition of a vaughtian pair: T has a Vaughtian pair if there are two models $\mathfrak{M} \prec \mathfrak{N}$ and an L(M)-formula $\phi(x)$ such that: $\mathfrak{M} \neq \mathfrak{N}$, $\phi(\mathfrak{M})$ is infinite and $\phi(\mathfrak{M}) = \phi(\mathfrak{N})$

-
By $\phi(\mathfrak M)$ do you mean $\{x\in\mathfrak M\mid \mathfrak M\models\phi(x)\}$? – Asaf Karagila Aug 13 '11 at 19:35
@Asaf: Yes.${}{}{}$ – Brian M. Scott Aug 13 '11 at 19:57

For (2), Peano arithmetic has a Vaughtian pair. Take $\mathfrak{M}$ and $\mathfrak{N}$ to be non-standard models such that $\mathfrak{N}$ is a proper elementary end-extension of $\mathfrak{M}$, fix an infinite $c \in M$, and let $\varphi(x)$ be $x<c$.

It took a while, but I think that I can now answer the first question as well. Let $G = \langle V,E \rangle$ be the random graph. Fix a vertex $v_0 \in V$, and let $V_0 = V \setminus \{v_0\}$. The partition property of the random graph ensures that $G_0 \triangleq G[V_0]$, the subgraph induced by $V_0$, is isomorphic to $G$, so $G_0 \prec G$ as models of $T_{RG}$, since $T_{RG}$ is model-complete. (Model-completeness follows, for example, from Theorem 3.1.12 in C.C. Chang & H. Jerome Keisler, Model Theory. In fact $T_{RG}$ even admits quantifier elimination.)
Fix any vertex $v_1 \in V_0$ such that $\{v_0,v_1\} \notin E$, and let $\varphi(x)$ be $R(x,v_1)$, where $R$ is the symbol for the edge relation in the language of $T_{RG}$. Then the infinitely many vertices satisfying $\varphi(x)$ are all in $V_0$, so $\varphi(G_0) = \varphi(G)$.
The fact that $G_0$ is isomorphic to $G$ does not ensure $G_0 \prec G$. For example $\mathbb Z$ is isomorphic to $2\mathbb Z$ in a language containing only $+$. But $\exists x (x + x) = 2$ is true in the first structure, but false in the second. – Levon Haykazyan Aug 17 '11 at 12:28
@Levon: In this case it does: $T_{RG}$ is model-complete. But I should have said so, and I’ve edited the answer accordingly. – Brian M. Scott Aug 17 '11 at 19:31