Zero–one law (logic)

In mathematical logic, zero-one law is a property of a logic saying that any property is either almost surely true or almost surely false.

Uses your system voice; voice and rate in settings.

≈ 3 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In mathematical logic, zero-one law is a property of a logic saying that any property is either almost surely true or almost surely false. Zero-one law holds for first-order logic (without function symbols ), first-order logic extended with fixed point operators and first-order with infinite disjunctions and conjunctions. It does not hold for monadic second order logic.

As pointed out by Yuri Gurevich, zero-one law was proven for first-order logic by Yu. V. Glebskii, D. I. Kogan, M. I. Liogon'kii & V. A. Talanov and independently by Ronald Fagin. Any logic in which "being of size even" is expressible by a formula \varphi does not have the zero-one law.

Indeed, \mu_n(\varphi) = 1 if n is even and \mu_n(\varphi) = 0 if n is odd. And the sequence (1, 0, 1, 0, 1, 0, ...) does not converge.

Consider the first-order formula \varphi that says that there is an isolated vertex: \exists x \forall y \lnot E(x, y) . We have \mu_n(\varphi) \leq \frac{n \cdot 2^{\binom {n-1}2}}{2^{\binom n 2}} = \frac n {2^{n-1}} Indeed, first 2^{\binom {n}2} is the total number of graphs with exactly n vertices. Second, there are n choices for the isolated vertex, and 2^{\binom {n-1}2} ways to put edges on the remaining vertices.

Thus, n \cdot 2^{\binom {n-1}2} is an upper bound on the number of graphs with n vertices having an isolated vertex. Thus, \mu(\varphi) = 0 . First we introduce so-called extension axioms.

The extension axiom EA_{n, m} says that for any two disjoint subsets X and Y of respective cardinality n and m , there is a point z connected to any points in X , but no points in Y . We show that \mu(EA_{n, m}) = 1 . Second, via pebble games, they prove that if two finite graphs satisfy all the extension axioms EA_{n, m} with n, m \leq k , then they satisfy the same first-order formulas with at most k variables.

We can define the theory \textbf{EA} of all extension axioms. This theory is \omega -categorial, meaning that it has only one countable model up to isomorphism. It turns out that model is the Rado graph.

Thus, by Lowenheim-Skolem theorem, we can prove that \textbf{EA} is complete, meaning that for any sentence \varphi , either \varphi or \lnot \varphi is entailed by \textbf{EA} . As \textbf{EA} is recursive (we have an algorithm that tells whether a formula is an extension axiom or not), we can decide whether \varphi or \lnot \varphi is entailed by \textbf{EA} , which is equivalent to deciding whether \mu(\varphi) = 1 or \mu(\varphi) = 0 .

Moreover this problem has been shown to be PSPACE-complete.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1364147372 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001364147372 · captured 2026-07-14 · ledger · version history

Cite this page as: encyclopegia.org, “Zero–one law (logic)”, snapshot enwiki-001364147372. https://encyclopegia.org/a/zero-one-law-logic

Sources cited in this revision

6 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.