This paper developed from Shelah’s proof of a zero-one law for the
complexity class “choiceless polynomial time,” defined by Shelah and
the authors. We present a detailed proof of Shelah's result for
graphs, and describe the extent of its generalizability to other sorts
of structures. The extension axioms, which form the basis for earlier
zero-one laws (for first-order logic, fixed-point logic, and
finite-variable infinitary logic) are inadequate in the case of
choiceless polynomial time; they must be replaced by what we call the
strong extension axioms. We present an extensive discussion of these
axioms and their role both in the zero-one law and in general.