On failure of 0-1 laws

2021/08/09 by Saharon Shelah, Shelah, Saharon
Computer Science · Mathematics · #03C13 #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #Logic, programming, and type systems

paper · pdf · doi:10.48550/arxiv.2108.03846

openalex publication_date 2021/08/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 inductive logic.

Related

• Failure of 0-1 law for sparse random graph in strong logics
• 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