Zero-One Laws and Almost Sure Valuations of First-Order Logic in Semiring Semantics

Semiring semantics evaluates logical statements by values in some commutative semiring (K, +, •, 0, 1). Random semiring interpretations, induced by a probability distribution on K, generalise random structures, and we investigate here the question of how classical results on first-order logic on random structures, most importantly the 0-1 laws of Glebskii et al. and Fagin, generalise to semiring semantics. For positive semirings, the classical 0-1 law implies that every first-order sentence is, asymptotically, either almost surely evaluated to 0 by random semiring interpretations, or almost surely takes only values different from 0. However, by means of a more sophisticated analysis, based on appropriate extension properties and on algebraic representations of first-order formulae, we can prove much stronger results.

For many semirings K the first-order sentences in FO(τ ) can be partitioned into classes (Φj)j∈K such that for each j ∈ K, every sentence in Φj evaluates almost surely to j under random semiring interpretations. Further, for finite or infinite lattice semirings, this partition actually collapses to just three classes Φ0, Φ1, and Φε, of sentences that, respectively, almost surely evaluate to 0, 1, and to the smallest value ε ̸ = 0. For all other values j ∈ K we have that Φj = ∅. The problem of computing the almost sure valuation of a first-order sentence on finite lattice semirings is Pspace-complete.

An important semiring where the analysis is somewhat different is the natural semiring (N, +, •, 0, 1). Here, both addition and multiplication are increasing with respect to the natural semiring order and the classes (Φj) j∈N no longer cover all FO(τ )-sentences, but have to be extended by Φ∞, the class of sentences that almost surely evaluate to unboundedly large values.