Topics Logic

Question 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?

Accepted:
December 4, 2007

Comments

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. Here's a cheap way to see this: Start with this tautology: (P v ~P) [That is, "P or not-P"]. Then notice that each of the following is also a tautology:

~~(P v ~P), ~~~~(P v ~P), ~~~~~~(P v ~P).....

This already gives us an infinite collection of distinct formulas, each of which is a tautology. But since any infinite subset of a countable set is also countable, the list I've indicated above is countable -- has aleph-null entries.

Now my list is only a subset of all the tautologies, but that doesn't matter. Since there are at least as many tautologies as there are formulas in my list, there are at least aleph null of them. However, since the tautologies are a subset of all the formulas of SC, of which there are aleph-null, there can be at most aleph-null tautologies. And so we conclude: there are exactly aleph-null tautological formulas in SC.

Question 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? Accepted:December 4, 2007

Question 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?

Accepted:
December 4, 2007