10
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

For the record, this lemma is proved in the lecture notes of Martin Otto on Finite Model Theory. I find it clear, short and self-contained.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.