# On proving the zero-one-law for first order logic

I'm trying to understand the proof of the zero-one-law for first order logic as provided in (Ebbinghaus-Flum, 1995). It goes as follows:

Let $\tau$ be a relational signature. Let $r\in\mathbb{N}$, then $\Delta_{r+1}=\{\phi(v_1,\ldots,v_r,v_{r+1})\mid\phi\text{ has the form }R\bar x\text{, where }R\in\tau\text{ and where }v_{r+1}\text{ occurs in }\bar x\}$. For $\Phi\subseteq\Delta_{r+1}$, we say the extension axiom of $\Phi$ is: $$\chi_\Phi=\forall v_1\ldots\forall v_r(\bigwedge_{1\leq i<j\leq r}v_i\neq v_j\rightarrow \exists v_{r+1}(\bigwedge_{1\leq i\leq r} v_i\neq v_{r+1}\wedge\bigwedge_{\phi\in\Phi}\phi\wedge\bigwedge_{\phi\in\Phi^c}\neg\phi)).$$ Now they prove

Lemma. Any extension axiom $\chi_{\Phi}$ holds in almost all finite structures, i.e. $l(\chi_\Phi)=\lim_{n\rightarrow\infty} \frac{L_n(\chi_\Phi)}{L_n(\tau)}=\lim_{n\rightarrow\infty}\frac{|\{\mathcal{A}\mid\mathcal A\models\chi_\Phi\wedge|A|=\{1,\ldots,n\}\}|}{|\{\mathcal A\mid|A|=\{1,\ldots,n\}\}|}=1$.

Proof. Given $\Phi$. For any tuple $a_1,\ldots,a_r$ of distinct elements in a structure $\mathcal A$ and any further object $a$ let $\delta$ be the probability that $a_1,\ldots,a_r,a$ satisfies $\Phi\cup\{\neg\phi\mid \phi\in\Phi^c\}$, when adding $a$ to $\mathcal A$ as a new element and randomly fixing the truth values of $R\bar b$ for any $R\in\tau$ and any sequence $\bar b$ in $A\cup\{a\}$ containing $a$. Clearly, if $c$ is the number of subsets of $\Delta_{r+1}$, $\delta=\frac1c$.

Until here I understand everything, but I don't understand the following derivation:

$$l_n(\neg\chi_\Phi)=l_n(\exists v_1\ldots\exists v_r(\ldots))\leq n^r(\tfrac{c-1}c)^{n-r}=n^r(1-\delta)^{n-r}.$$

I don't understand where the expression just after the inequality comes from, could someone explain this?

Update. I have found this article, in which they seem to prove a special case of the lemma above (see the proof of Lemma 0.3, (b) $\Rightarrow$ (c)). I'm still not fully able to make the generalisation to this case, could someone explain this?

Update II. By replacing $\frac1{2^2k}$ by $\frac1c$ in the above article, and thinking some more about the arguments in 1. and 2., I have been able to prove the lemma.

Update III. The replacement part in my last update wasn't really clear to me at that moment. I now have been able to fully prove it: Since we can choose our relations arbitrarily, for a relation $R\in\tau$ and a sequence of variables $\bar x$ of the right size, the probability of $R\bar x$ to hold equals $\tfrac12$. So in total there are $$\left(\dfrac12\right)^{\|\Delta_{r+1}\|}$$ sequences $v_1,\ldots,v_r,v_{r+1}$ in $\{1,\ldots,n\}$ that realise $\psi_\Phi$. If now $c$ is the amount of subsets of $\Delta_{r+1}$, then $c=2^{\|\Delta_{r+1}\|}$, and filling that in in my original proof, finally proves the lemma.