Random Graph: Stronger logic but with the zero one law
Saharon Shelah · arXiv (Cornell University) · 2015
We find a logic really stronger than first order for the random graph with edge probability $\frac 12$ but satisfies the 0-1 law. This means that on the one hand it satisfies the 0-1 law, e.g. for the random graph ${\mathcal G}_{n,1/2}$ and on the other hand there is a formula $φ(x)$ such that for no first order $ψ(x)$ do we have: for every random enough ${\mathcal G}_{n,1/2}$ the formulas $φ(x),ψ(x)$ equivalent in it.