In structural proof theory, an analytical proof is a proof whose structure is simple in a special way. The term does not admit an uncontroversial definition, but for several proof calculi there is an accepted notion of analytic proof. For example: In mathematical logic, structural proof theory is the subdiscipline of proof theory that studies proof calculi that support a notion of analytic proof. ...
In Gentzen's natural deduction calculus the analytic proofs are those in normal form; that is, no formula occurrence is both the principal premise of an elimination rule and the conclusion of an introduction rule;
In Gentzen's sequent calculus the analytic proofs are those that do not use the cut rule.
However it is possible to extend both calculi so that there are proofs that satisfy the condition but are not analytic: a particularly tricky example of this is the analytic cut rule: this is a special case of the cut rule where the cut formula is a subformula of side formulae of the cut rule; a proof that contains an analytic cut is by virtue of that rule not analytic. 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). ... The Cut-elimination theorem is the central result establishing the significance of the sequent calculus. ...
For example, "additive number theory" asks about ways of expressing an integer N as a sum of integers a_i in a set A. If we set f(z) = Sum exp(2 pi i a_i z), then f(z)^k has exp(2 pi i N z) as a summand iff N is a sum of k of the a_i.
Thus analytical techniques are used to approach Waring's problem, for example (representing integers as sums of squares, cubes, etc.), and to address other questions with exponential sums.
Even when few analytic tools are used for the analysis of the functions themselves, the groups of interest (e.g.
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.
Structural proof theory is the subdiscipline of proof theory that studies proof calculi that support a notion of analyticproof.
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.
Feeds |
Contact