nLab tautology

Tautologies

Tautologies

Idea

In common language, a tautology refers to a proposition whose truth is felt to be “trivial” or “completely obvious” or “not requiring argument or highlighting”, for instance since it follows just by unwinding definitions (“true by definition”).

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)=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.

Definition

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}.

Discussion

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 nn variables is the free boolean algebra on nn 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).

mathematical statements

References

See also:

Last revised on March 26, 2023 at 12:39:19. See the history of this page for a list of all contributions to it.