Random Graph: Stronger logic but with the zero one law

2015/11/17 by Shelah, Saharon
#03C13 #FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.1511.05383

Abstract

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.

Related

• Failure of 0-1 law for sparse random graph in strong logics
• On failure of 0-1 laws
• Zero-one laws for k-variable first-order logic of sparse random graphs
• Extension of zero-one k-law
• Hereditary Zero-One Laws for Graphs