Proving an logical identity for the zero one laws

102 Views Asked by At

With identity I mean that there is an equivalent statement. With logicall I mean that this statement deals with EF-games.

I want to prove that

A function $p(n)\in [0,1]$ satisfies the Zero one laws iff for every first order logical statement $A$ over the signature for graphs $\lim_{n\rightarrow\infty}Pr[((G,n,p(n)))\models A]=1 \vee 0$

I want to show now that

A function satisfies the zero one laws iff for every $t,G(n,p(n)),H(m,p(m)):\lim_{m,n\rightarrow\infty}Pr[\texttt{Duplicator wins EHR[G,n,p(n),H(m,p(m)),t]}]=1$

$\Leftarrow$ is proved in the book (proof Theorem 10.7.4). How can I prove the other direction?

hh zz qq