Past exam of the mathematics course of the University of Cambridge / 2002 / iii / Paper 23 / 9 / a / Solution

For an unrestricted binary relation $R$, the extension axioms permit arbitrary directed edges and loops. For each $m\ge 0$ and each choice of bits ${ϵ}_i,{\delta }_i,\eta \in \{0,1\}$, require that every tuple of distinct $x_1,\dots ,x_m$ has a fresh element $y$ withHere $P^1$ denotes $P$ and $P^0$ denotes $\neg P$; the notation is a literal abbreviation, not exponentiation of a relation. Incoming and outgoing choices are independent, and the loop bit is also specified. These are the extension axioms for an unrestricted binary relation. If one instead restricts to undirected loop-free graphs, the allowable patterns reduce to the random-graph extension axioms of Question 2; no such restriction is imposed here.