Analytic proof

In mathematics, an analytic proof is a proof of a theorem in analysis that only makes use of methods from analysis, and which does not predominantly make use of algebraic or geometrical methods. 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 a proof of the theorem which was free from intuitions concerning lines crossing each other at a point, and so he felt happy calling it analytic (Bolzano 1817).

Bolzano's philosophical work encouraged a more abstract reading of when a demonstration could be regarded as analytic, where a proof is analytic if it does not go beyond its subject matter (Sebastik 2007). In proof theory, an analytic proof has come to mean a proof whose structure is simple in a special way, due to conditions on the kind of inferences that ensure none of them go beyond what is contained in the assumptions and what is demonstrated.

Structural proof theory

In proof theory, the notion of analytic proof provides the fundamental concept that brings out the similarities between a number of essentially distinct proof calculi, so defining the subfield of structural proof theory. There is no uncontroversial general definition of analytic proof, but for several proof calculi there is an accepted notion. For example:

  • In Gerhard 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 the inference rules of both calculi so that there are proofs that satisfy the condition but are not analytic. For example, a particularly tricky example of this is the analytic cut rule, used widely in the tableau method, which 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.

Furthermore, structural proof theories that are not analogous to Gentzen's theories have other notions of analytic proof. For example, the calculus of structures organises its inference rules into pairs, called the up fragment and the down fragment, and an analytic proof is one that only contains the down fragment.

gollark: You should install a package for that?
gollark: It should! The minefield of bad ones is annoying!
gollark: `/usr/share/dict/words`
gollark: Accursed configure scripts.
gollark: It's a lowest common denominator. If you want to bind two high-level languages together it may be more practical, if arguably awful, to just shove JSON over IPC pipes between them.

See also

References
  • Bernard Bolzano (1817). Purely analytic proof of the theorem that between any two values which give results of opposite sign, there lies at least one real root of the equation. In Abhandlungen der koniglichen bohmischen Gesellschaft der Wissenschaften Vol. V, pp.225-48.
  • Pfenning (1984). Analytic and Non-analytic Proofs. In Proc. 7th International Conference on Automated Deduction.
  • Sebastik (2007). Bolzano's Logic. Entry in the Stanford Encyclopedia of Philosophy.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.