**Mathematical Surveys and Monographs**

Volume: 86;
2001;
289 pp;
Hardcover

MSC: Primary 03; 05; 11;

Print ISBN: 978-0-8218-2666-9

Product Code: SURV/86

List Price: $84.00

Individual Member Price: $67.20

**Electronic ISBN: 978-1-4704-1313-2
Product Code: SURV/86.E**

List Price: $84.00

Individual Member Price: $67.20

# Number Theoretic Density and Logical Limit Laws

Share this page
*Stanley N. Burris*

This book shows how a study of generating series (power series in the additive
case and Dirichlet series in the multiplicative case), combined with structure
theorems for the finite models of a sentence, lead to general and powerful
results on limit laws, including \(0 - 1\) laws. The book is unique in its
approach to giving a combined treatment of topics from additive as well as from
multiplicative number theory, in the setting of abstract number systems,
emphasizing the remarkable parallels in the two subjects. Much evidence is
collected to support the thesis that local results in additive systems lift to
global results in multiplicative systems.

All necessary material is given to understand thoroughly the method of Compton
for proving logical limit laws, including a full treatment of
Ehrenfeucht-Fraissé games, the Feferman-Vaught Theorem, and Skolem's
quantifier elimination for finite Boolean algebras. An intriguing aspect of the
book is to see so many interesting tools from elementary mathematics pull
together to answer the question: What is the probability that a randomly chosen
structure has a given property? Prerequisites are undergraduate analysis and
some exposure to abstract systems.

#### Table of Contents

# Table of Contents

## Number Theoretic Density and Logical Limit Laws

- Contents vii8 free
- Preface xi12 free
- Overview xiii14 free
- Notation Guide xix20 free
- Part 1. Additive Number Systems 122 free
- Chapter 1. Background from Analysis 324
- Chapter 2. Counting Functions and Fundamental Identities 1738
- 2.1. Defining additive number systems 1738
- 2.2. Examples of additive number systems 2142
- 2.3. Counting functions, fundamental identities 2546
- 2.4. Global counts 3354
- 2.5. Alternate version of the fundamental identity 3455
- 2.6. Reduced additive number systems 3758
- 2.7. Finitely generated number systems 3960
- 2.8. a*(n) is eventually positive 4364

- Chapter 3. Density and Partition Sets 4566
- 3.1. Asymptotic density 4566
- 3.2. Dirichlet density 4869
- 3.3. The standard assumption 5172
- 3.4. The set of additives of an element 5172
- 3.5. Partition sets 5475
- 3.6. Generating series of partition sets 5778
- 3.7. Partition sets have Dirichlet density 5879
- 3.8. Schur's Tauberian Theorem 6283
- 3.9. Simple partition sets 6788
- 3.10. The asymptotic density of γ[sup(P)] 6889
- 3.11. Adding an indecomposable 7091

- Chapter 4. The Case ρ = 1 7596
- Chapter 5. The Case 0 < ρ < 1 87108
- Chapter 6. Monadic Second-Order Limit Laws 103124

- Part 2. Multiplicative Number Systems 125146
- Chapter 7. Background from Analysis 127148
- Chapter 8. Counting Functions and Fundamental Identities 143164
- Chapter 9. Density and Partition Sets 159180
- 9.1. Asymptotic density 159180
- 9.2. Dirichlet density 160181
- 9.3. The standard assumption 164185
- 9.4. The set of multiples of an element 164185
- 9.5. Partition sets 166187
- 9.6. Generating series of partition sets 169190
- 9.7. Partition sets have Dirichlet density 170191
- 9.8. Discrete multiplicative number systems 174195
- 9.9. When sets bA have global asymptotic density 177198
- 9.10. The strictly multiplicative case and RV[sub(α)] 181202
- 9.11. The discrete case and RV[sub(α)] 181202
- 9.12. Analog of Schur's Tauberian Theorem 182203
- 9.13. Simple partition sets 188209
- 9.14. The asymptotic density of P[sup(γ)] 189210
- 9.15. Adding an indecomposable 191212
- 9.16. First conjecture 194215

- Chapter 10. The Case α = 0 195216
- Chapter 11. The Case 0 < α < ∞ 201222
- Chapter 12. First-Order Limit Laws 217238
- 12.1. Asymptotic density of subsets of K 217238
- 12.2. The Feferman-Vaught Theorem 218239
- 12.3. Skolem's analysis of the first-order calculus of classes 223244
- 12.4. K[omitted] is a disjoint union of partition classes 226247
- 12.5. Applications 227248
- 12.6. Finite dimensional structures 231252
- 12.7. The main problem 231252

- Appendix A. Formal Power Series 233254
- Appendix B. Refined Counting 251272
- Appendix C. Consequences of δ(P) = 0 261282
- Appendix D. On the Monotonicity of a(n) When p(n) ≤ 1 269290
- Appendix E. Results of Woods 273294
- Bibliography 281302
- Symbol Index 285306
- Subject Index 287308

#### Readership

Graduate students and research mathematicians interested in combinatorics, number theory and logic.

#### Reviews

Shows an exciting connection between combinatorics, number theory and logic, and certainly deserves to be more widely known. The book gives a very clear account of it and it is easily readable.

-- Zentralblatt MATH

This book is a lucid, self-contained introduction to a fascinating interaction between analysis, combinatorics, logic and number theory … accessible to an undergraduate and gives interesting examples to illustrate the concepts.

-- Mathematical Reviews