## Number Theoretic Density and Logical Limit LawsThis 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-Fraisse 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. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Counting Functions and Fundamental Identities | 17 |

Density and Partition Sets | 45 |

The Case p 1 | 75 |

The Case 0 p 1 | 87 |

Monadic SecondOrder Limit Laws | 103 |

Background from Analysis | 127 |

Counting Functions and Fundamental Identities | 143 |

Chapter g Density and Partition Sets | 159 |

The Case 0 a oc | 201 |

FirstOrder Limit Laws | 217 |

Appendix A Formal Power Series | 233 |

Appendix B Refined Counting | 251 |

Consequences of 6P 0 | 261 |

On the Monotonicity of an When pn 1 | 269 |

285 | |

The Case a 0 | 195 |

### Common terms and phrases

Abelian groups abscissa of convergence absolutely convergent additive number system adequate class apply aq(n Boolean algebras Cauchy product Chapter choose class of finite coefficients Compton converges absolutely converges iff Corollary defined Definition Dirichlet density Dirichlet product Dirichlet series expansion disjoint union equation equivalence relation eventually positive example exists expressed Feferman-Vaught first-order 0-1 law first-order limit law first-order logic follows formula free commutative monoid given global asymptotic density global count function graphs holds hypothesis implies indecomposable elements indecomposables infinite product inverse isomorphism Knopfmacher L-formulas L-structures Lemma limsup logical limit laws multiplicative number system n—oc A(n nondecreasing nonnegative integers norm norm n notation partition classes partition sets Player posets positive integer power series expansion prime number Proof Proposition proved quantifier rank radius of convergence satisfy Schur's sequence set of indecomposables Suppose Tauberian Theorem two-colored linear forests unary

### References to this book

Mathematics and Computer Science II: Algorithms, Trees ..., Volume 2 Brigitte Chauvin Limited preview - 2002 |