Cut-elimination theorem
The Gentzensche main block and cut set is a set of mathematical logic, which states that the cut rule is valid in Gentz type calculi. It is named after Gerhard Gentzen, who set it in 1934 and proved.
The cut rule
The cut rule is the modus ponens on metalogischer level:
Suppose the sequences and are derived. The cut rule is that one can pass to the sequence then, that is, the formula is then derivable even without.
The Greek letters stand for and lists of formulas that have been derived. For the derivability here the sign is used.
Sketch of proof
Evidence for this law are now available in a simple form. The basic idea is to dissolve derivations in which the cut rule is used as (English: cut elimination ) that it is no longer used.
These leads are an induction on the number of sub-formulas in the average formula by ( partial formula induction).
Induction start ( ): When only has a partial formula, so it is not assembled, must be a prime or atomic formula:
In the simplest case, is not used in the derivation. Then this derivation is valid without, that is. This means, however, that can be derived without the cut rule.
In contrast, when present in the derivation, it is possible to replace it by the derivation. Also in this case so there is a possibility to derive without the cutting rule.
Induction step ( to ): The induction hypothesis states that the cut rule is valid for formulas that have n sub-formulas:
Now, a case distinction with respect to the in:
Newly added logic characters performed, the cut rule is thus replaced by the calculus rules for this character.
The connectives of this evidence part is relatively easy, despite the many case distinctions. In the quantifiers is induced in the dialogic proof of the number of development steps.
The ( long ) non- dialogic evidence use of technical simplification of evidence in addition to provable so called from the cut rule mixing rule ( mix ):
Is mixed formula and represents the sequence of formulas that arises when stroking in each occurrence.
Consistency
The calculi for which the law applies are consistent.
A train of thought of consistency is the following: Let ( read: wrong or falsum ), by definition, can not be derived. Then nothing but the derivability is the negation of this special case of subjunction.
Substituting now ( for ): in the cut rule:
It follows from the derivability of and ( just mentioned ) of ( both together is a contradiction in the premises ), be derivable from unherleitbaren what can not be. would - due to the removability of the cut rule - even self a valid sequence in calculus, which is not possible by definition of. Typical of these consistency proofs that only part of those formulas formulas occur in a derivation that ( ie below the final stroke ) occur in the derived tail sequence.
Consistency proofs in mathematics are carried out by, like Gerhard Gentzen, the transfinite induction or, as Kurt Schütte and Paul Lorenzen, the so-called rule in the proof of the main theorem slipstreams (full half- formalism ).
Importance and applications
The removal of sections is not only an opportunity to demonstrate the validity of the cut rule, but turned a very useful mathematical and logical tools, such as the proof of the interpolation theorem of Craig and Schütte. The possibility to carry out evidence based on resolution, is very powerful (machine -assisted proofs ). The execution of a Prolog program (ie, what happens during the Prolog program runs ) can be interpreted as a cut -free calculus derivation.
If we introduce, however, in Gentz type calculi evidence by which avoid the cut ( analytic proofs ), these are usually longer than using the cut rule. In his article "Do not Eliminate Cut! " showed the mathematician and logician George Boolos that there is a formula that can be derived with the aid of the cut in about one page, while it would take longer than the lifetime of the universe to write a derivation that does not cut.
By applying the cut rule is modallogische statements can be justified if the corresponding logical statements are true. The in modal logic always sheltering knowledge can be cut away in the case. So the Gentzensche main clause is also used for grounding of modal logic, because you can define modallogische truth.
The so-called stringent law is similar to the set of Herbrand. It is about the role of quantifiers in a proof.