A formalised language for the propositional calculus consists of:

  1. an infinite (countable) set of propositional variables p_0, p_1,...;

  2. a set of propositional connectives (conjunction, disjunction, etc.);

  3. a set of auxiliary signs (parentheses).

A formula is defined as a propositional variable or any finite sequence of propositional symbols (i.e. strings of propositional variables with connective(s) and, perhaps, parentheses).

Why is the set of propositional variables required to be countable? Isn't it something artificial in requiring it to be so if we are only interested in finite sequences of propositional symbols?

Also, as a related question: Could we consider a finite set of propositional variables and develop the same propositional calculus?

  • 2
    Finite sequences are always in finite time reducible to either "True" or "False". Infinite sequences may not be. I say "may", because some sequences are reducible - e.g. "True or False or False or False or ...".
    – user2953
    Aug 11 '15 at 9:59

We run into this need pretty early because the first thing we always want to introduce is arithmetic, and the simplest expressions for arithmetic all include the principle of induction.

You cannot capture something like the axiom of induction with a finite set of propositional variables unless you go to the second order and allow propositions themselves to be enumerated over.

We want the axiom that "when something holds for a given integer and we know that whenever it holds for one integer, it will hold for the next, that thing is true of all integers."

In second-order logic, we can say

[ p(0) /\ p(n) -> p(n+1) ] => p(n)

But in first-order logic, this is really a template for an infinite number of additional axioms. We do not have variables available to us that enumerate potential predicates. So we need to spell out all possible instances of p, each in a separate axiom.

That requires allowing any particular instance of p to have arbitrarily many parameters, beyond the parameter n that we are trying to do induction over. (We cannot use 'Currying' to state the axiom with a single parameter, as we did above, because, as a rule about partial functions, it can only be expressed in second-order language, itself.)

The only way to have arbitrarily many variables, in arbitrarily many different instances is to presume infinitely many to begin with.


We specify an infinite set of variables, because we want to be sure that we won't "run out". it is an important motivation for the first-order logic, that it is powerful enough to describe any actual situation, no matter how complicated it gets. We want, in other words, to be able to describe relations among arbitrarily many objects and for this we need a denumerable infinity of possible names to give those objects. We don't want it to be the case that we need to describe the relationship between n many objects, and we only have n-1 many names available in our logic, so we just let ourselves have as many as we please.

The infinite number of potential names for objects does not cause us problems, unlike the possibility of having a sentence that is infinitely long. (Keelan explains this above.)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy