Sufficient conditions for zero-one laws

Authors
Citation
Jp. Bell, Sufficient conditions for zero-one laws, T AM MATH S, 354(2), 2001, pp. 613-630
Citations number
10
Categorie Soggetti
Mathematics
Journal title
TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY
ISSN journal
00029947 → ACNP
Volume
354
Issue
2
Year of publication
2001
Pages
613 - 630
Database
ISI
SICI code
0002-9947(2001)354:2<613:SCFZL>2.0.ZU;2-R
Abstract
We generalize a result of Bateman and Erdos concerning partitions, thereby answering a question of Compton. From this result it follows that if K is a class of finite relational structures that is closed under the formation o f disjoint unions and the extraction of components, and if it has the prope rty that the number of indecomposables of size n is bounded above by a poly nomial in n, then K has a monadic second order 0-1 law. Moreover, we show t hat if a class of finite structures with the unique factorization property is closed under the formation of direct products and the extraction of inde composable factors, and if it has the property that the number of indecompo sables of size at most n is bounded above by a polynomial in log n, then th is class has a first order 0-1 law. These results cover all known natural e xamples of classes of structures that have been proved to have a logical 0- 1 law by Compton's method of analyzing generating functions.