Definable subsets of the random graph.

Question

Let $T_{rg}$ be the theory of the random graph, denote with $r$ the binary relation which makes its language. I have two questions which both regard definability.

1. Let $N\models T_{rg}$ and $A\subset N$. Let $\phi(x)\in L(A)$ be a first order formula with a single free variable and parameters from $A$. Show that: $$|\phi(N)|<\infty\rightarrow \phi(N)\subset A$$ where $\phi(N)=\{b\in N\ |N\models\phi(b)\}$.

2. Let $M_1,M_2\models T_{rg}$ and let $M=M_1\sqcup M_2$ be the graph obtained by considering the disjoint union of vertex and edges in $M_i$. Show that $M \nvDash T_{rg}$ and find a first order formula $\psi(x,y)$ such that $M\models\psi(a,b)$ if and only if $a,b$ are in the same connected component.

For the first point I think that one can solve the problem if $A$ is finite. In fact if it was $\phi(N)\subsetneq A$ one can easily find a partial automorphism which extends to an automorphism fixing $A$ but not $\phi(N)$. This would be a contradiction. The fact is we do not have such an hypothesis: is it right to restrict to this case since $\phi$, being a first order formula, will only mention a finite numbers of parameters? Otherwise what I would try to do is to show that $$|\phi(N)|<\infty\rightarrow\ \phi(x)=\ 'x=a_1\lor\cdots\lor x=a_n' $$ for some $a_1,...,a_n\subset A$. In this direction, the only thing I managed to observe is that $\forall a\in A$ the defined set $r(a,N)$ is an isomorphic copy of the random graph, hence infinite. This seems to suggest that any formula defining a finite subset of $N$ should not involve $r$, but I have no clue of how to make this precise.

For the second problem, I think I have to exploit the fact $M_i$ are random graph to translate in a first order form the following formula, which is obviously not first order, but $L_{\omega\infty}$ in general: $$\psi(x,y)=\lor_{k=1}^{\infty}\exists x_1\cdots\exists x_k\ (r(x,x_1)\wedge r(x_i,x_{i+1})\wedge r(x_k,y))$$ Again, I am a bit clueless.

Thanks in advance

Answer 1

1. The general case easily reduces to the case when $A$ is finite. Let $A'\subseteq A$ be the finite set of parameters used in $\phi$. Now apply your argument to show that if $|\phi(N)|$ is finite, then $\phi(N)\subseteq A'\subseteq A$. Another comment: Your argument implicitly assumes $N$ is countable, when you extend a partial automorphism to a total automorphism. To handle an arbitrary model of the theory of the random graph (which may not be so homogeneous), you can apply your argument in a countable elementary submodel which contains $A'$.

2. You're on the right track - now you just have to observe that the random graph has diameter $2$.