Zero-One Laws

Origin. Glebskii, Kogan, Liogon'kii, and Talanov (1969) in the Soviet literature and Ronald Fagin, "Probabilities on finite models" (Journal of Symbolic Logic, 1976), independently. Compton, Kolaitis, and Vardi extended the subject through the 1980s and 90s; Shelah and Spencer (1988) settled the sparse random-graph case.

Models. Take a first-order sentence about graphs and ask what fraction of graphs on n vertices satisfy it, as n grows. The answer is always 0 or 1 — never ½, never oscillating, never anything else. First-order logic cannot express any property of finite structures that is asymptotically borderline, which is simultaneously a striking fact about probability and a sharp limit on expressive power.

Formalism.

The asymptotic probability: μ_n(φ) = |{structures on {1..n} satisfying φ}| / |{structures on {1..n}}| μ(φ) = lim_{n→∞} μ_n(φ), when it exists.

The theorem (Glebskii et al., Fagin): For every first-order sentence φ over a relational vocabulary, μ(φ) exists and is 0 or 1.

The proof — extension axioms: E_{k,l}: for any k distinct elements and any prescribed pattern, there is another element related to them exactly as prescribed. Each E_{k,l} has asymptotic probability 1. T = the theory of all extension axioms is complete and ℵ₀-categorical. Its unique countable model is the Rado graph (the random graph). So φ or ¬φ is in T; whichever is has probability 1. First-order logic cannot tell the finite structures apart from the random graph.

Where it fails: MSO: "the number of vertices is even" is MSO-expressible and has no limit. FO with a linear order: parity again. So the law is a statement about unordered relational structures, and order breaks it.

Where it holds beyond FO (Kolaitis–Vardi): Fixed-point logic (LFP) has a 0-1 law. Infinitary logic L^ω_∞ω with finitely many variables has one. So the law is not about first-orderness but about a bounded-variable property.

Shelah–Spencer (1988): For G(n, p) with p = n^{-α}: the 0-1 law holds iff α is irrational. Rational α gives sentences with no limiting probability. The sparse regime is where the phenomenon becomes delicate.

Convergence vs 0-1: A convergence law says μ(φ) exists; a 0-1 law says it is 0 or 1. Some logics and measures have the first without the second.

Symbols.

Metatheory. The mechanism is that first-order logic's asymptotic theory is the theory of the Rado graph, which is ℵ₀-categorical and complete — so the logic sees the same thing at every large finite size, and probability has nowhere to land but 0 or 1. That is why order breaks the law: order gives the logic a way to count, and counting is what parity needs. Kolaitis and Vardi's extension to fixed-point and bounded-variable infinitary logic locates the real cause — it is the bounded-variable property, not first-orderness, and the 0-1 law is a corollary of a pebble-game argument. The Shelah–Spencer result shows the phenomenon is a knife edge: shift the density by an irrational exponent and it holds, by a rational one and it fails.

Applies to. Finite model theory and descriptive complexity, where 0-1 laws are the standard inexpressibility tool. Random graph theory. Database theory, where the law says a first-order query is almost always true or almost always false on random data. Any argument that a property is not first-order definable — exhibit a sentence with no limit.

Limitations. The law is a statement about the uniform measure on unordered structures, and almost every application of logic to finite structures assumes an order — so the theorem is sharpest exactly where it does not apply. It gives inexpressibility results only for properties with oscillating probability, which excludes most properties one wants to prove undefinable. And the asymptotic framing says nothing about any particular structure: a sentence of probability 1 may fail on every graph anyone will ever look at.

© 2026 Lingenic LLC