tautologies in predicate logic
, where is not free in
, where , , and is free for in
The first three axiom schemas and the modus ponens tell us that predicate logic is an extension of the propositional logic. On the other hand, we can also view predicate logic as a part of propositional logic if we treat all quantified formulas as atoms. This can be done precisely as follows:
Call a wff of FO quasi-atom if it is either atomic, or of the form , where is a wff of FO. Let be the set of all quasi-atoms of FO.
Every wff of FO can be uniquely built up from using only logical connectives and .
Induction on the complexity of wff. For any wff of FO, it has one of the following forms: , , or , where are wff’s. If were or , by induction, since and were in , is in as a result. If were , then is quasi-atomic, and therefore in by the definition of . Unique readability follows from the unique readability of wff’s of propositional logic. ∎
Since no quantifiers are involved in the built-up process, the language based on as the set of atoms can be considered as the language of propositional logic. Call this logic PL. So the atoms of PL are precisely the quasi-atoms of FO.
Suppose wff is a tautology in FO. Then it is a tautology in PL by definition, and therefore a theorem in PL since propositional logic is complete with respect to truth-value semantics. If is a deduction of (with ), then each is either an axiom, or is obtained by an application of modus ponens. If is an axiom (of PL), it is an instance of one of the first three axiom schemas of FO above, which means that is an axiom of FO. Furthermore, since modus ponens is a rule of inference for FO, is a deduction of in FO, which means that is a theorem of FO.
On the other hand, any wff that is an instance of one of the last two axiom schemas of FO is a theorem that is not a tautology. For example, is an instance of the fourth axiom schema, which takes the form , where is a quasi-atom, and an atom, both of which are atoms of PL. Any truth-valuation that takes to and to , takes to . Therefore, is not a tautology. ∎