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
    @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
    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