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

633 Views Asked by At

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

1

There are 1 best solutions below

7
On BEST ANSWER

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

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