Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-23T19:22:09.946Z Has data issue: false hasContentIssue false
  • English
  • Français

Fine Spectra and Limit Laws, II First-Order 0–1 Laws

Published online by Cambridge University Press:  20 November 2018

Stanley Burris ,
Kevin Compton ,
Andrew Odlyzko  and
Bruce Richmond
Stanley Burris
Affiliation:
Dept. of Pure Mathematics, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1
Kevin Compton
Affiliation:
AT&T Bell Laboratories, Murray Hill, NJ 07974, U.S.A.
Andrew Odlyzko
Affiliation:
Dept. of EECS, University of Michigan, Ann Arbor, MI 48109–2122, U.S.A.
Bruce Richmond
Affiliation:
Dept. of Combinatorics & Optimization, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Using Feferman-Vaught techniques a condition on the fine spectrum of an admissible class of structures is found which leads to a first-order 0–1 law. The condition presented is best possible in the sense that if it is violated then one can find an admissible class with the same fine spectrum which does not have a first–order 0–1 law.

If the condition is satisfied (and hence we have a first-order 0–1 law) we give a natural model of the limit law theory; and show that the limit law theory is decidable if the theory of the directly indecomposables is decidable. Using asymptotic methods from the partition calculus a useful test is derived to show several admissible classes have a first–order 0–1 law.

Keywords

Primary: 03N4511N4511N8005A1505A1611M4111P81
Type
Research Article
Information
Canadian Journal of Mathematics , Volume 49 , Issue 4 , 01 August 1997 , pp. 641 - 652
Copyright
Copyright © Canadian Mathematical Society 1997

References

1. Burris, S. and Sárközy, A., Fine spectra and limit laws I. First-Order Laws. Can. J. Math., 49(1997), 468– 498.Google Scholar
2. Comer, S., Complete and model-complete theories of monadic algebras. Colloq. Math. 34(1975/76), 183– 190.Google Scholar
3. Feferman, S. and Vaught, R.L., The first-order properties of algebraic systems. Fund. Math. 47(1959), 57–103.Google Scholar
4. Hardy, G.H. and Wright, E.M., An Introduction to the Theory of Numbers. Oxford Press, Fourth Ed.Google Scholar
5. Richmond, L.B., Asymptotic results for partitions (I) and the distribution of certain integers. J. Number Th. 8(1976), 372–389.Google Scholar
6. Roth, K.F. and Szekeres, G., Some asymptotic formulas in the theory of partitions. Quart. J. Math. Oxford Ser. 2 5(1954), 244–259.Google Scholar
7. Szmielew, W., Elementary properties of Abelian groups. Fund. Math. 41(1955), 203–271.Google Scholar