Tautology (logic) - Tautologies Versus Validities in First-order Logic

Tautologies Versus Validities in First-order Logic

The fundamental definition of a tautology is in the context of propositional logic. The definition can be extended, however, to sentences in first-order logic (see Enderton (2002, p. 114) and Kleene (1967 secs. 17–18)). These sentences may contain quantifiers, unlike sentences of propositional logic. In the context of first-order logic, a distinction is maintained between logical validities, sentences that are true in every model, and tautologies, which are a proper subset of the first-order logical validities. In the context of propositional logic, these two terms coincide.

A tautology in first-order logic is a sentence that can be obtained by taking a tautology of propositional logic and uniformly replacing each propositional variable by a first-order formula (one formula per propositional variable). For example, because is a tautology of propositional logic, is a tautology in first order logic. Similarly, in a first-order language with a unary relation symbols R,S,T, the following sentence is a tautology:

It is obtained by replacing with, with, and with in the propositional tautology .

Not all logical validities are tautologies in first-order logic. For example, the sentence

is true in any first-order interpretation, but it corresponds to the propositional sentence which is not a tautology of propositional logic.