Monadic second order probabilities in algebra. Directly representable varieties and groups
Paweł M. Idziak, Jerzy Tyszkiewicz · DIMACS series in discrete mathematics and theoretical computer science · 1997
We analyze the question of existence of asymptotic cumulative probabilities for monadic second order definable properties of finite algebras. We focus our attention on the directly representable varieties and on the variety of groups. We prove in a very strong way that some recently proven first-order 0-1 laws and limit laws for these varieties cannot be extended to monadic second order logic. Namely, if the function (n; A) 7! pr n [fAg] assigning probabilities to structures is recursive, then the 0-1 law holds according to the sequence fpr n g = pr 1 ; pr 2 ; : : : of probabilities iff asymptotically there exists fpr n g-almost surely precisely one algebra. Similarly, the convergence law holds iff asymptotically there are no large algebras according to fpr n g: