3
$\begingroup$

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

  • 0
    By $\phi(\mathfrak M)$ do you mean $\{x\in\mathfrak M\mid \mathfrak M\models\phi(x)\}$?2011-08-13
  • 0
    @Asaf: Yes.${}{}{}$2011-08-13

1 Answers 1

8

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

Added:

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

  • 0
    wow! as simple as sufficient, nice answer, thx2011-08-15
  • 0
    @Sebastian: I’ve added an answer to your first question. (I’m not sure whether you’re automatically informed of edits.)2011-08-16
  • 0
    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.2011-08-17
  • 0
    @Levon: In this case it does: $T_{RG}$ is model-complete. But I should have said so, and I’ve edited the answer accordingly.2011-08-17
  • 0
    @Brian: Ok, then you gen an upvote :)2011-08-17
  • 0
    definitely an upvote, Thank you Brian2011-08-18
  • 0
    I would've argued like this: prove that $G_0\models{RG}$, since $RG$ is complete, by vaught's test, $G_0$ and $G$ satisfy the same sentences, and since $RG$ has quantifier elimination, using induction on formulas, one can prove from all of this that $G_0\prec{G}$2012-10-29