03/01/1990 09:00 AM
Computer Science
We investigate asymptotic probabilities of properties expressible in the infinitary logic L^omega_{infinity omega} on finite structures. Sentences in this logic may have arbitrary disjunctions and conjunctions, but they involve only a finite number of distinct variables. We show that the 0-1 law holds for L^omega_{infinity omega}, i.e., the asymptotic probability of every sentence in this logic exists and is equal to either 0 or 1. This result subsumes earlier work on asymptotic probabilities for various fixpoint logics and reveals the boundary of 0-1 laws for infinitary logics.
