Structural Proof Theory Information (Analytic Proof) @ Pr00f.com

In mathematical logic Mathematical logic is a subfield of mathematics with close connections to computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics. The unifying themes in mathematical logic include the study of the expressive power of formal systems and the, structural proof theory is the subdiscipline of proof theory 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 that studies proof calculi In mathematical logic, a proof calculus corresponds to a family of formal systems that use a common style of formal inference for its inference rules. The specific inference rules of a member of such a family characterize the theory of a logic that support a notion of analytic proof In mathematical analysis, an analytical proof is a proof of a theorem in analysis that only makes use of methods from analysis, and which does not make use of results from geometry. The term was first used by Bernard Bolzano, who first provided a non-analytic proof of his intermediate value theorem and then, several years later provided proof of.

1 Analytic proof
2 Structures and connectives
3 Cut-elimination in the sequent calculus
4 Natural deduction and the formulae-as-types correspondence
5 Logical duality and harmony
6 Display logic
7 Calculus of structures

Analytic proof

Main article: analytic proof In mathematical analysis, an analytical proof is a proof of a theorem in analysis that only makes use of methods from analysis, and which does not make use of results from geometry. The term was first used by Bernard Bolzano, who first provided a non-analytic proof of his intermediate value theorem and then, several years later provided proof of

The notion of analytic proof was introduced into proof theory by Gerhard Gentzen Gerhard Karl Erich Gentzen was a German mathematician and logician. He had his major contributions in the foundation of mathematics, proof theory, especially on natural deduction and sequent calculus. He died in 1945 after the Second World War, because he was deprived of food after being arrested in Prague for the sequent calculus In proof theory and mathematical logic, sequent calculus is a widely known family of formal systems sharing a certain style of inference and certain formal properties. The first sequent calculi, systems LK and LJ, were introduced by Gerhard Gentzen in 1934, as a tool for studying natural deduction in first-order logic. Gentzen's so-called "; these are the analytic proofs are those that are cut-free The cut-elimination theorem is the central result establishing the significance of the sequent calculus. It was originally proved by Gerhard Gentzen 1934 in his landmark paper "Investigations in Logical Deduction" for the systems LJ and LK formalising intuitionistic and classical logic respectively. The cut-elimination theorem states. His natural deduction calculus also supports a notion of analytic proof, as was shown by Dag Prawitz; the definition is slightly more complex — we say the analytic proofs are the normal forms 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 the axiomatic systems which instead use axioms as much as possible to express the logical laws of deductive reasoning, which are related to the notion of normal form in term rewriting.

Structures and connectives

The term structure in structural proof theory comes from a technical notion introduced in the sequent calculus: the sequent calculus represents the judgement made at any stage of an inference using special, extra-logical operators which we call structural operators: in , the commas to the left of the turnstile In mathematical logic and computer science the symbol has taken the name turnstile because of its resemblance to a typical turnstile if viewed from above. It is also referred to as tee and is often read as "yields" or "proves". The symbol was first used by Gottlob Frege in his 1879 book on logic, Begriffsschrift are operators normally interpreted as conjunctions, those to the right as disjunctions, whilst the turnstile symbol itself is interpreted as an implication. However, it is important to note that there is a fundamental difference in behaviour between these operators and the logical connectives In logic, a logical connective is a symbol or word used to connect two or more sentences (of either a formal or a natural language) in a grammatically valid way, such that the compound sentence produced has a truth value dependent on the respective truth values of the original sentences they are interpreted by in the sequent calculus: the structural operators are used in every rule of the calculus, and are not considered when asking whether the subformula property applies. Furthermore, the logical rules go one way only: logical structure is introduced by logical rules, and cannot be eliminated once created, while structural operators can be introduced and eliminated in the course of a derivation.

The idea of looking at the syntactic features of sequents as special, non-logical operators is not old, and was forced by innovations in proof theory: when the structural operators are as simple as in Getzen's original sequent calculus there is little need to analyse them, but proof calculi of deep inference such as display logic support structural operators as complex as the logical connectives, and demand sophisticated treatment.