Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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})$

share|cite|improve this question
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
up vote 7 down vote accepted

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)$.

share|cite|improve this answer
wow! as simple as sufficient, nice answer, thx – Sebastian Aug 15 '11 at 15:53
@Sebastian: I’ve added an answer to your first question. (I’m not sure whether you’re automatically informed of edits.) – Brian M. Scott Aug 16 '11 at 21:37
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
@Brian: Ok, then you gen an upvote :) – Levon Haykazyan Aug 17 '11 at 20:16

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.