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

DOI10.1007/S00153-015-0438-7zbMATH Open1341.03091arXiv1309.3408OpenAlexW3104494214WikidataQ60691910 ScholiaQ60691910MaRDI QIDQ892132FDOQ892132

Authors: Vedran Čačić, Vjekoslav Kovač 

Publication date: 18 November 2015

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Analytic combinatorics
• Singularity Analysis of Generating Functions
• A new principle in the interpretability logic of all reasonable arithmetical theories
• Title not available (Why is that?)
• The On-Line Encyclopedia of Integer Sequences
• A note on the normal form of closed formulas of interpretability logic
• The closed fragment of IL is PSPACE hard
• A note on normal forms for the closed fragment of system IL
• Arithmetically complete modal theories

Cited In (1)

• An overview of Verbrugge semantics, a.k.a. generalised Veltman semantics

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)