A logic has a zero-one law if for each sentence the fraction of structures with universe {1,2, ..., n} that satisfy that sentence goes to 1 or 0, as n goes to infinity. We provide an introduction to zero-one laws and present a proof by Fagin for the zero-one law for first order logic.
(This is the last Theory Seminar of the semester.)
Last modified 6 December 2002