HOME

TheInfoList




Proof theory is a major branchAccording to Wang (1981), pp. 3–4, proof theory is one of four domains mathematical logic, together with
model theory In 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 ...
,
axiomatic set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, i ...
, and
recursion theory Computability theory, also known as recursion theory, is a branch of mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. ...
. Barwise (1978) consists of four corresponding parts, with part D being about "Proof Theory and Constructive Mathematics".
of
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 sys ...
that represents
proof Proof may refer to: * Proof (truth), argument or sufficient evidence for the truth of a proposition * Alcohol proof, a measure of an alcoholic drink's strength Formal sciences * Formal proof, a construct in proof theory * Mathematical proof, a co ...
s as formal
mathematical object A mathematical object is an abstract concept arising in mathematics. In the usual language of mathematics, an ''object'' is anything that has been (or could be) formally defined, and with which one may do deductive reasoning and mathematical proofs ...
s, facilitating their analysis by mathematical techniques. Proofs are typically presented as inductively-defined
data structures 315px, A data structure known as a hash table. In computer science, a data structure is a data organization, management, and storage format that enables efficient access and modification. More precisely, a data structure is a collection of dat ...
such as plain lists, boxed lists, or
tree In botany, a tree is a perennial plant with an elongated Plant stem, stem, or trunk (botany), trunk, supporting branches and leaves in most species. In some usages, the definition of a tree may be narrower, including only wood plants with se ...
s, which are constructed according to the
axiom An axiom, postulate or assumption is a statement that is taken to be truth, true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Greek ''axíōma'' () 'that which is thought worthy or fit' o ...

axiom
s and
rules of inference In the philosophy of logic Following the developments in formal logic with symbolic logic in the late nineteenth century and mathematical logic in the twentieth, topics traditionally treated by logic not being part of formal logic have tended to ...
of the logical system. Consequently, proof theory is
syntactic In linguistics Linguistics is the scientific study of language, meaning that it is a comprehensive, systematic, objective, and precise study of language. Linguistics encompasses the analysis of every aspect of language, as well as the ...
in nature, in contrast to
model theory In 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 ...
, which is
semantic Semantics (from grc, σημαντικός ''sēmantikós'', "significant") is the study of reference Reference is a relationship between objects in which one object designates, or acts as a means by which to connect to or link to, another ...
in nature. Some of the major areas of proof theory include
structural proof theoryIn mathematical logic Mathematical logic, also called formal logic, is a subfield of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algeb ...
,
ordinal analysisIn proof theory, ordinal analysis assigns ordinal number, ordinals (often large countable ordinals) to mathematical theories as a measure of their strength. If theories have the same proof-theoretic ordinal they are often equiconsistency, equiconsis ...
,
provability logicProvability logic is a modal logic, in which the box (or "necessity") operator is interpreted as 'it is provable that'. The point is to capture the notion of a proof predicate of a reasonably rich theory (mathematical logic), formal theory, such as P ...
,
reverse mathematics Reverse mathematics is a program in 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 com ...
, proof mining,
automated theorem provingAutomated theorem proving (also known as ATP or automated deduction) is a subfield of automated reasoning and mathematical logic Mathematical logic, also called formal logic, is a subfield of mathematics Mathematics (from Ancient Greek, Gree ...
, and
proof complexityIn logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, label=none, lit=possessed of reason, intellectual, dialectical, argumentative, translit=logikḗ)Also related to (''logos''), "word, thought, idea, argument, acc ...
. Much research also focuses on applications in computer science, linguistics, and philosophy.


History

Although the formalisation of logic was much advanced by the work of such figures as
Gottlob Frege Friedrich Ludwig Gottlob Frege (; ; 8 November 1848 – 26 July 1925) was a German philosopher, logician, and mathematician. He worked as a mathematics professor at the University of Jena, and is understood by many to be the father of analy ...
,
Giuseppe Peano Giuseppe Peano (; ; 27 August 1858 – 20 April 1932) was an Italian mathematician A mathematician is someone who uses an extensive knowledge of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as ...

