Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

Sufficient conditions for zero-one laws


Author: Jason P. Bell
Journal: Trans. Amer. Math. Soc. 354 (2002), 613-630
MSC (1991): Primary 60F20; Secondary 05A16
Published electronically: September 28, 2001
MathSciNet review: 1862560
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We generalize a result of Bateman and Erdos concerning partitions, thereby answering a question of Compton. From this result it follows that if $\mathcal{K}$ is a class of finite relational structures that is closed under the formation of disjoint unions and the extraction of components, and if it has the property that the number of indecomposables of size $n$ is bounded above by a polynomial in $n$, then $\mathcal{K}$ has a monadic second order $0$-$1$ law. Moreover, we show that if a class of finite structures with the unique factorization property is closed under the formation of direct products and the extraction of indecomposable factors, and if it has the property that the number of indecomposables of size at most $n$ is bounded above by a polynomial in $\log n$, then this class has a first order $0$-$1$ law. These results cover all known natural examples of classes of structures that have been proved to have a logical $0$-$1$ law by Compton's method of analyzing generating functions.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (1991): 60F20, 05A16

Retrieve articles in all journals with MSC (1991): 60F20, 05A16


Additional Information

Jason P. Bell
Affiliation: Department of Mathematics, University of California San Diego, La Jolla, California 92093-0112
Email: jbell@math.ucsd.edu

DOI: http://dx.doi.org/10.1090/S0002-9947-01-02884-7
PII: S 0002-9947(01)02884-7
Received by editor(s): April 10, 2000
Received by editor(s) in revised form: May 18, 2001
Published electronically: September 28, 2001
Additional Notes: I am indebted to Stan Burris for pointing out that results obtained in the additive case lift to the multiplicative case, to John Lawrence for helping with an application, and to the referee for valuable comments regarding the presentation.
Article copyright: © Copyright 2001 American Mathematical Society