Editing Natural deduction (section)

=== Cut (substitution) ===
{{Unreferenced section|date=May 2024}}
: ''If'' Γ ⇒ π<sub>1</sub> : ''A'' ''and'' Γ, ''u'':''A'' ⇒ π<sub>2</sub> : ''C'', ''then'' Γ ⇒ [π<sub>1</sub>/u] π<sub>2</sub> : ''C''.

In most well behaved logics, cut is unnecessary as an inference rule, though it remains provable as a [[meta-theorem]]; the superfluousness of the cut rule is usually presented as a computational process, known as ''cut elimination''. This has an interesting application for natural deduction; usually it is extremely tedious to prove certain properties directly in natural deduction because of an unbounded number of cases. For example, consider showing that a given proposition is ''not'' provable in natural deduction. A simple inductive argument fails because of rules like ∨E or E which can introduce arbitrary propositions. However, we know that the sequent calculus is complete with respect to natural deduction, so it is enough to show this unprovability in the sequent calculus. Now, if cut is not available as an inference rule, then all sequent rules either introduce a connective on the right or the left, so the depth of a sequent derivation is fully bounded by the connectives in the final conclusion. Thus, showing unprovability is much easier, because there are only a finite number of cases to consider, and each case is composed entirely of sub-propositions of the conclusion. A simple instance of this is the ''global consistency'' theorem: "⋅ ⊢ ⊥" is not provable. In the sequent calculus version, this is manifestly true because there is no rule that can have "⋅ ⇒ ⊥" as a conclusion! Proof theorists often prefer to work on cut-free sequent calculus formulations because of such properties.