English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

It has been shown in the late 1960s that each formula of first-order logicwithout constants and function symbols obeys a zero-one law: As the number ofelements of finite models increases, every formula holds either in almost allor in almost no models of that size. Therefore, many properties of models, suchas having an even number of elements, cannot be expressed in the language offirst-order logic. For modal logics, limit behavior for models and frames maydiffer. Halpern and Kapron proved zero-one laws for classes of modelscorresponding to the modal logics K, T, S4, and S5.  In this paper, we prove zero-one laws for provability logic with respect toboth model and frame validity. Moreover, we axiomatize validity in almost allrelevant finite models and in almost all relevant finite frames, leading to twodifferent axiom systems. In the proofs, we use a combinatorial result byKleitman and Rothschild about the structure of almost all finite partialorders. On the way, we also show that a previous result by Halpern and Kapronabout the axiomatization of almost sure frame validity for S4 is not correct.Finally, we consider the complexity of deciding whether a given formula isalmost surely valid in the relevant finite models and frames.

Zero-one laws for provability logic: Axiomatizing validity in almost all models and almost all frames