mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal ...

, 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 Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations b ...

first-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...

. *

Rules of inference In the philosophy of logic, a rule of inference, inference rule or transformation rule is a logical form consisting of a function which takes premises, analyzes their syntax, and returns a conclusion (or conclusions). For example, the rule of ...

: List of rules that can be employed to prove theorems from axioms and theorems. *

Axioms An axiom, postulate, or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word (), meaning 'that which is thought worthy or f ...

: Formulas in ''L'' assumed to be valid. All theorems are derived from axioms. Usually a given proof calculus encompasses more than a single particular formal system, since many proof calculi are under-determined and can be used for radically different logics. For example, a paradigmatic case is the

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 ...

, which can be used to express the consequence relations of both

intuitionistic logic Intuitionistic logic, sometimes more generally called constructive logic, refers to systems of symbolic logic that differ from the systems used for classical logic by more closely mirroring the notion of constructive proof. In particular, systems ...

and

relevance logic Relevance logic, also called relevant logic, is a kind of non-classical logic requiring the antecedent and consequent of implications to be relevantly related. They may be viewed as a family of substructural or modal logics. It is generally, but ...

. Thus, loosely speaking, a proof calculus is a template or

design pattern A design pattern is the re-usable form of a solution to a design problem. The idea was introduced by the architect Christopher Alexander and has been adapted for various other disciplines, particularly software engineering. The "Gang of Four" boo ...

, characterized by a certain style of formal inference, that may be specialized to produce specific formal systems, namely by specifying the actual inference rules for such a system. There is no consensus among logicians on how best to define the term.

Examples of proof calculi

The most widely known proof calculi are those classical calculi that are still in widespread use: *The class of

Hilbert system :''In mathematical physics, ''Hilbert system'' is an infrequently used term for a physical system described by a C*-algebra.'' In logic, especially mathematical logic, a Hilbert system, sometimes called Hilbert calculus, Hilbert-style deductive s ...

s, of which the most famous example is the 1928 Hilbert–Ackermann system of

; *

Gerhard Gentzen Gerhard Karl Erich Gentzen (24 November 1909 – 4 August 1945) was a German mathematician and logician. He made major contributions to the foundations of mathematics, proof theory, especially on natural deduction and sequent calculus. He died ...

's calculus of

natural deduction In logic and proof theory, natural deduction is a kind of proof calculus in which logical reasoning is expressed by inference rules closely related to the "natural" way of reasoning. This contrasts with Hilbert-style systems, which instead use ax ...

, which is the first formalism of structural proof theory, and which is the cornerstone of the formulae-as-types correspondence relating logic to

functional programming In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that ...

; *Gentzen's

, which is the most studied formalism of structural proof theory. Many other proof calculi were, or might have been, seminal, but are not widely used today. *

Aristotle Aristotle (; grc-gre, Ἀριστοτέλης ''Aristotélēs'', ; 384–322 BC) was a Greek philosopher and polymath during the Classical period in Ancient Greece. Taught by Plato, he was the founder of the Peripatetic school of ph ...

's syllogistic calculus, presented in the ''

Organon The ''Organon'' ( grc, Ὄργανον, meaning "instrument, tool, organ") is the standard collection of Aristotle's six works on logical analysis and dialectic. The name ''Organon'' was given by Aristotle's followers, the Peripatetics. The six ...

'', readily admits formalisation. There is still some modern interest in syllogisms, carried out under the

aegis The aegis ( ; grc, αἰγίς ''aigís''), as stated in the ''Iliad'', is a device carried by Athena and Zeus, variously interpreted as an animal skin or a shield and sometimes featuring the head of a Gorgon. There may be a connection with a d ...

term logic In philosophy, term logic, also known as traditional logic, syllogistic logic or Aristotelian logic, is a loose name for an approach to formal logic that began with Aristotle and was developed further in ancient history mostly by his followers, ...

. *

Gottlob Frege Friedrich Ludwig Gottlob Frege (; ; 8 November 1848 – 26 July 1925) was a German philosopher, logician, and mathematician. He was a mathematics professor at the University of Jena, and is understood by many to be the father of analytic ph ...

's two-dimensional notation of the ''

Begriffsschrift ''Begriffsschrift'' (German for, roughly, "concept-script") is a book on logic by Gottlob Frege, published in 1879, and the formal system set out in that book. ''Begriffsschrift'' is usually translated as ''concept writing'' or ''concept notatio ...

'' (1879) is usually regarded as introducing the modern concept of quantifier to logic. * C.S. Peirce's existential graph easily might have been seminal, had history worked out differently. Modern research in logic teems with rival proof calculi: *Several systems have been proposed that replace the usual textual syntax with some graphical syntax. proof nets and

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 ...

are among such systems. *Recently, many logicians interested in structural proof theory have proposed calculi with

deep inference Deep inference names a general idea in structural proof theory that breaks with the classical sequent calculus by generalising the notion of structure to permit inference to occur in contexts of high structural complexity. The term ''deep inferenc ...

, for instance

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 ...

, hypersequents, the calculus of structures, and bunched implication.

References

{{Reflist Proof theory Logical calculi

Overview

Examples of proof calculi

See also

References