0-1-LAWS BY PRESERVATION

Our central result asserts that a (logical) language preserved under e xtension of models has a 0-1 law under the uniform probability distrib ution. We then investigate some fragments of the first-order infinitar y logic L-infinity omega and of second-order logic which are preserved under extension. This paper reveals new boundaries of 0-1 laws for fr agments of L-infinity omega and of second-order logic. The latter frag ments are particularly interesting as they capture the prototypical co mplete problem for each level of the polynomial-time hierarchy.