Notes - Logic and Proof MT24, Rado graph

The $\sigma$-theory axiomatised by the sentences

\[\begin{aligned} F_1& : \exists x \exists y \lnot(x=y) \\\\ F_2& : \forall x \lnot R(x, x) \\\\ F_3& : \forall x \forall y(R(x, y) \to R(y, x)) \\\\ \\\\ H_{m,n}&: \forall x_1 \cdots \forall x_m \forall y_1 \cdots \forall y_n \left( \left(\bigwedge^m_{i=1} \bigwedge^n_{j=1} \lnot(x_i = y_j)\right) \to \exists z \bigwedge^m_{i = 1}R(x_i, z) \land \bigwedge^n_{j = 1}\lnot R(y_j, z) \right) \end{aligned}\]

• $F _ 1$ says that every vertex is distinct
• $F _ 2$ says that there are no self-loops
• $F _ 3$ says that for every two disjoint collections of vertices $\{x _ 1, \ldots, x _ m\}$ and $\{y _ 1, \ldots, y _ n\}$, there exists some vertex that’s connected to every vertex in the first set, but not to any vertex in the second.

Let $N > n+m$ and pick some tuples $\pmb a = (a _ 1, \ldots, a _ m)$, $\pmb b = (b _ 1, \ldots, b _ n)$ drawn from the set $\{1, \ldots, N\}$.

Claim: For a graph $G$ drawn uniformly at random from $\pmb G _ N$,

\[\mathbb P\left( G \not\models \exists z \left( \bigwedge^m_{i = 1}E(a_i, z) \land \bigwedge^n_{j = 1} E(b_j, z)\right) \right) \le q^{N - m - n}\]

where

\[q := 1 - 2^{-n-m} < 1\]

Proof: For each possible choice $c$ from

\[\\{1, \ldots, N\\} \setminus \\{a_1, \ldots, a_m, b_1, \ldots, b_m\\}\]

the probability

\[G \not\models \bigwedge^m_{i = 1} E(a_i, c) \land \bigwedge^n_{j = 1} E(b_j, c)\]

is at most $q$. Since these are independent events for the $N - m - n$ choices of $c$, the claim follows.

Proof of original statement: Take the union bound ($\mathbb P(\bigcup A _ n) \le \sum \mathbb P(A _ n)$) over the $N^{n+m}$ possible choices of $a _ 1, \ldots, a _ m, b _ 1, \ldots, b _ n \in \{1, \ldots, N\}$. We have that

\[\mathbb P_N(\lnot H_{m,n}) \le N^{n+m} q^{N-n-m}\]

Since $q < 1$, $\lim _ {N \to \infty} \mathbb P _ N(H _ {m,n}) = 1$.

For every $\sigma$-formula $\varphi$ the limit $\lim _ {N \to \infty} \mathbb P _ N(\varphi)$ exists and is either zero or one, and $\pmb T _ {RG} = \{\varphi : \lim _ {N \to \infty} \mathbb P _ N(\varphi) = 1\}$.

Since $\pmb T _ {RG}$ is complete, it suffices to show that

\[\lim_{N \to \infty} \mathbb P_N(\varphi) = 1\]

for every $\varphi$ in $\pmb T _ {RG}$.

By the compactness theorem for first-order logic, there exist $m, n \in \mathbb N$ such that $\{F _ 1, F _ 2, F _ 3, H _ {m,n}\}$ entails $\varphi$. Hence $\mathbb P _ N(\varphi) \ge \mathbb P _ N(H _ {m,n})$ which entails $\lim _ {N \to \infty} \mathbb P _ N(\varphi) = 1$.

@todo, once have done sheet 3.