Failure of 0-1 law for sparse random graph in strong logics

2017/06/05 by Shelah, Saharon
#03B48 #03C13 #05C80 #FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.1706.01226

Abstract

Let α∈(0,1)_ℝ be irrational and G_n = G_n, 1/n^α be the random graph with edge probability 1/n^α; we know that it satisfies the 0-1 law for first order logic. We deal with the failure of the 0-1 law for stronger logics: \mathbbL _{∞, k}, k large enough and the LFP, least fix point logic.

Related

• On failure of 0-1 laws
• Random Graph: Stronger logic but with the zero one law
• Zero-one laws for k-variable first-order logic of sparse random graphs
• Hereditary Zero-One Laws for Graphs
• Universal Zero-One k--Law