A New Zero-One Law and Strong Extension Axioms
- Andreas Blass ,
- Yuri Gurevich
Bulletin of the European Association for Theoretical Computer Science | , Vol 72: pp. 103-122
This article is a part of the continuing column on Logic in Computer Science. One of the previous articles in the column was devoted to the zero-one laws for a number of logics playing prominent role in finite model theory: first-order logic FO, the extension FO+LFP of first-order logic with the least fixed-point operator, and the infinitary logic where every formula uses finitely many variables [Zero-One Laws]. Recently Shelah proved a new, powerful, and surprising zero-one law. His proof uses so-called strong extension axioms. Here we formulate Shelah’s zero-one law and prove a few facts about these axioms. In the process we give a simple proof for a “large deviation” inequality a la Chernoff.
This publication was also reprinted in 2004 World Scientific book, Current Trends in Theoretical Computer Science, pages 99-118.