Title: Modal zero-one laws: provability logic, Grzegoczyk logic and
weak Grzegorczyk logic

Abstract:

Glebskii and colleagues proved in the late 1960s that each formula of
first-order logic without constants and function symbols obeys a
zero-one law.  That is, every such formula is either almost surely
valid or almost surely not valid: As the number of elements of finite
models increases, each formula holds either in almost all or in almost
no models of that size. As a consequence, many properties of models,
such as having an even number of elements, cannot be expressed in the
language of first-order logic without constants and function
symbols. In a 1994 paper, Halpern and Kapron proved similar zero-one
laws for classes of models corresponding to the modal logics K, T, S4,
and S5.

In this presentation, we discuss zero-one laws for some modal logics
that impose structural restrictions on their models; all three logics
that we are interested in are sound and complete with respect to
finite partial orders with different extra restrictions per logic. We
prove zero-one laws for provability logic, Grzegorczyk logic and weak
Grzegorczyk logic, with respect to model validity. Moreover, for all
three logics, we axiomatize validity in almost all relevant finite
models, leading to three different axiom systems.  In the proofs, we
use a combinatorial result by Kleitman and Rothschild about the
structure of almost all finite partial orders. We also discuss the
question whether for the three sibling logics, validity in almost all
relevant finite frames can be axiomatized as well. In the process, we
explain that some results about almost sure frame validity from
Halpern and Kapron’s paper do not hold after all.