Probabilities on finite models1

E-ISSN： 1943-5886|41|1|50-58

ISSN： 0022-4812

Source： The Journal of Symbolic Logic, Vol.41, Iss.1, 1976-03, pp. : 50-58

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

Let be a finite set of (nonlogical) predicate symbols. By an -structure, we mean a relational structure appropriate for . Let be the set of all -structures with universe {1, …, n}. For each first-order -sentence σ (with equality), let μ_n(σ) be the fraction of members of for which σ is true. We show that μ_n(σ) always converges to 0 or 1 as n → ∞, and that the rate of convergence is geometrically fast. In fact, if T is a certain complete, consistent set of first-order -sentences introduced by H. Gaifman [6], then we show that, for each first-order -sentence σ, μ_n(σ) →_n 1 iff T ⊩ ω. A surprising corollary is that each finite subset of T has a finite model. Following H. Scholz [8], we define the spectrum of a sentence σ to be the set of cardinalities of finite models of σ. Another corollary is that for each first-order -sentence a, either σ or ˜σ has a cofinite spectrum (in fact, either σ or ˜σ is “nearly always“ true).