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.
Principle
In this article, to keep it simple, we talk about graphs instead of considering arbitrary structures. Given a sentence
φ
{\displaystyle \varphi }
in some logic, we define
μ
n
(
φ
)
{\displaystyle \mu _{n}(\varphi )}
to be the proportion of graphs that satisfy
φ
{\displaystyle \varphi }
among the graphs with exactly
n
{\displaystyle n}
vertices. We say that a logic has the zero-one law if
μ
n
(
φ
)
{\displaystyle \mu _{n}(\varphi )}
converges to 1 or 0, for any sentence
φ
{\displaystyle \varphi }
of that logic. We set
μ
(
φ
)
{\displaystyle \mu (\varphi )}
to be that limit to which
μ
n
(
φ
)
{\displaystyle \mu _{n}(\varphi )}
converges when
n
{\displaystyle n}
grows to infinity.
Examples
We give the examples given in p. 236.
Even
Any logic in which "being of size even" is expressible by a formula
φ
{\displaystyle \varphi }
does not have the zero-one law. Indeed,
μ
n
(
φ
)
=
1
{\displaystyle \mu _{n}(\varphi )=1}
if
n
{\displaystyle n}
is even and
μ
n
(
φ
)
=
0
{\displaystyle \mu _{n}(\varphi )=0}
if
n
{\displaystyle n}
is odd. And the sequence
(
1
,
0
,
1
,
0
,
1
,
0
,
.
.
.
)
{\displaystyle (1,0,1,0,1,0,...)}
does not converge.
2
(
n
−
1
2
)
2
(
n
2
)
=
n
2
n
−
1
{\displaystyle \mu _{n}(\varphi )\leq {\frac {n\cdot 2^{\binom {n-1}{2}}}{2^{\binom {n}{2}}}}={\frac {n}{2^{n-1}}}}
2
(
n
−
1
2
)
{\displaystyle n\cdot 2^{\binom {n-1}{2}}}
is an upper bound on the number of graphs with
n
{\displaystyle n}
vertices having an isolated vertex. Thus,
μ
(
φ
)
=
0
{\displaystyle \mu (\varphi )=0}
.
First-order logic
In this section, we consider first-order logic without function symbols. Note that with function symbols, zero-one law may fail. For instance, the formula
p
(
c
)
{\displaystyle p(c)}
where
c
{\displaystyle c}
is a constant symbol (i.e. a function symbol of arity 0) would be true half of the times.
Statement
First-order logic has the zero-one law. The main ingredients of the proof presented in (their proof is about first-order logic with infinite conjunctions and disjunctions but the idea is similar) are the following.
First we introduce so-called extension axioms. The extension axiom
E
A
n
,
m
{\displaystyle EA_{n,m}}
says that for any two disjoint subsets
X
{\displaystyle X}
and
Y
{\displaystyle Y}
of respective cardinality
n
{\displaystyle n}
and
m
{\displaystyle m}
, there is a point
z
{\displaystyle z}
connected to any points in
X
{\displaystyle X}
, but no points in
Y
{\displaystyle Y}
. We show that
μ
(
E
A
n
,
m
)
=
1
{\displaystyle \mu (EA_{n,m})=1}
.
Second, via pebble games, they prove that if two finite graphs satisfy all the extension axioms
E
A
n
,
m
{\displaystyle EA_{n,m}}
with
n
,
m
≤
k
{\displaystyle n,m\leq k}
, then they satisfy the same first-order formulas with at most
k
{\displaystyle k}
variables.
Decidability
We can define the theory
EA
{\displaystyle {\textbf {EA}}}
of all extension axioms. This theory is
ω
{\displaystyle \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
EA
{\displaystyle {\textbf {EA}}}
is complete, meaning that for any sentence
φ
{\displaystyle \varphi }
, either
φ
{\displaystyle \varphi }
or
¬
φ
{\displaystyle \lnot \varphi }
is entailed by
EA
{\displaystyle {\textbf {EA}}}
. As
EA
{\displaystyle {\textbf {EA}}}
is recursive (we have an algorithm that tells whether a formula is an extension axiom or not), we can decide whether
φ
{\displaystyle \varphi }
or
¬
φ
{\displaystyle \lnot \varphi }
is entailed by
EA
{\displaystyle {\textbf {EA}}}
, which is equivalent to deciding whether
μ
(
φ
)
=
1
{\displaystyle \mu (\varphi )=1}
or
μ
(
φ
)
=
0
{\displaystyle \mu (\varphi )=0}
. Moreover this problem has been shown to be PSPACE-complete.
Other logics
The following logics have the zero-one law:
First-order logic (as seen above)
First-order logic
L
∞
ω
ω
{\displaystyle L_{\infty \omega }^{\omega }}
with infinite conjunctions and disjunctions (see Theorem 12.2 in )
First-order logic with least fixed-point operators, first-order logic with inflationary fixed-point operators, with partial fixed-point operators (see Corollary 12.3 in )
∃
S
O
(
∃
∗
∀
∗
)
{\displaystyle \exists SO(\exists ^{*}\forall ^{*})}
(see Theorem 12.12 in )
∃
S
O
(
∃
∗
∀
∃
∗
)
{\displaystyle \exists SO(\exists ^{*}\forall \exists ^{*})}
(see Theorem 12.15 in )
First-order logic on grids
The following logics do not have the zero-one law:
First-order logic with least fixed-point operators with a predicate < interpreted as a total order on the domain (see second paragraph after Corollary 12.3 in )
∃
S
O
(
∀
∀
∃
)
{\displaystyle \exists SO(\forall \forall \exists )}
even if the FO part does not use equality (see Theorem 12.16 in )
MSO (see Exercice 12.6 in )
First-order logic with unary function symbols does not have the zero-one law, but has the convergence law, meaning that for all formulas
φ
{\displaystyle \varphi }
, the quantity
μ
n
(
φ
)
{\displaystyle \mu _{n}(\varphi )}
converges.
References