Deep inference names a general idea in structural proof theory that breaks with the classical

sequent calculus In mathematical logic, sequent calculus is a style of formal logical argumentation in which every line of a proof is a conditional tautology (called a sequent by Gerhard Gentzen) instead of an unconditional tautology. Each conditional tautology i ...

by generalising the notion of

structure A structure is an arrangement and organization of interrelated elements in a material object or system, or the object or system so organized. Material structures include man-made objects such as buildings and machines and natural objects such as ...

to permit inference to occur in contexts of high structural complexity. The term ''deep inference'' is generally reserved for

proof calculi In mathematical logic, a proof calculus or a proof system is built to prove statements. Overview A proof system includes the components: * Language: The set ''L'' of formulas admitted by the system, for example, propositional logic or first-order ...

where the structural complexity is unbounded; in this article we will use non-shallow inference to refer to calculi that have structural complexity greater than the sequent calculus, but not unboundedly so, although this is not at present established terminology. Deep inference is not important in logic outside of structural proof theory, since the phenomena that lead to the proposal of

formal system A formal system is an abstract structure used for inferring theorems from axioms according to a set of rules. These rules, which are used for carrying out the inference of theorems from axioms, are the logical calculus of the formal system. A form ...

s with deep inference are all related to the

cut-elimination theorem The cut-elimination theorem (or Gentzen's ''Hauptsatz'') is the central result establishing the significance of the sequent calculus. It was originally proved by Gerhard Gentzen in his landmark 1934 paper "Investigations in Logical Deduction" for ...

. The first calculus of deep inference was proposed by

Kurt Schütte Kurt Schütte (14 October 1909, Salzwedel – 18 August 1998, Munich) was a German mathematician who worked on proof theory and ordinal analysis. The Feferman–Schütte ordinal, which he showed to be the precise ordinal bound for predicativi ...

,Kurt Schütte. Proof Theory. Springer-Verlag, 1977. but the idea did not generate much interest at the time.

Nuel Belnap Nuel Dinsmore Belnap Jr. (; born 1930) is an American logician and philosopher who has made contributions to the philosophy of logic, temporal logic, and structural proof theory. He taught at the University of Pittsburgh from 1963 until his ret ...

proposed

display logic In mathematical logic, structural proof theory is the subdiscipline of proof theory that studies proof calculi that support a notion of analytic proof, a kind of proof whose semantic properties are exposed. When all the theorems of a logic formalis ...

in an attempt to characterise the essence of structural proof theory. The calculus of structures was proposed in order to give a cut-free characterisation of noncommutative logic.

Cirquent calculus Cirquent calculus is a proof calculus that manipulates graph-style constructs termed ''cirquents'', as opposed to the traditional tree-style objects such as formulas or sequents. Cirquents come in a variety of forms, but they all share one main c ...

was developed as a system of deep inference allowing to explicitly account for the possibility of subcomponent-sharing.

Notes

Further reading