|
Proof theory is a branch of mathematical logic that represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as inductively-defined data structures such as plain lists, boxed lists, or trees, which are constructed according to the axioms and rules of inference of the logical system. As such, proof theory is syntactic in nature, in contrast to model theory, which is semantic in nature. Together with model theory, axiomatic set theory, and recursion theory, proof theory is one of the so-called four pillars of the foundations of mathematics. Mathematical logic is a subfield of mathematics that is concerned with formal systems in relation to the way that they encode intuitive concepts of mathematical objects such as sets and numbers, proofs, and computation. ...
In mathematics, a proof is a demonstration that, assuming certain axioms, some statement is necessarily true. ...
A binary tree, a simple type of branching linked data structure. ...
This article does not cite its references or sources. ...
In logic, especially in mathematical logic, a rule of inference is a scheme for constructing valid inferences. ...
Syntax in logic is a systematic statement of the rules governing the properly formed formulas (WFFs) of a logical system. ...
In mathematics, model theory is the study of the representation of mathematical concepts in terms of set theory, or the study of the structures that underlie mathematical systems. ...
The truth conditions of various sentences we may encounter in arguments will depend upon their meaning, and so conscientious logicians cannot completely avoid the need to provide some treatment of the meaning of these sentences. ...
In mathematics, model theory is the study of the representation of mathematical concepts in terms of set theory, or the study of the structures that underlie mathematical systems. ...
This article or section is in need of attention from an expert on the subject. ...
Recursion theory, or computability theory, is a branch of mathematical logic dealing with generalizations of the notion of computable function, and with related notions such as Turing degrees and effective descriptive set theory. ...
Foundations of mathematics is a term sometimes used for certain fields of mathematics itself, namely for mathematical logic, axiomatic set theory, proof theory, model theory, and recursion theory. ...
Proof theory can also be considered a branch of philosophical logic, where the primary interest is in the idea of a proof-theoretic semantics, an idea which depends upon technical ideas in structural proof theory to be feasible. Philosophical logic is the application of formal logical techniques to problems that concern philosophers. ...
Proof-theoretic semantics is an approach to the semantics of logic that attempts to locate the meaning of propositions and logical connectives not in terms of interpretations, as in Tarskian approaches to semantics, but in the role that the proposition or logical connective plays within the system of inference. ...
In mathematical logic, structural proof theory is the subdiscipline of proof theory that studies proof calculi that support a notion of analytic proof. ...
History
Although the formalisation of logic was much advanced by the work of such figures as Gottlob Frege, Giuseppe Peano, Bertrand Russell, and Richard Dedekind, the story of modern proof theory is often seen as being established by David Hilbert, who initiated what is called Hilbert's program in the foundations of mathematics. Kurt Gödel's seminal work on proof theory first advanced, then refuted this program: his completeness theorem initially seemed to bode well for Hilbert's aim of reducing all mathematics to a finitist formal system; then his incompleteness theorems showed that this is unattainable. All of this work was carried out with the proof calculi called the Hilbert systems. Friedrich Ludwig Gottlob Frege (8 November 1848, Wismar – 26 July 1925, IPA: ) was a German mathematician who became a logician and philosopher. ...
Giuseppe Peano Giuseppe Peano (August 27, 1858 – April 20, 1932) was an Italian mathematician and philosopher best known for his contributions to set theory. ...
Bertrand Arthur William Russell, 3rd Earl Russell OM FRS (18 May 1872 – 2 February 1970), was a British philosopher, logician, and mathematician. ...
Richard Dedekind Julius Wilhelm Richard Dedekind (October 6, 1831 – February 12, 1916) was a German mathematician who did important work in abstract algebra and the foundations of the real numbers. ...
David Hilbert (January 23, 1862, Königsberg, East Prussia – February 14, 1943, Göttingen, Germany) was a German mathematician, recognized as one of the most influential and universal mathematicians of the 19th and early 20th centuries. ...
Hilberts program, formulated by German mathematician David Hilbert in the 1920s, was to formalize all existing theories to a finite, complete set of axioms, and provide a proof that these axioms were consistent. ...
Foundations of mathematics is a term sometimes used for certain fields of mathematics itself, namely for mathematical logic, axiomatic set theory, proof theory, model theory, and recursion theory. ...
Kurt Gödel (IPA: ) (April 28, 1906 Brno, then Austria-Hungary, now Czech Republic – January 14, 1978 Princeton, New Jersey) was an Austrian logician, mathematician, and philosopher of mathematics One of the most significant logicians of all time, Gödels work has had immense impact upon scientific and philosophical...
Gödels completeness theorem is an important theorem in mathematical logic which was first proved by Kurt Gödel in 1929. ...
In mathematical logic, Gödels incompleteness theorems are two celebrated theorems proven by Kurt Gödel in 1931. ...
The phrase Hilbert-style deduction system denotes a specific formalization of the notion of deduction in first-order logic [1], attributed to Gottlob Frege and David Hilbert. ...
In parallel with the proof theoretic work of Gödel, Gerhard Gentzen was laying the foundations of what is now known as structural proof theory. In a few short years, Gentzen introduced the core formalisms of natural deduction (simultaneously with and independently of Jaskowski) and the sequent calculus, made fundamental advances in the formalisation of intuitionistic logic, introduced the important idea of analytic proof, and provided the first combinatorial proof of the consistency of Peano arithmetic. Gerhard Gentzen (November 24, 1909 – August 4, 1945) was a German mathematician and logician. ...
In mathematical logic, natural deduction is an approach to proof theory that attempts to provide a formal model of logical reasoning as it naturally occurs. ...
In proof theory and mathematical logic, the sequent calculus is a widely known deduction system for first-order logic (and propositional logic as a special case of it). ...
In structural proof theory, an analytical proof is a proof whose structure is simple in a special way. ...
In mathematics, the Peano axioms (or Peano postulates) are a set of first-order axioms proposed by Giuseppe Peano which determine the theory of Peano arithmetic (also known as first-order 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 would have all the drawbacks of programming in machine code. Machine code or machine language is a system of instructions and data directly understandable by a computers central processing unit. ...
Formal proofs are constructed with the help of computers in automated theorem proving. Significantly, these proofs can be checked automatically, also by computer. (Checking formal proofs is usually trivial, whereas finding proofs is typically quite hard.) An informal proof in the mathematics literature, by contrast, requires weeks of peer review to be checked, and may still contain errors. Automated theorem proving (ATP), symbolic analysis, automated deduction, symbolic reasoning, or symbolic deduction, currently the most well-developed subfield of automated reasoning (AR), is the proving of mathematical theorems by a computer program. ...
Peer review (known as refereeing in some academic fields) is a scholarly process used in the publication of manuscripts and in the awarding of funding for research. ...
Kinds of proof calculi The three most well-known styles of proof calculi are: Each of these can given a complete and axiomatic formalization of propositional or predicate logic of either the classical or intuitionistic flavour, almost any modal logic, and many substructural logics, such as relevance logic or linear logic. Indeed it is unusual to find a logic that resists being represented in one of these calculi. The phrase Hilbert-style deduction system denotes a specific formalization of the notion of deduction in first-order logic [1], attributed to Gottlob Frege and David Hilbert. ...
In mathematical logic, natural deduction is the name given to a class of foundational approaches for two key concepts in logic, propositions and proofs. ...
In proof theory and mathematical logic, the sequent calculus is a widely known deduction system for first-order logic (and propositional logic as a special case of it). ...
Propositional logic or sentential logic is the logic of propositions, sentences, or clauses. ...
...
Classical logic identifies a class of formal logics that have been most intensively studied and most widely used. ...
Intuitionistic logic, or constructivist logic, is the logic used in mathematical intuitionism and other forms of mathematical constructivism. ...
In philosophical logic, a modal logic is any logic for handling modalities: concepts like possibility, impossibility, and necessity. ...
In mathematical logic, in particular in connection with proof theory, a number of substructural logics have been introduced, as systems of propositional calculus that are weaker than the conventional one. ...
Relevance logic, also called relevant logic, is any of a family of non-classical substructural logics that impose certain restrictions on implication. ...
In mathematical logic, linear logic is a type of substructural logic that denies the structural rules of weakening and contraction. ...
Consistency proofs Main article: Consistency proof In mathematical logic, a formal system is consistent if it does not contain a contradiction, or, more precisely, for no proposition φ are both φ and ¬φ provable. ...
As previously mentioned, the spur for the mathematical investigation of proofs in formal theories was Hilbert's program. The central idea of this program was that if we could give finitary 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 Π01 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. Hilberts program, formulated by German mathematician David Hilbert in the 1920s, was to formalize all existing theories to a finite, complete set of axioms, and provide a proof that these axioms were consistent. ...
In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene hierarchy classifies the set of arithmetic formulas (or arithmetic sets) according to their degree of solvability. ...
The failure of the program was induced by Kurt Gödel's incompleteness theorems, which showed that any ω-consistent theory that is sufficiently strong to express certain simple arithmetic truths, cannot prove its own consistency, which on Gödel's formulation is a sentence. Kurt Gödel (IPA: ) (April 28, 1906 Brno, then Austria-Hungary, now Czech Republic – January 14, 1978 Princeton, New Jersey) was an Austrian logician, mathematician, and philosopher of mathematics One of the most significant logicians of all time, Gödels work has had immense impact upon scientific and philosophical...
In mathematical logic, Gödels incompleteness theorems, proved by Kurt Gödel in 1931, are two celebrated theorems stating inherent limitations of all but the most trivial formal systems for arithmetic of mathematical interest. ...
In mathematical logic, an ω-consistent (or omega-consistent) theory is a theory (collection of sentences) that is not only consistent (that is, does not prove a contradiction), but also avoids proving certain infinite combinations of sentences that are intuitively contradictory. ...
Much investigation has been carried out on this topic since, which has in particular led to:
- Refinement of Gödel's result, particularly J. Barkley Rosser'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 logic;
- Transfinite iteration of theories, due to Alan Turing and Solomon Feferman;
- The recent discovery of self-verifying theories, systems strong enough to talk about themselves, but too weak to carry out the diagonal argument that is the key to Gödel's unprovability argument.
John Barkley Rosser Sr. ...
Provability logic, or the logic of provability, is a modal logic where the necessity operator is interpreted as provability in a reasonably rich formal theory such as Peano arithmetic. ...
Alan Mathison Turing, OBE (June 23, 1912 – June 7, 1954), was an English mathematician, logician, and cryptographer. ...
Solomon Feferman is a mathematician and philosopher at Stanford University. ...
Self-verifying theories are consistent first-order systems of arithmetic much weaker than Peano arithmetic that are capable of proving their own consistency. ...
Structural proof theory Main article: Structural proof theory In mathematical logic, structural proof theory is the subdiscipline of proof theory that studies proof calculi that support a notion of analytic proof. ...
Structural proof theory is the subdiscipline of proof theory that studies proof calculi that support a notion of analytic proof. The notion of analytic proof was introduced by Gentzen for the sequent calculus; there the analytic proofs are those that are cut-free. His natural deduction calculus also supports a notion of analytic proof, as shown by Dag Prawitz. The definition is slightly more complex: we say the analytic proofs are the normal forms, which are related to the notion of normal form in term rewriting. More exotic proof calculi such as Jean-Yves Girard's proof nets also support a notion of analytic proof. In structural proof theory, an analytical proof is a proof whose structure is simple in a special way. ...
The Cut-elimination theorem is the central result establishing the significance of the sequent calculus. ...
Dag Prawitz (born 1936) is a Swedish philosopher and logician. ...
In mathematical logic, natural deduction is an approach to proof theory that attempts to provide a formal model of logical reasoning as it naturally occurs. ...
Jean-Yves Girard is a French mathematician working in proof theory. ...
In proof theory, proof nets are a geometrical method of representing proofs that eliminates irrelevant syntactical features of regular proof calculi such as the natural deduction calculus and the sequent calculus; by this means the formal properties of proof identity correspond more closely to the intuitively desirable properties. ...
Structural proof theory is connected to type theory by means of the Curry-Howard correspondence, which observes a structural analogy between the process of normalisation in the natural deduction calculus and beta reduction in the typed lambda calculus. This provides the foundation for the intuitionistic type theory developed by Per Martin-Löf, and is often extended to a three way correspondence, the third leg of which are the cartesian closed categories. At the broadest level, type theory is the branch of mathematics and logic that first creates a hierarchy of types, then assigns each mathematical (and possibly other) entity to a type. ...
The Curry-Howard correspondence is the close relationship between computer programs and mathematical proofs; the correspondence is also known as the Curry-Howard isomorphism, or the formulae-as-types correspondence. ...
Typed versions of the lambda calculus extend the standard lambda calculus with types. ...
Intuitionistic Type Theory, or Constructive Type Theory, or Martin-Löf Type Theory or just Type Theory (with capital letters) is at the same time a functional programming language, a logic and a set theory based on the principles of mathematical constructivism. ...
Per Martin-Löf 2004 Per Martin-Löf is a Swedish logician, philosopher, and mathematician born in 1942. ...
In category theory, a category is cartesian closed if, roughly speaking, any morphism defined on a product of two objects can be naturally identified with a morphism defined on one of the factors. ...
In linguistics, type-logical grammar, categorial grammar and Montague grammar apply formalisms based on structural proof theory to give a formal natural language semantics. Linguistics is the scientific study of language. ...
Categorial grammar is a term used for a family of formalisms in natural language syntax motivated by the principle of compositionality and organized according to the view that syntactic constituents should generally combine as functions or according to a function-argument relationship. ...
Montague grammar is an approach to natural language semantics, based on formal logic, especially lambda calculus and set theory. ...
Tableau systems Main article: Tableau systems Analytic tableaux, or, more briefly, just tableaux, are a fundamental concept in automated theorem proving. ...
Tableau systems 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.
Ordinal analysis Main article: Ordinal analysis
Ordinal analysis is a powerful technique for providing combinatorial consistency proofs for theories formalising arithmetic and analysis.
Substructural logics Main article: Substructural logic In mathematical logic, in particular in connection with proof theory, a number of substructural logics have been introduced, as systems of propositional calculus that are weaker than the conventional one. ...
See also In analytical calculus (often times known as advanced calculus, a specific subset of mathematical analysis), there are three important methods to determine that a given hypothesis is true or false. ...
Intermediate logics are intermediate between intuitionistic logic and classical logic in the sense that they contain theorems that are not provable in intuitionistic logic, without giving rise to the whole of classical logic. ...
Proof-theoretic semantics is an approach to the semantics of logic that attempts to locate the meaning of propositions and logical connectives not in terms of interpretations, as in Tarskian approaches to semantics, but in the role that the proposition or logical connective plays within the system of inference. ...
References |
Feeds |
Contact