A Zero-one Law for Logic with a Fixed-point Operator

The zero-one law, known to hold for first-order logic but not for monadic or even existential monadic second-order logic, is generalized to the extension of first-order logic by the least (or iterative) fixed-point operator. We also show that the problem of deciding, for any pi, whether it is almost sure is complete for exponential time, if we consider only pi’s with a fixed finite vocabulary (or vocabularies of bounded arity) and complete for double-exponential time if pi is unrestricted.