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.
≈ 3 min read
Zero–one law (logic). encyclopegia.org, snapshot enwiki-001364147372. /a/zero-one-law-logic
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.