0-1 laws for recursive structures (Q1127833)

It is a well-known result due to Gaifman that the set of all extension axioms of a finite relational vocabulary \(\sigma\), has a unique countable model, called the random \(\sigma\)-structure \({\mathcal R}\), and that the isomorphism class of \({\mathcal R}\) has measure one (with respect to the Lebesgue measure) within the class of \(\sigma\)-structures with universe \(\omega\). A relational structure of finite vocabulary is called recursive if its universe is countable and each relation is recursive. To study 0-1 laws on recursive structures one has to define a reasonable measure for this class; since, obviously, the recursive structures have Lebesgue measure 0. A non-standard, but convenient, way to define the Lebesgue measure is in terms of betting strategies or, equivalently, martingales. The restriction to recursive martingales yields a measure on the set of recursive structures. In this paper it is shown that the isomorphism class of the random \(\sigma\)-structure has measure one also on the class of recursive structures. As a consequence, every logic has a 0-1 law on the class of recursive structures. These results can even be extended to countable structures where the relations satisfy certain complexity restrictions.