Giuseppe Peano
,
Bertrand Russell Bertrand Arthur William Russell, 3rd Earl Russell (18 May 1872 – 2 February 1970) was a British polymath A polymath ( el, πολυμαθής, , "having learned much"; la, homo universalis, "universal human") is an individual whose know ...
, and
Richard Dedekind Julius Wilhelm Richard Dedekind (6 October 1831 – 12 February 1916) was a German German(s) may refer to: Common uses * of or related to Germany * Germans, Germanic ethnic group, citizens of Germany or people of German ancestry * For citiz ...
, the story of modern proof theory is often seen as being established by
David Hilbert David Hilbert (; ; 23 January 1862 – 14 February 1943) was a German mathematician This is a List of German mathematician A mathematician is someone who uses an extensive knowledge of mathematics Mathematics (from Ancient Greek, G ...
, who initiated what is called
Hilbert's program In mathematics, Hilbert's program, formulated by Germans, German mathematician David Hilbert in the early part of the 20th century, was a proposed solution to the foundational crisis of mathematics, when early attempts to clarify the foundations of ...
in the ''Foundations of Mathematics''. The central idea of this program was that if we could give
finitary In mathematics and logic, an Operation (mathematics), operation is finitary if it has Finite cardinality, finite arity, i.e. if it has a finite number of input values. Similarly, an infinitary operation is one with an Infinite set, infinite numbe ...
proofs of consistency for all the sophisticated formal theories needed by mathematicians, then we could ground these theories by means of a metamathematical argument, which shows that all of their purely universal assertions (more technically their provable \Pi^0_1 sentences) are finitarily true; once so grounded we do not care about the non-finitary meaning of their existential theorems, regarding these as pseudo-meaningful stipulations of the existence of ideal entities. The failure of the program was induced by
Kurt Gödel Kurt Friedrich Gödel ( , ; April 28, 1906 – January 14, 1978) was a logician Logic is an interdisciplinary field which studies truth Truth is the property of being in accord with fact or reality.Merriam-Webster's Online Dict ...
's
incompleteness theorems Complete may refer to: Logic * Completeness (logic) In mathematical logic and metalogic, a formal system is called complete with respect to a particular property (philosophy), property if every Well-formed formula, formula having the property can ...
, which showed that any
ω-consistent theory In mathematical logic, an ω-consistent (or omega-consistent, also called numerically segregative)W. V. O. Quine (1971), ''Set Theory and Its Logic''. theory is a theory (mathematical logic), theory (collection of sentence (mathematical logic), sen ...
that is sufficiently strong to express certain simple arithmetic truths, cannot prove its own consistency, which on Gödel's formulation is a \Pi^0_1 sentence. However, modified versions of Hilbert's program emerged and research has been carried out on related topics. This has led, in particular, to: *Refinement of Gödel's result, particularly
J. Barkley Rosser John Barkley Rosser Sr. (December 6, 1907 – September 5, 1989) was an United States, American logician, a student of Alonzo Church, and known for his part in the Church–Rosser theorem, in lambda calculus. He also developed what is now called t ...
's refinement, weakening the above requirement of ω-consistency to simple consistency; *Axiomatisation of the core of Gödel's result in terms of a modal language,
provability logicProvability logic is a modal logic, in which the box (or "necessity") operator is interpreted as 'it is provable that'. The point is to capture the notion of a proof predicate of a reasonably rich theory (mathematical logic), formal theory, such as P ...
; *Transfinite iteration of theories, due to
Alan Turing Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician A mathematician is someone who uses an extensive knowledge of mathematics Mathematics (from Greek: ) includes the study of such topics as numb ...

Alan Turing
and
Solomon Feferman Solomon Feferman (December 13, 1928 – July 26, 2016) was an American philosopher and mathematician who worked in mathematical logic. Life Solomon Feferman was born in The Bronx in New York City to working-class parents who had immigrated to the ...
; *The discovery of self-verifying theories, systems strong enough to talk about themselves, but too weak to carry out the
diagonal argumentDiagonal argument in mathematics may refer to: *Cantor's diagonal argument (the earliest) *Cantor's theorem *Halting problem *Diagonal lemma See also

* Diagonalization (disambiguation) {{mathdab ...
that is the key to Gödel's unprovability argument. In parallel to the rise and fall of Hilbert's program, the foundations of
structural proof theoryIn mathematical logic Mathematical logic, also called formal logic, is a subfield of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algeb ...
were being founded.
Jan Łukasiewicz Jan Łukasiewicz (; 21 December 1878 – 13 February 1956) was a Polish logician and philosopher who is best known for Polish notation and Łukasiewicz logic. He was born in Lemberg, a city in the Austrian Galicia, Galician Kingdom of Austria-Hungar ...

Jan Łukasiewicz
suggested in 1926 that one could improve on
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 sys ...
s as a basis for the axiomatic presentation of logic if one allowed the drawing of conclusions from assumptions in the inference rules of the logic. In response to this, Stanisław Jaśkowski (1929) and
Gerhard Gentzen Gerhard Karl Erich Gentzen (November 24, 1909 – August 4, 1945) was a German mathematician A mathematician is someone who uses an extensive knowledge of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such t ...

Gerhard Gentzen
(1934) independently provided such systems, called calculi of
natural deduction In logic Logic is an interdisciplinary field which studies truth and reasoning. Informal logic seeks to characterize Validity (logic), valid arguments informally, for instance by listing varieties of fallacies. Formal logic represents statemen ...
, with Gentzen's approach introducing the idea of symmetry between the grounds for asserting propositions, expressed in introduction rules, and the consequences of accepting propositions in the elimination rules, an idea that has proved very important in proof theory. Gentzen (1934) further introduced the idea of the
sequent calculusIn mathematical logic, sequent calculus is a style of formal logical argumentation in which every line of a formal proof, proof is a conditional tautology (logic), tautology (called a sequent by Gerhard Gentzen) instead of an unconditional tautology. ...
, a calculus advanced in a similar spirit that better expressed the duality of the logical connectives, and went on to make fundamental advances in the formalisation of intuitionistic logic, and provide the first
combinatorial proofIn mathematics, the term ''combinatorial proof'' is often used to mean either of two types of mathematical proof: * A proof by double counting (proof technique), double counting. A combinatorics, combinatorial identity (mathematics), identity is pro ...
of the consistency of
Peano arithmetic In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian people, Italian mathematician Giuseppe Peano. These axioms have been ...
. Together, the presentation of natural deduction and the sequent calculus introduced the fundamental idea of
analytic proofIn mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ha ...
to proof theory.


Structural proof theory

Structural proof theory is the subdiscipline of proof theory that studies the specifics of
proof calculiIn mathematical logic, a proof calculus or a proof system is built to prove statements. Overview A proof system includes the components: * Language: The set of formulas admitted by the system, for example, propositional logic or first-order logic. ...
. The three most well-known styles of proof calculi are: *The Hilbert calculi *The natural deduction calculi *The sequent calculi Each of these can give a complete and axiomatic formalization of propositional or
predicate 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 Quantifica ...
of either the
classical Classical may refer to: European antiquity *Classical antiquity, a period of history from roughly the 7th or 8th century B.C.E. to the 5th century C.E. centered on the Mediterranean Sea *Classical architecture, architecture derived from Greek and ...
or
intuitionistic In the philosophy of mathematics, intuitionism, or neointuitionism (opposed to preintuitionism), is an approach where mathematics is considered to be purely the result of the constructive mental activity of humans rather than the discovery of funda ...
flavour, almost any
modal logic Modal logic is a collection of formal system A formal system is an 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 ...
, and many
substructural logic In logic Logic is an interdisciplinary field which studies truth and reasoning. Informal logic seeks to characterize Validity (logic), valid arguments informally, for instance by listing varieties of fallacies. Formal logic represents statem ...
s, such as
relevance logic Relevance logic, also called relevant logic, is a kind of non-classical logic Classical logic (or standard logic) is the intensively studied and most widely used class of deductive logic. Classical logic has had much influence on analytic philosophy ...
or
linear logic Linear logic is a substructural logic In logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, label=none, lit=possessed of reason, intellectual, dialectical, argumentative, translit=logikḗ)Also related to (''log ...
. Indeed, it is unusual to find a logic that resists being represented in one of these calculi. Proof theorists are typically interested in proof calculi that support a notion of
analytic proofIn mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ha ...
. The notion of analytic proof was introduced by Gentzen for the sequent calculus; there the analytic proofs are those that are cut-free. Much of the interest in cut-free proofs comes from the subformula property: every formula in the end sequent of a cut-free proof is a subformula of one of the premises. This allows one to show consistency of the sequent calculus easily; if the empty sequent were derivable it would have to be a subformula of some premise, which it is not. Gentzen's midsequent theorem, the Craig interpolation theorem, and Herbrand's theorem also follow as corollaries of the cut-elimination theorem. Gentzen's natural deduction calculus also supports a notion of analytic proof, as shown by
Dag Prawitz Dag Prawitz (born 1936, Stockholm Stockholm is the Capital city, capital of Sweden. It has the most populous urban area in Sweden as well as in Scandinavia. 1 million people live in the Stockholm Municipality, municipality, approximately 1. ...
. The definition is slightly more complex: we say the analytic proofs are the
normal forms Database normalization is the process of structuring a database A database is an organized collection of data Data are units of information Information can be thought of as the resolution of uncertainty; it answers the question of ...
, which are related to the notion of normal form in term rewriting. More exotic proof calculi such as
Jean-Yves Girard Jean-Yves Girard (; born 1947) is a French logician working in proof theory. He is the research director (emeritus) at the mathematical institute of the University of Aix-Marseille, at Faculte des Sciences de Luminy, Luminy. Biography Jean-Yv ...
's proof nets also support a notion of analytic proof. A particular family of analytic proofs arising in reductive logic are focused proofs which characterise a large family of goal-directed proof-search procedures. The ability to transform a proof system into a focused form is a good indication of its syntactic quality, in a manner similar to how admissibility of cut shows that a proof system is syntactically consistent. Structural proof theory is connected to
type theory In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no gene ...
by means of the
Curry–Howard correspondence In programming language theory and proof theory Proof may refer to: * Proof (truth), argument or sufficient evidence for the truth of a proposition * Alcohol proof, a measure of an alcoholic drink's strength Formal sciences * Formal proof, a c ...
, which observes a structural analogy between the process of normalisation in the natural deduction calculus and beta reduction in the
typed lambda calculus A typed lambda calculus Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computability, computation based on function Abstraction (computer science), abstraction and function application, ap ...
. This provides the foundation for the
intuitionistic type theory Intuitionistic type theory (also known as constructive type theory, or Martin-Löf type theory) is a type theory In mathematics, logic, and computer science, a type system is a formal system in which every term has a "type" which defines its meanin ...
developed by
Per Martin-Löf Per Erik Rutger Martin-Löf (; ; born 8 May 1942) is a Sweden, Swedish logician, philosopher, and mathematical statistics, mathematical statistician. He is internationally renowned for his work on the foundations of probability, statistics, mathe ...
, and is often extended to a three way correspondence, the third leg of which are the cartesian closed categories. Other research topics in structural theory include analytic tableau, which apply the central idea of analytic proof from structural proof theory to provide decision procedures and semi-decision procedures for a wide range of logics, and the proof theory of substructural logics.


Ordinal analysis

Ordinal analysis is a powerful technique for providing combinatorial consistency proofs for subsystems of arithmetic, analysis, and set theory. Gödel's second incompleteness theorem is often interpreted as demonstrating that finitistic consistency proofs are impossible for theories of sufficient strength. Ordinal analysis allows one to measure precisely the infinitary content of the consistency of theories. For a consistent recursively axiomatized theory T, one can prove in finitistic arithmetic that the well-foundedness of a certain transfinite ordinal implies the consistency of T. Gödel's second incompleteness theorem implies that the well-foundedness of such an ordinal cannot be proved in the theory T. Consequences of ordinal analysis include (1) consistency of subsystems of classical second order arithmetic and set theory relative to constructive theories, (2) combinatorial independence results, and (3) classifications of provably total recursive functions and provably well-founded ordinals. Ordinal analysis was originated by Gentzen, who proved the consistency of Peano Arithmetic using
transfinite induction Transfinite induction is an extension of mathematical induction Mathematical induction is a mathematical proof technique. It is essentially used to prove that a statement ''P''(''n'') holds for every natural number ''n'' = 0,  ...
up to ordinal ε0. Ordinal analysis has been extended to many fragments of first and second order arithmetic and set theory. One major challenge has been the ordinal analysis of impredicative theories. The first breakthrough in this direction was Takeuti's proof of the consistency of Π-CA0 using the method of ordinal diagrams.


Provability logic

''Provability logic'' is a
modal logic Modal logic is a collection of formal system A formal system is an 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 ...
, in which the box operator is interpreted as 'it is provable that'. The point is to capture the notion of a proof predicate of a reasonably rich formal theory. As basic axioms of the provability logic GL ( Gödel- Löb), which captures provable in
Peano Arithmetic In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian people, Italian mathematician Giuseppe Peano. These axioms have been ...
, one takes modal analogues of the Hilbert-Bernays derivability conditions and Löb's theorem (if it is provable that the provability of A implies A, then A is provable). Some of the basic results concerning the incompleteness of Peano Arithmetic and related theories have analogues in provability logic. For example, it is a theorem in GL that if a contradiction is not provable then it is not provable that a contradiction is not provable (Gödel's second incompleteness theorem). There are also modal analogues of the fixed-point theorem. Robert Solovay proved that the modal logic GL is complete with respect to Peano Arithmetic. That is, the propositional theory of provability in Peano Arithmetic is completely represented by the modal logic GL. This straightforwardly implies that propositional reasoning about provability in Peano Arithmetic is complete and decidable. Other research in provability logic has focused on first-order provability logic, polymodal provability logic (with one modality representing provability in the object theory and another representing provability in the meta-theory), and
interpretability logicInterpretability logics comprise a family of modal logics that extend provability logic to describe interpretability or various related metamathematical properties and relations such as weak interpretability, Π1-conservativity, cointerpretability, ...
s intended to capture the interaction between provability and interpretability. Some very recent research has involved applications of graded provability algebras to the ordinal analysis of arithmetical theories.


Reverse mathematics

Reverse mathematics is a program in
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 sys ...
that seeks to determine which axioms are required to prove theorems of mathematics.Simpson 2010 The field was founded by
Harvey Friedman __NOTOC__ Harvey Friedman (born 23 September 1948)Handbook of Philosophical Logic, , p. 38 is an American mathematical logic Mathematical logic, also called formal logic, is a subfield of mathematics Mathematics (from Ancient Greek, Greek: ...

Harvey Friedman
. Its defining method can be described as "going backwards from the
theorem In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ge ...
s to the
axiom An axiom, postulate or assumption is a statement that is taken to be truth, true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Greek ''axíōma'' () 'that which is thought worthy or fit' o ...

axiom
s", in contrast to the ordinary mathematical practice of deriving theorems from axioms. The reverse mathematics program was foreshadowed by results in set theory such as the classical theorem that the
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product#Infinite Cartesian products, Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the a ...

axiom of choice
and
Zorn's lemma Zorn's lemma, also known as the Kuratowski–Zorn lemma, after mathematicians Max August Zorn, Max Zorn and Kazimierz Kuratowski, is a proposition of set theory. It states that a partially ordered set containing upper bounds for every chain (ord ...
are equivalent over
ZF set theoryZF, Z-F, or Zf may refer to: Businesses and organizations * ZF Friedrichshafen ZF Friedrichshafen AG, also known as ZF Group, originally ''Zahnradfabrik Friedrichshafen'', and commonly abbreviated to ZF (ZF = "Zahnradfabrik" = "Cogwheel Factory" ...
. The goal of reverse mathematics, however, is to study possible axioms of ordinary theorems of mathematics rather than possible axioms for set theory. In reverse mathematics, one starts with a framework language and a base theory—a core axiom system—that is too weak to prove most of the theorems one might be interested in, but still powerful enough to develop the definitions necessary to state these theorems. For example, to study the theorem "Every bounded sequence of
real number In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no g ...
s has a
supremum In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ge ...

supremum
" it is necessary to use a base system that can speak of real numbers and sequences of real numbers. For each theorem that can be stated in the base system but is not provable in the base system, the goal is to determine the particular axiom system (stronger than the base system) that is necessary to prove that theorem. To show that a system ''S'' is required to prove a theorem ''T'', two proofs are required. The first proof shows ''T'' is provable from ''S''; this is an ordinary mathematical proof along with a justification that it can be carried out in the system ''S''. The second proof, known as a reversal, shows that ''T'' itself implies ''S''; this proof is carried out in the base system. The reversal establishes that no axiom system ''S′'' that extends the base system can be weaker than ''S'' while still proving ''T''. One striking phenomenon in reverse mathematics is the robustness of the ''Big Five'' axiom systems. In order of increasing strength, these systems are named by the initialisms RCA0, WKL0, ACA0, ATR0, and Π-CA0. Nearly every theorem of ordinary mathematics that has been reverse mathematically analyzed has been proven equivalent to one of these five systems. Much recent research has focused on combinatorial principles that do not fit neatly into this framework, like RT (Ramsey's theorem for pairs). Research in reverse mathematics often incorporates methods and techniques from
recursion theory Computability theory, also known as recursion theory, is a branch of mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. ...
as well as proof theory.


Functional interpretations

Functional interpretations are interpretations of non-constructive theories in functional ones. Functional interpretations usually proceed in two stages. First, one "reduces" a classical theory C to an intuitionistic one I. That is, one provides a constructive mapping that translates the theorems of C to the theorems of I. Second, one reduces the intuitionistic theory I to a quantifier free theory of functionals F. These interpretations contribute to a form of Hilbert's program, since they prove the consistency of classical theories relative to constructive ones. Successful functional interpretations have yielded reductions of infinitary theories to finitary theories and impredicative theories to predicative ones. Functional interpretations also provide a way to extract constructive information from proofs in the reduced theory. As a direct consequence of the interpretation one usually obtains the result that any recursive function whose totality can be proven either in I or in C is represented by a term of F. If one can provide an additional interpretation of F in I, which is sometimes possible, this characterization is in fact usually shown to be exact. It often turns out that the terms of F coincide with a natural class of functions, such as the primitive recursive or polynomial-time computable functions. Functional interpretations have also been used to provide ordinal analyses of theories and classify their provably recursive functions. The study of functional interpretations began with Kurt Gödel's interpretation of intuitionistic arithmetic in a quantifier-free theory of functionals of finite type. This interpretation is commonly known as the
Dialectica interpretationIn proof theory, the Dialectica interpretation is a proof interpretation of intuitionistic arithmetic (Heyting arithmetic) into a finite type extension of primitive recursive arithmetic, the so-called System T. It was developed by Kurt Gödel to pr ...
. Together with the double-negation interpretation of classical logic in intuitionistic logic, it provides a reduction of classical arithmetic to intuitionistic arithmetic.


Formal and informal proof

The ''informal'' proofs of everyday mathematical practice are unlike the ''formal'' proofs of proof theory. They are rather like high-level sketches that would allow an expert to reconstruct a formal proof at least in principle, given enough time and patience. For most mathematicians, writing a fully formal proof is too pedantic and long-winded to be in common use. Formal proofs are constructed with the help of computers in interactive theorem proving. Significantly, these proofs can be checked automatically, also by computer. Checking formal proofs is usually simple, whereas ''finding'' proofs (
automated theorem provingAutomated theorem proving (also known as ATP or automated deduction) is a subfield of automated reasoning and mathematical logic Mathematical logic, also called formal logic, is a subfield of mathematics Mathematics (from Ancient Greek, Gree ...
) is generally hard. An informal proof in the mathematics literature, by contrast, requires weeks of
peer review Peer review is the evaluation of work by one or more people with similar competencies as the producers of the work ( peers). It functions as a form of self-regulation by qualified members of a profession within the relevant field Field may r ...
to be checked, and may still contain errors.


Proof-theoretic semantics

In
linguistics Linguistics is the scientific study of language A language is a structured system of communication Communication (from Latin Latin (, or , ) is a classical language belonging to the Italic languages, Italic branch of the Indo ...

linguistics
, type-logical grammar,
categorial grammar Categorial grammar is a family of formalisms in natural language In neuropsychology Neuropsychology is a branch of psychology. It is concerned with how a person's cognition and behavior are related to the brain and the rest of the nervous s ...
and
Montague grammar __notoc__ Montague grammar is an approach to natural language In neuropsychology Neuropsychology is a branch of psychology. It is concerned with how a person's cognition and behavior are related to the brain and the rest of the nervous syst ...
apply formalisms based on structural proof theory to give a formal
natural language semantics Semantics (from grc, wikt:σημαντικός, σημαντικός ''sēmantikós'', "significant") is the study of reference, Meaning (philosophy), meaning, or truth. The term can be used to refer to subfields of several distinct discipline ...
.


See also

*
Intermediate logicIn mathematical logic Mathematical logic, also called formal logic, is a subfield of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algeb ...
*
Model theory In 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 ...
*
Proof (truth) A proof is sufficient evidence Evidence for a proposition is what supports this proposition. It is usually understood as an indication that the supported proposition is true. What role evidence plays and how it is conceived varies from field ...
* Proof techniques *
Sequent calculusIn mathematical logic, sequent calculus is a style of formal logical argumentation in which every line of a formal proof, proof is a conditional tautology (logic), tautology (called a sequent by Gerhard Gentzen) instead of an unconditional tautology. ...


Notes


References

* J. Avigad and E.H. Reck (2001)
"'Clarifying the nature of the infinite': the development of metamathematics and proof theory
. Carnegie-Mellon Technical Report CMU-PHIL-120. * J. Barwise, ed. (1978). ''Handbook of Mathematical Logic''. North-Holland. * S. Buss, ed. (1998)
Handbook of Proof Theory
'' Elsevier. * A. S. Troelstra and H. Schwichtenberg (1996). ''Basic Proof Theory'', Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, . * G. Gentzen (1935/1969).
Investigations into logical deduction
. In M. E. Szabo, ed. ''Collected Papers of Gerhard Gentzen''. North-Holland. Translated by Szabo from "Untersuchungen über das logische Schliessen", ''Mathematisches Zeitschrift'' v. 39, pp. 176–210, 405 431. * D. Prawitz (1965). ''Natural deduction: A proof-theoretical study'', Dover Publications, * S.G. Simpson (2010). ''Subsystems of Second-order Arithmetic'', second edition. Cambridge University Press, . * H. Wang (1981). ''Popular Lectures on Mathematical Logic'', Van Nostrand Reinhold Company, .


External links

* *J. von Plato (2008)
The Development of Proof Theory
Stanford Encyclopedia of Philosophy The ''Stanford Encyclopedia of Philosophy'' (''SEP'') combines an online encyclopedia An online encyclopedia, also called an Internet encyclopedia, or a digital encyclopedia, is an encyclopedia An encyclopedia or encyclopaedia (British E ...
. {{Mathematical logic P Metalogic