Theorem: For every A in language L(<) lim [f(A,n+1)-f(A,n)] = 0.
Note, as an extreme example, that this implies the nonexistence of a sentence A holding with probability 1-o(1) when n is even and with probability o(1) when n is odd.
In section 2 we give the proof, based on a circuit complexity result. In
Section 3 we prove that result, which is very close to the now classic theorem
that parity cannot given by an AC^0 circuit. In Section 4 we give a very
weak zero-one law for random two-place functions. The proof is very similar,
the random function theorem being perhaps of more interest to logicians, the
random graph theorem to discrete mathematicians.
Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-53.ps.gz