Definability of subgraphs of random graphs

Question

I'm new to model theory and I'm trying to solve this problem.

Let $N$ and $M\subseteq N$ random graphs, is there a $\phi \in L(N)$ (where $L(N)$ is the language of graphs with a constant symbol for each element of $N$) such that $\phi$ defines $M$ for every such $M$? In other words, is $M$ definable with parameters in $N$?

I don't have any clue. I noticed that I can't use an atomic formula of the form $\phi(a,x)$ with $a$ parameter, so I was thinking the answer is no and trying of use the fact that every automorphism send definable sets with parameters in definable sets with parameters to find a contradiction, but I'm not sure of this method. Do you have any suggestion?

Answer 1

If $N$ is a random graph (countable) then it is a fact that for any finite partition of $N$ at least one of the members of the partition is a random graph (with induced graph structure). Since there are continuum many partitions in say two sets, there are continuum many subgraphs of $N$ which are random. On the other hand there are only countably many formulae in $L(N)$. Therefore, not every random $M\subseteq N$ is definable.

Answer 2

As an alternative to SMM's argument, you can construct a non-definable elementary substructure of the random graph by directly diagonalizing against formulas. This strategy has the advantage of also working for other Fraïssé limits which do not satisfy the property about finite partitions in SMM's answer.

Let $(\varphi_n(x,a_n))_{n\in \omega}$ enumerate the $L(N)$-formulas with the property that the subgraph they define is an isomorphic copy of the random graph. We will build two sequences of finite sets $(A_n)_{n\in \omega}$ and $(B_n)_{n\in \omega}$ such that $A_n\subseteq A_{n+1}$, $B_n\subseteq B_{n+1}$, and $A_n\cap B_n = \varnothing$ for all $n$. The idea is that we want ensure that the union of the $A_n$ is an isomorphic copy of the random graph, by throwing in witnesses to the extension axioms, while at the same time ensuring that it's not defined by any formula. We do this by putting "blocking" elements into $B_n$, one for each formula. Start with $A_n = B_n = \emptyset$.

Now suppose we're given $A_n$ and $B_n$. If $X$ and $Y$ are disjoint subsets of $A_n$, there is some $a\in N\setminus B_n$ (because $B_n$ is finite) such that $a$ is has an edge to every element of $X$ and has no edge every element of $Y$. Pick such an element $a$, which we call an extension witness for $X$ and $Y$. Let $A_{n+1}$ be $A_n$ together with an extension witness for every pair of disjoint subsets of $A_n$. Then $A_{n+1}$ is finite, because there are only finitely many such pairs. Now look at the formula $\varphi_n(x,a_n)$. Because it defines an isomorphic copy of the random graph, in particular it defines an infinite set, and there is some $b$ such that $N\models \varphi_n(b,a_n)$ and $b\notin A_{n+1}$. Let $B_{n+1} = B_n\cup \{b\}$.

By induction, we've defined $A_n$ and $B_n$ for all $n$. Let $M = \bigcup_{n\in \omega} A_n$, and note that $M$ is disjoint from $B_\infty = \bigcup_{n\in \omega} B_n$. Also $M$ is an isomorphic copy of the random graph, because it satisfies all extension axioms. But on the other hand, $M$ is not defined by any formula $\varphi_n(x,a_n)$. This is because for any such formula, there is some element $b\in B_\infty$ such that $N\models \varphi_n(b,a_n)$, and $b\notin M$.