On the share of closed IL formulas which are also in GL

DOI10.1007/S00153-015-0438-7MaRDI QIDQ892132zbMATHOpenAlexWikidataFDO

Authors Vedran Čačić, Vjekoslav Kovač

Publication date 18 November 2015

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.3408

zbMATH Keywords

normal formsasymptotic enumerationprovability logicinterpretability logic

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Asymptotic enumeration (05A16) Provability logics and related algebras (e.g., diagonalizable algebras) (03F45)

Abstract: Normal forms for wide classes of closed IL formulas were given in [4]. Here we quantify asymptotically, in exact numbers, how wide those classes are. As a consequence, we show that the "majority" of closed IL formulas have GL-equivalents, and by that, they have the same normal forms as GL formulas. Our approach is entirely syntactical, except for applying the results of [4]. As a byproduct we devise a convenient way of computing asymptotic behaviors of somewhat general classes of formulas given by their grammar rules. Its applications do not require any knowledge of the recurrence relations, generating functions, or the asymptotic enumeration methods, as all these are incorporated into two fundamental parameters.

Recommendations

• A note on the normal form of closed formulas of interpretability logic
• A note on normal forms for the closed fragment of system IL
• Classical and Intuitionistic Logic Are Asymptotically Identical
• The closed fragment of IL is PSPACE hard
• Distribution of the equilibrium logic formulas in classical logic metric space

Cites work

• scientific article; zbMATH DE number 3539473 (Why is no real title available?)
• scientific article; zbMATH DE number 1215477 (Why is no real title available?)
• A new principle in the interpretability logic of all reasonable arithmetical theories
• A note on normal forms for the closed fragment of system IL
• A note on the normal form of closed formulas of interpretability logic
• Analytic combinatorics
• Arithmetically complete modal theories
• Singularity Analysis of Generating Functions
• The On-Line Encyclopedia of Integer Sequences
• The closed fragment of IL is PSPACE hard

Cited in

(2)

• An overview of Verbrugge semantics, a.k.a. generalised Veltman semantics
• The closed fragment of IL is PSPACE hard

Describes a project that uses

Uses Software

• Mathematica
• OEIS

This page was built for publication: On the share of closed \(\mathsf {IL}\) formulas which are also in \(\mathsf {GL}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q892132)