Deduction theorem

Article summary

In mathematical logic, a deduction theorem is a metatheorem that justifies doing conditional proofs from a hypothesis in systems that do not explicitly axiomatize that hypothesis, i.e. to prove an implication A \to B , it is sufficient to assume A as a hypothesis and then proceed to derive B . Deduction theorems exist for both propositional logic and first-order logic. The deduction theorem is an important tool in Hilbert-style deduction systems because it permits one to write more comprehensible and usually much shorter proofs than would be possible without it. In certain other formal proof systems the same conveniency is provided by an explicit inference rule; for example natural deduction calls it implication introduction. In more detail, the propositional logic deduction theorem states that if a formula B is deducible from a set of assumptions \Delta \cup \{A\} then the implication A \to B is deducible from \Delta ; in symbols, \Delta \cup \{A\} \vdash B implies \Delta \vdash A \to B . In the special case where \Delta is the empty set, the deduction theorem claim can be more compactly written as: A \vdash B implies \vdash A \to B . The deduction theorem for predicate logic is similar, but comes with some extra constraints (that would for example be satisfied if A is a closed formula).…

Key claims

No claims recorded.

Discussion questions

1. Summarise the article in your own words. Which single claim would you verify first, and why?
2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.