Probabilities of first-order sentences about unary functions

Abstract

Let $f$ be any fixed positive integer and $\sigma$ a sentence in the first-order predicate calculus of $f$ unary functions. For positive integers $n$, an $n$-structure is a model with universe $\{ 0,1, \ldots ,n - 1\}$ and $f$ unary functions, and $\mu (n,\sigma )$ is the ratio of the number of $n$-structures satisfying $\sigma$ to ${n^{nf}}$, the number of $n$-structures. We show that ${\lim _{n \to \infty }}\mu (n,\sigma )$ exists for all such $\sigma$, and its value is given by an expression consisting of integer constants and the operators $+ , - , \cdot ,/$, and ${e^x}$.

Locations

• Transactions of the American Mathematical Society - View - PDF