Concept
Sequent calculus
Overview
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 is inferred from other conditional tautologies on earlier lines in a formal argument according to rules and procedures of inference, giving a better approximation to the natural style of deduction used by mathematicians than David Hilbert's earlier style of formal logic, in which every line was an unconditional tautology. More subtle distinctions may exist; for example, propositions may implicitly depend upon non-logical axioms. In that case, sequents signify conditional theorems of a first-order theory rather than conditional tautologies.
Sequent calculus is one of several extant styles of proof calculus for expressing line-by-line logical arguments.
Hilbert style. Every line is an unconditional tautology (or theorem).
Gentzen style. Every line is a conditional tautology (or theorem) with zero or more conditions on the left.
Natural deduction. Every (conditional) line has exactly one asserted proposition on the right.
Sequent calculus. Every (conditional) line has zero or more asserted propositions on the right.
In other words, natural deduction and sequent calculus systems are particular distinct kinds of Gentzen-style systems. Hilbert-style systems typically have a very small number of inference rules, relying more on sets of axioms. Gentzen-style systems typically have very few axioms, if any, relying more on sets of rules.
Gentzen-style systems have significant practical and theoretical advantages compared to Hilbert-style systems. For example, both natural deduction and sequent calculus systems facilitate the elimination and introduction of universal and existential quantifiers so that unquantified logical expressions can be manipulated according to the much simpler rules of propositional calculus. In a typical argument, quantifiers are eliminated, then propositional calculus is applied to unquantified expressions (which typically contain free variables), and then the quantifiers are reintroduced. This very much parallels the way in which mathematical proofs are carried out in practice by mathematicians. Predicate calculus proofs are generally much easier to discover with this approach, and are often shorter. Natural deduction systems are more suited to practical theorem-proving. Sequent calculus systems are more suited to theoretical analysis.
Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).
Possible passages
Found by search and not yet checked by a person; they may only mention the idea in passing.
To complete this rapid general enumeration of the different essential parts of the calculus of direct functions, I must, lastly, mention expressly one of the most fruitful and important theories of algebra proper, that relating to the transformation of functions into series by the aid of what is called the _Method of indeterminate Coefficients_. This method, so eminently analytical, and which must be regarded as one…
Auguste Comte, The philosophy of mathematics
States what Sequent calculus is.
This is nothing else than the necessity of abstract logic, which is the presupposition involved in the very fact of interrelated existence as disclosed in each immediate occasion of experience. The key to the pattern means this fact:—that from a select set of those general conditions, exemplified in any one and the same occasion, a pattern involving an infinite variety of other such conditions, also exemplified in…
Alfred North Whitehead, Science and the modern world
States what Sequent calculus is.
We have suffered much from critics who consider it sufficient to criticise our procedure on the slender basis of a knowledge of the dictionary meanings of such terms. For example, a one-to-one correlation depends on the notion of a class with only one member, and this notion is defined without appeal to the concept of the number one. The notion of diversity is all that is wanted. Thus the class α has only one…
Alfred North Whitehead, The organisation of thought, educational and scientific
States what Sequent calculus is.
Philosophers who discussed Sequent calculus
Related ideas
- Method of analytic tableaux
- First-order logic
- Artificial intelligence
- Argument
- Free variables and bound variables
- If and only if
- Judgment (mathematical logic)
- Truth value
- Intuitionistic logic
- Law of excluded middle
- Logical conjunction
- Propositional logic
- Proof theory
- Modus ponens
- Mathematical logic
- Hypothesis
- Rule of inference
- Set (mathematics)
- Soundness
- Proof (truth)
- Stephen Cole Kleene
- Semantics
- Theorem
- Completeness (logic)
Place in the tradition
Part of First-order logic.