Definition 12.4 (Rado graph). Let $L=\{E\}$, with $E$ a binary relation. A Rado or Random graph is a graph $(V,E)$ such that $V\ne \varnothing$ and for any finite disjoint $X,Y\subseteq V$ there is some $v\in V$ such that:

• $E(v,x)$ for all $x\in X$

• $\neg (v,y)$ for all $y\in Y$

We denote the theory of Rado graphs as $RC$. It consists of

• Graph axioms (irreflexive and symmetric).

• For any $k\ge 1$ and $l\ge 1$,

  $$\forall x_1,\dots ,x_k,\forall y_1,\dots ,y_l\left(\underset{i,j}{\wedge }{x}_i\ne y_j\to \exists v\left(\underset{i,j}{\wedge }E(v,x_i)\wedge \neg E(v,y_j)\right)\right).$$