Zero-One Laws: Thesauri and Parametric Conditions

The 0-1 law for first-order properties of finite structures and its proof via extension axioms were first obtained in the context of arbitrary finite structures for a fixed finite vocabulary. But it was soon observed that the result and the proof continue to work for structures subject to certain restrictions. Examples include undirected graphs, tournaments, and pure simplicial complexes. We discuss two ways of formalizing these extensions, Oberschelp’s parametric conditions (Springer Lecture Notes in Mathematics 969, 1982) and our thesauri of “Strong Extension Axioms and Shelah’s Zero-One Law for Choiceless Polynomial Time.” We show that, if we restrict thesauri by requiring their probability distributions to be uniform, then they and parametric conditions are equivalent. Nevertheless, some situations admit more natural descriptions in terms of thesauri, and the thesaurus point of view suggests some possible extensions of the theory.

This publication has also been reprinted in the following:

• Logic at the Crossroads: An Interdisciplinary View, Amitabha Gupta, Rohit Parikh, Johan van Benthem, eds. Allied Publishers, New Delhi, 2007, pages 187-206
  
• Proof, Computation and Agency: Logic at the Crossroads, Amitabha Gupta, Rohit Parikh, Johan van Benthem, eds. Springer 2011, pages 99-114