Abstract

The time-honoured idea that logical deduction is "analytic" or "tautological" is one of the most influential in the whole history of philosophy, one which is shared by authors as different as Locke, Kant, Wittgenstein, Mach and Popper. Since proving a mathematical theorem is nothing but deducing it from a given axiom system, advocates of this idea are forced to draw the embarassing conclusion that mathematical proofs do not play any significant role in the growth of knowledge. Some authors have taken this paradox as evidence that traditional formal logic is inadequate to formalize scientific inference and have argued for some form of non-monotonic logic. In this paper I criticize the view that logical inference in classical logic does not increase information by revisiting and extending Hintikka's well-known argument for the synthetic character of first-order logic. I also claim that computational complexity should urge us to revise this view even in the innocuoslooking domain of propositional logic and maintain that any truly "analytic" inference should be not only effective (which excludes first-order logic) but also "tractable" (which is very likely to exclude propositional logic too). Therefore I argue that the "paradox" of logical deduction should not be taken as evidence against classical logic, but rather against our theory of logical information.