#
My question is following: can we estimate how many validities (formulas that are always true) are there among all formulas of propositional logic? Is there a method of doing it?

As it turns out, the answer is easy: there are aleph-null tautologies (formulas true in every row of a truth table) in any standard system of propositional logic -- for sort, in SC (sentential calculus). Here "aleph-null" is the number of integers. Here's a sketch of a proof. First, how many formulas are there in SC? Infinitely many, of course. But it's possible to set up a function that pairs each formula in SC with a unique positive integer. (There are many ways to do this, in fact.) So there can't be any more formulas than there are integers; no more than aleph-null. But some standard arguments tell us that every infinite subset of the integers has the same number of members (aleph-null) as the set of integers itself. In the usual terminology, every infinite subset of a countable set is itself countable. (I recommend as an exercise thinking about how that might be proved.) So, we know that there are aleph-null formulas of SC. But we also know that there are infinitely many tautologies....

- Log in to post comments