Threshold spectra via the Ehrenfeucht game (Q757267): Difference between revisions

This author with Saharon Shelah has shown that the random graph G(n,p) with \(p=n^{-\alpha}\), \(\alpha\) irrational, satisfies the Zero-One Law - every first order sentence A holds with probability approaching zero or one. Here a general connection is made between Zero-One Laws and the Ehrenfeucht game - to prove a Zero-One Law it suffices to find a strategy for dublicator that almost always wins on two random structures. The result is then reproved, with copious examples, by giving such a strategy. Further the threshold spectrum Sp(A) is defined, roughly, as those \(\alpha\) for which the Zero-One Law does not hold for \(p=n^{- \alpha +0(1)}\). The proof is refined to show that Sp(A) is a well-ordered (under \(>)\) set of rational numbers of order type less than \(\omega^{\omega}\).