Lindström Lectures 2023: Rineke Verbrugge

It has been shown in the late 1960s that each formula of first-order logic without constants and function symbols obeys a zero-one law: As the number of elements of finite models increases, every formula holds either in almost all or in almost no models of that size. For modal logics, limit behavior for models and frames may differ. In 1994, Halpern and Kapron proved zero-one laws for classes of models corresponding to the modal logics K, T, S4, and S5. They also proposed zero-one laws for the corresponding classes of frames, but their zero-one law for K-frames has since been disproved, and so has more recently their zero-one law for S4-frames.

Provability logic was one of the main interests of Per Lindström. In this talk, we prove zero-one laws for provability logic with respect to both model and frame validity. Moreover, we axiomatize validity in almost all irreflexive transitive finite models and in almost all irreflexive transitive finite frames, leading to two different axiom systems. In the proofs, we use a combinatorial result by Kleitman and Rothschild about the structure of finite (strict) partial orders: almost all of them consist of only three layers. Finally, we present empirical results in order to give an idea of the number of elements from which onwards a formula’s almost sure validity or almost sure invalidity stabilizes in such three-layer Kleitman-Rothschild frames. We also discuss possible extensions of the zero-one laws to the modal logics S4 and K4.

More about the Lectures

Research lecture: Friday, 12 May at 10-12, room J439: Aspects of provability and interpretability

Rineke Verbrugge is Professor of Logic and Cognition, at Bernoulli Institute of Mathematics, Computer Science and Artificial Intelligence, University of Groningen.

The Department of Philosophy, Linguistics and Theory of Science at the University of Gothenburg launched a lecture series in 2013 to celebrate the singular achievements of Pelle Lindström, former professor of logic at the department.

Annually, a distinguished logician is invited to deliver a general lecture to the public, and a specialized presentation at the logic seminar.