Number Theoretic Density and Logical Limit Laws

Front Cover
American Mathematical Soc., Jan 1, 2001 - Mathematics - 289 pages
0 Reviews
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-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
Symbol Index
285
Copyright

The Case a 0
195

Common terms and phrases

References to this book

Bibliographic information