How big is fragment of logic

作者：Grygiel Katarzyna^*; Idziak Pawel M; Zaionc Marek

来源：Journal of Logic and Computation, 2013, 23(3): 673-691.

DOI：10.1093/logcom/exs017

• and logics
• asymptotic probability in logic
• analytic combinatorics

We investigate quantitative properties of and logics. The first part of the article compares the number of formulas provable in versus logics. We consider formulas built on implication and a fixed set of k variables. We investigate the proportion between the number of such formulas of a given length n provable in logic against the number of formulas of length n provable in richer logic. We examine an asymptotic behaviour of this fraction when length n of formulas tends to infinity. This limit gives a probability measure that randomly chosen formula is also provable in . We prove that this probability tends to zero as the number of variables tends to infinity. The second part of the article is devoted to the number of lambda terms representing proofs of and logics. We build a proportion between number of such proofs of the same length n and we investigate asymptotic behaviour of this proportion when length of proofs tends to infinity. We demonstrate that with probability 0 a randomly chosen proof is also a proof of a formula.

• 出版日期2013-6