= Solution
Use the <Rado graph> on the <natural numbers>. Interpret the binary relation by
$$
\boxed{E(i,j)\quad\Longleftrightarrow\quad
[i<j\land\mathit{Bit}(i,j)]\lor[j<i\land\mathit{Bit}(j,i)].}
$$
The relation is symmetric by its definition, and $E(i,i)$ is always false. Thus this <first-order structure> satisfies $F_1$ and $F_2$.
To verify an extension axiom, take distinct $x_1,\ldots,x_n$. Choose a <natural number> $k$ larger than every $x_i$ and put
$$
y=2^k+\sum_{i=1}^{m-1}2^{x_i}.
$$
The powers are distinct, so there are no carries in this <binary representation>. In particular $y>x_i$ for every $i$, and the <bit> in position $x_i$ is one exactly when $i<m$. Therefore $y$ is different from all the given <vertices>, is adjacent to $x_1,\ldots,x_{m-1}$, and is not adjacent to the others. If the $x_i$ are not distinct, the antecedent of the extension axiom is false, so it places no restriction. The case $n=0$, if included in the convention for <natural numbers>, simply asks for a nonempty domain, which this <first-order structure> has.
For example, prescribing adjacency to $1$ and $3$ and nonadjacency to $2$ permits $k=4$ and $y=16+2+8=26$, whose <binary representation> is $11010$. This explicitly realizes the required pattern. Hence
$$
\boxed{(\mathbb N,E)\models T_0.}
$$
Reordering a tuple makes the extension axioms applicable to any two disjoint finite sets of <vertices>, with any desired adjacency and nonadjacency pattern. This is the extension property defining the <theory of the random graph>.
Back to article page
