Lecture Notes in Computer Science, 2008, Volume 4941/2008, 100-109, DOI: 10.1007/978-3-540-68103-8_7

Intuitionistic vs. Classical Tautologies, Quantitative Comparison

Antoine Genitrini, Jakub Kozik and Marek Zaionc

View Related Documents

Abstract

We consider propositional formulas built on implication. The size of a formula is the number of occurrences of variables in it. We assume that two formulas which differ only in the naming of variables are identical. For every n εℕ, there is a finite number of different formulas of size n. For every n we consider the proportion between the number of intuitionistic tautologies of size n compared with the number of classical tautologies of size n. We prove that the limit of that fraction is 1 when n tends to infinity.

Fulltext Preview

Image of the first page of the fulltext document