On the share of IL formulas that have normal forms
Vedran Čačić, Vjekoslav Kovač · arXiv (Cornell University) · 2013
Normal forms for wide classes of closed IL formulas were given in [3]. Here we quantify, in exact numbers, how wide those classes are. As a consequence, we show that more than 93% 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 [3], and we enumerate certain subclasses of formulas by recurrence relations similar to Segner's relation for the Catalan numbers. We also devise a convenient way of comparing asymptotic behaviors of such recursively defined sequences, which does not require explicit expressions for their generating functions.