Deducibility

Deducibility, in formal logic, is the relation that a formula φ is derivable from a set of premises Γ using a specified deductive system. It is usually denoted Γ ⊢ φ. Deducibility is a syntactic notion, in contrast to semantic consequence, which is defined semantically.

In a deductive system, a theory or set of premises Γ consists of axioms and inference rules. A formula φ is deducible from Γ if there exists a finite sequence of formulas, called a proof, such that each formula is either an axiom, a member of Γ, or obtained from earlier formulas by an allowed rule; the last formula is φ. If Γ is empty, φ is a theorem.

Typical examples include propositional logic and first‑order logic. From Γ = {A, A→B} one can deduce B by modus ponens, or from {∀x P(x), P(a)} deduce P(a). In classical logic, inconsistent theories may prove every formula (the principle of explosion).

Deducibility is related to provability. For a fixed theory T, φ is deducible from T precisely when T ⊢ φ. Soundness ensures that deducible formulas are semantically valid (T ⊨ φ); completeness ensures that every semantically valid φ is deducible (T ⊢ φ). The deduction theorem connects deducibility with implications: if Γ ∪ {φ} ⊢ ψ, then Γ ⊢ φ → ψ, given suitable conditions.

Applications include mathematics, automated theorem proving, and formal verification. Limitations arise in non-classical logics and in inconsistent theories, where deducibility can be degenerate or require alternative proof systems. See also provability, semantic consequence, deduction theorem, sequent calculus.