tautologies in predicate logic


Let FO(Σ) be a first order language over signaturePlanetmathPlanetmathPlanetmath Σ. Recall that the axioms for FO(Σ) are (universalPlanetmathPlanetmath) generalizationsPlanetmathPlanetmath of wff’s belonging to one of the following six schemas:

  1. 1.

    A(BA)

  2. 2.

    (A(BC))((AB)(AC))

  3. 3.

    ¬¬AA

  4. 4.

    x(AB)(xAxB), where xV

  5. 5.

    AxA, where xV is not free in A

  6. 6.

    xAA[a/x], where xV, aV(Σ), and a is free for x in A

where V is the set of variables and V(Σ) is the set of variables and constants, with modus ponensMathworldPlanetmath as its rule of inferenceMathworldPlanetmath: from A and AB we may infer B.

The first three axiom schemasMathworldPlanetmath and the modus ponens tell us that predicate logic is an extensionPlanetmathPlanetmath of the propositional logicPlanetmathPlanetmath. 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 xA, where A is a wff of FO(Σ). Let Γ be the set of all quasi-atoms of FO(Σ).

Proposition 1.

Every wff of FO(Σ) can be uniquely built up from Γ using only logical connectives and ¬.

Proof.

InductionMathworldPlanetmath on the complexity of wff. For any wff A of FO(Σ), it has one of the following forms: BC, ¬B, or xB, where B,C are wff’s. If A were BC or ¬B, by induction, since B and C were in Γ, A is in Γ as a result. If A were xB, then A 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 quantifiersMathworldPlanetmath are involved in the built-up process, the languagePlanetmathPlanetmath 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(Σ).

Definition. We call a wff of FO(Σ) a tautologyMathworldPlanetmath if it is a tautology of PL(Γ) (via truth tablesMathworldPlanetmath).

Proposition 2.

In FO(Σ), every tautology is a theoremMathworldPlanetmath, but not conversely.

Proof.

Suppose wff A is a tautology in FO(Σ). Then it is a tautology in PL(Γ) by definition, and therefore a theorem in PL(Γ) since propositional logic is completePlanetmathPlanetmathPlanetmathPlanetmathPlanetmath with respect to truth-value semantics. If A1,\ldot,An is a deductionMathworldPlanetmathPlanetmath of A (with An=A), then each Ai is either an axiom, or is obtained by an application of modus ponens. If Ai is an axiom (of PL(Γ)), it is an instance of one of the first three axiom schemas of FO(Σ) above, which means that Ai is an axiom of FO(Σ). Furthermore, since modus ponens is a rule of inference for FO(Σ), A1,,An is a deduction of A in FO(Σ), which means that A 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, x(x=y)(z=y) is an instance of the fourth axiom schema, which takes the form CD, where C is a quasi-atom, and D an atom, both of which are atoms of PL(Γ). Any truth-valuation that takes C to 1 and D to 0, takes CD to 0. Therefore, x(x=y)(z=y) is not a tautology. ∎

Title tautologies in predicate logic
Canonical name TautologiesInPredicateLogic
Date of creation 2013-03-22 19:32:25
Last modified on 2013-03-22 19:32:25
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 15
Author CWoo (3771)
Entry type Definition
Classification msc 03B10