The 0-1 Law

To start off the year 2006, I want to talk about the 0-1 law, which is an extremely important and elegant topic in finite model theory. A logic L (over a fixed vocabulary σ) is said to admit the 0-1 law if, for any sentence f of L, the fraction of σ-structures with universe {0,...,n-1} that satisfy the sentence f converges to either 0 or 1 as n approaches infinity. We denote this fraction by μ_n(f) and the limit, if exists, by μ(f). [Of course, this means that μ and μ_n ranges between 0 and 1.] In other words, every sentence f is almost surely false or almost surely true. For simplicity, let us restrict our attention to undirected loopless graphs, i.e., σ contains only one binary relation E which is both symmetric and irreflexive. Below is perhaps the most fundamental theorem about the 0-1 law.

Theorem (Fagin 1976, Glebskii et al. 1969): First-order logic admits the 0-1 law

Most finite model theorists equate the admission of 0-1 law with the inability to do "counting". Consider the following properties EVEN = { G : G has even number of vertices }. We see that μ_n(EVEN) = 1 iff n is even, and hence μ(EVEN) does not exist. I am yet to see a property whose asymptotic probability μ converges to something other than 0 or 1, or diverges, but has nothing to do with counting. Consider the following properties:

1. μ(BIPARTITE) = 0
   
2. μ(HAMILTONIAN) = 1
   
3. μ(CONNECTED) = 1
   
4. μ(TREE) = 0
   

On the other hand, if you admit constant or function symbols, it is possible to have first-order properties whose asymptotic probability converges to something other than 0 or 1. So, it is crucial to assume that our vocabulary σ be purely relational.

What is the use of 0-1 law in finite model theory apart from the amusement of some theoreticians? [I will have to confess many proofs about the 0-1 law, including Fagin's proof of the above theorem, are usually of great beauty.] Well, a primary concern of finite model theory is to determine how expressive a logic is over a given class of finite structures. By proving that a logic admits the 0-1 law, we show that any property whose asymptotic probability does not converge to either 0 or 1 is not expressible in the logic. For example, an immediate corollary of the above theorem is that first-order logic cannot express EVEN.

Let me briefly outline the proof ideas of the above theorem which recurs in 0-1 law proofs. We only need to show that, for each natural number k, there exists a property P_k of graphs such that

1. μ(P_k) = 1, and
   
2. Any two models of P_k cannot be distinguished by a first-order sentence of quantifier rank k. [Recall that the quantifier rank of a first-order sentence is the maximum depth of any nesting of quantifiers of the sentence.]
   

Why is this sufficient? Let f be a first-order sentence of quantifier rank k. There are two cases. First, there exists a model of P_k that is also a model of f. In this case, it is not hard to show that any model of P_k is also a model of f, which implies that μ(f) ≥ μ(P_k) = 1. The second case is that all models of P_k are not models of f, i.e., they are models of "not f". Therefore, μ("not f") ≥ μ(P_k) = 1. That is, we have μ(f) = 0.

The property P_k is commonly referred to as an extension axiom. Note that P_k does not have to be L-definable (where L is the logic that is to admit 0-1 law).

Two excellent expositions of the basics of 0-1 laws include Leonid Libkin's Elements of Finite Model Theory chapter 12, and James Lynch DIMACS 1995-1996 Tutorial notes on "Random Finite Models".