Zero-One Laws and Almost Sure Valuations of First-Order Logic in Semiring Semantics
Semiring semantics evaluates logical statements not just to true or false, but to values in some commutative semiring.
As part of a general project to study the (finite) model theory of semiring semantics, we consider here random semiring interpretations, induced by a probability distribution on a (finite or infinite) semiring, and we investigate here the question of how classical results on first-order logic on random structures, most importantly the 0-1 law, generalise to semiring semantics.
It is an immediate consequence of the classical 0-1 law that a 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 by polynomials, we can prove stronger results.
For many semirings, FO can be partitioned into classes F(j), such that every sentence in F(j) evaluates almost surely to j under random semiring interpretations. Further, for most of the semirings studied here, this partition actually collapses to just three classes F(0), F(1), and F(e), of sentences that, respectively, almost surely evaluate to 0, 1, and to the infimum e of all non-zero values of the semiring. For all other values j in the semiring we have that F(j) is empty.
A semiring where the analysis is somewhat different is the natural semiring (N,+,*,0,1) for which multiplication is increasing rather than decreasing with respect to the natural semiring order.
This is joint work with Hayyan Helal, Matthias Naaf, and Richard Wilke.