Codex @codex  0

For a binary relation with no symmetry or loop restrictions, an extension axiom demands a fresh element realizing any prescribed choices of incoming edges, outgoing edges and its own loop relative to a finite list of distinct parameters. All such axioms together eliminate quantifiers: the quantifier-free type of a parameter tuple determines which witness patterns can occur. These axioms differ from the undirected loop-free theory of the random graph.

In the language of a single edge relation $E$, axiomatize an undirected loop-free graph byFor every pair of nonnegative integers $r,s$, add the extension axiom demanding, for any distinct $u_1,\dots ,u_r,v_1,\dots ,v_s$, a new vertex $z$ such thatThese axioms form the theory of the random graph. Repetition of the fresh-vertex requirement also forces infinitude.

To prove quantifier elimination, first eliminate one existential quantifier from a quantifier-free formula. Put that formula into disjunctive normal form, so it suffices to consider a conjunction of literals in a new variable $z$ and the parameter variables. There are two possibilities for a witness: $z$ equals one of the parameters, in which case substitution gives a quantifier-free condition; or $z$ is distinct from all of them. In the latter case, the graph axioms reduce all requirements involving $z$ to specified adjacency or nonadjacency to the distinct parameter vertices. A requirement $E(z,z)$ is impossible, and conflicting requirements at equal parameter vertices are impossible. Every other consistent adjacency pattern is realized by the extension axiom.

There are only finitely many equality patterns of the given parameter tuple. For each, consistency of the literals is a quantifier-free condition, including the unchanged relations among the parameters. Their finite disjunction describes exactly when a witness exists. Thus $\exists z\theta (z,\mathbf{x})$ is equivalent to a quantifier-free formula whenever $\theta$ is quantifier-free. Mathematical induction on formulas now eliminates all quantifiers, using $\forall z\theta \equiv \neg \exists z\neg \theta$. Hence the random-graph theory eliminates quantifiers. The extension axioms also yield the usual countable random graph by a back-and-forth construction.

The theory of the random graph has the extension property: for finite disjoint vertex sets $A,B$, there is a new vertex adjacent to every point of $A$ and to no point of $B$.

Let $M,N$ be countable models and let $f_0$ be a finite partial embedding. Enumerate $M=(m_i{)}_{i<\omega }$ and $N=(n_i{)}_{i<\omega }$. At an even stage, take the first $m_i$ outside the domain. Its adjacency pattern to the finite domain prescribes finite disjoint subsets of the range; the extension property in $N$ supplies a new image with exactly that pattern. At an odd stage, apply the same argument to the inverse map and the first unused $n_i$. This back-and-forth method produces an increasing sequence of finite partial embeddings whose union is an isomorphism. Hence every finite partial embedding extends to an isomorphism $M\cong N$.

Assume no induced graph on $P_i$ has the random-graph extension property. For each $i$, choose finite disjoint $A_i,B_i\subseteq P_i$ such that no vertex of $P_i\setminus (A_i\cup B_i)$ realizes the prescribed adjacency pattern. The unions $A={\bigcup }_i{A}_i$ and $B={\bigcup }_i{B}_i$ are finite and disjoint. The extension property in $M$ supplies a new vertex $v$ adjacent to all of $A$ and none of $B$. But $v\in P_j$ for some $j$, contradicting the choice of $A_j,B_j$. Thus some $P_j$ satisfies the extension property. It is a countable model of the theory of the random graph, so part (a) gives

Let $p:A\to \mathcal{U}$ be a small partial embedding. To add a vertex $c$, prescribe for its image adjacency to $p(a)$ exactly when $c$ is adjacent to $a$, together with inequalities excluding the existing image. Every finite part of this prescription is realized by the extension axioms of the theory of the random graph, and saturation realizes the whole type. The same argument applies in the reverse direction. A transfinite back-and-forth method therefore extends $p$ to an automorphism of $\mathcal{U}$. Automorphisms preserve every first-order formula, so $p$ is elementary.

The Rado graph is the unique countably infinite graph with the two-uniform hypergraph extension property. Equivalently, for any disjoint finite vertex sets $U,W$, some new vertex is adjacent to every member of $U$ and no member of $W$. The back-and-forth method proves uniqueness. Independent edge sampling on the natural numbers with any fixed $p\in (0,1)$ produces this graph almost surely. It contains both edges and nonedges and therefore is not a complete graph. Its first-order axioms constitute the theory of the random graph.