tautology

In boolean propositional logic, a *tautology* is any proposition whose validity is unconditional — independent of the validity of its propositional variables. Several generalizations are possible. On the one hand, the family of boolean tautologies is also the family of boolean theorems: a proposition is a boolean tautology iff it has a boolean proof. On the other hand, construing a boolean proposition as a universalized equation in the language of boolean algebras, the boolean propositions are also the (universal, first-order) propositions of the form $P(x_1,...,x_n) = \top$ that are valid in every boolean algebra.

Of course, tautologies exist in other logics besides boolean logic, although boolean logic is perhaps the simplest nontrivial case.

Given a logic, a context $\Gamma$ within that logic, and a class of models of $\Gamma$, a **tautology** is a proposition $\phi$ in $\Gamma$ that is true in all models; that is,

$\mathcal{M} \vDash \phi$

for every model $\mathcal{M}$.

Compare the notion of **theorem**, sometimes called a *syntactic tautology*, which asks that $\phi$ be *provable* in $\Gamma$:

$\Gamma \vdash \phi .$

In the best behaved cases, each context has a free model? such that the theorems are precisely the tautologies for the free model. (For example, in the case of boolean propositional logic, the free model for the context with $n$ variables is the free boolean algebra on $n$ generators.) Even without this, there may be a class of models that can be proved to be sound? (every theorem is a tautology) and complete (every tautology is a theorem).

Revised on May 9, 2017 03:47:11
by David Corfield
(129.12.18.176)