Věta o eliminaci řezu - Cut-elimination theorem

The věta o eliminaci řezu (nebo Gentzen Hauptsatz) je ústředním výsledkem určujícím význam následný počet. To bylo původně prokázáno Gerhard Gentzen ve svém dokumentu z roku 1934 „Investigations in Logical Deduction“ pro systémy LJ a LK formalizace intuitivní a klasická logika resp. Věta o eliminaci omezení uvádí, že jakýkoli úsudek, který má důkaz v následném počtu využívajícím snížit pravidlo také má a důkaz bez řezu, tj. důkaz, který nevyužívá pravidlo řezu.^[1]^[2]

Pravidlo řezu

A následující je logický výraz vztahující se k více vzorcům ve formě " ${ displaystyle A_ {1}, A_ {2}, A_ {3}, ldots vdash B_ {1}, B_ {2}, B_ {3}, ldots}$ ", kterou je třeba číst jako " ${ displaystyle A_ {1}, A_ {2}, A_ {3}, ldots}$ dokazuje ${ displaystyle B_ {1}, B_ {2}, B_ {3}, ldots}$ ", a (jak Gentzen vysvětlil) je třeba chápat jako ekvivalent funkce pravdy „Pokud ( ${ displaystyle A_ {1}}$ a ${ displaystyle A_ {2}}$ a ${ displaystyle A_ {3}}$ …) pak ( ${ displaystyle B_ {1}}$ nebo ${ displaystyle B_ {2}}$ nebo ${ displaystyle B_ {3}}$ …)."^[3] Všimněte si, že levá strana (LHS) je spojení (a) a pravá strana (RHS) je disjunkce (nebo).

LHS může mít libovolně mnoho nebo málo vzorců; když je LHS prázdný, RHS je a tautologie. V LK může mít RHS také libovolný počet vzorců - pokud žádný nemá, LHS je a rozpor vzhledem k tomu, že v LJ může mít RHS pouze jeden vzorec nebo žádný: zde vidíme, že povolení více než jednoho vzorce v RHS je za přítomnosti pravidla správné kontrakce rovnocenné s přípustností zákon vyloučeného středu. Sekvenční kalkul je však poměrně expresivní rámec a pro intuicionistickou logiku byly navrženy sekvenční kalkly, které umožňují mnoho vzorců v RHS. Z Jean-Yves Girard Díky logice LC je snadné dosáhnout poměrně přirozené formalizace klasické logiky, kde RHS obsahuje nejvýše jeden vzorec; zde je klíčová souhra logických a strukturálních pravidel.

"Vyjmout" je pravidlo v normálním prohlášení následný počet, a ekvivalent k řadě pravidel v jiných důkazní teorie, který, vzhledem k tomu

${ displaystyle Gamma vdash A, Delta}$

a

${ displaystyle Pi, A vdash Lambda}$

umožňuje odvodit

${ Displaystyle Gamma, Pi vdash Delta, Lambda}$

To znamená, že „snižuje“ výskyty vzorce ${ displaystyle A}$ z inferenčního vztahu.

Omezení eliminace

Věta o eliminaci omezení uvádí, že (pro daný systém) lze jakýkoli sled prokazatelný pomocí pravidla Cut dokázat bez použití tohoto pravidla.

Pro následné kameny, které mají v RHS pouze jeden vzorec, je uvedeno pravidlo „Vyjmout“

${ displaystyle Gamma vdash A}$

a

${ displaystyle Pi, A vdash B}$

umožňuje odvodit

${ displaystyle Gamma, Pi vdash B}$

Pokud na to myslíme ${ displaystyle B}$ jako věta, pak cut-eliminace v tomto případě jednoduše říká, že lemma ${ displaystyle A}$ slouží k prokázání této věty lze inline. Kdykoli se zmíní důkaz věty lemma ${ displaystyle A}$ , můžeme výskyty nahradit důkazem ${ displaystyle A}$ . Následkem toho je pravidlo řezu přípustný.

Důsledky věty

Pro systémy formulované v následném počtu, analytické důkazy jsou ty důkazy, které nepoužívají Cut. Obvykle takový důkaz bude samozřejmě delší a nemusí to být nutně triviální. Ve své eseji „Don't Eliminate Cut!“ George Boolos demonstroval, že existuje derivace, kterou lze dokončit na stránce pomocí řezu, ale jejíž analytický důkaz nelze dokončit během životnosti vesmíru.

Věta má mnoho, bohatých důsledků:

Systém je nekonzistentní pokud připouští důkaz absurdnosti. Pokud má systém větu o eliminaci řezu, má-li důkaz absurdnosti nebo prázdného sledu, měl by mít také důkaz absurdity (nebo prázdného sledu) bez řezů. Obvykle je velmi snadné zkontrolovat, zda takové důkazy neexistují. Jakmile se tedy ukáže, že systém má větu o eliminaci řezu, je obvykle okamžité, že je systém konzistentní.
Normálně také systém, alespoň v logice prvního řádu, má vlastnost podformulí, důležitá vlastnost v několika přístupech k důkazová sémantika.

Odstranění řezu je jedním z nejsilnějších nástrojů pro dokazování věty o interpolaci. Možnost provést důkazní prohlídku na základě rozlišení, základní pohled vedoucí k Prolog programovací jazyk, závisí na přípustnosti Cut v příslušném systému.

Pro kontrolní systémy založené na lambda kalkul vyššího řádu přes a Curry – Howardův izomorfismus, algoritmy eliminace řezu odpovídají silná normalizační vlastnost (každý zkušební termín se sníží v konečném počtu kroků na a normální forma ).

Viz také

Poznámky

^ Curry 1977, str. 208–213, poskytuje 5stránkový důkaz věty o eliminaci. Viz také strany 188, 250.
^ Kleene 2009, str. 453, poskytuje velmi krátký důkaz věty o eliminaci řezu.
^ Wilfried Buchholz, Beweistheorie (univerzitní přednášky o eliminaci škrtů, němčina, 2002-2003)

Reference

Gentzen, Gerhard (1934–1935). „Untersuchungen über das logische Schließen“. Mathematische Zeitschrift. 39: 405–431. doi:10.1007 / BF01201363.
Gentzen, Gerhard (1964). "Vyšetřování logické dedukce". American Philosophical Quarterly. 1 (4): 249–287.
Gentzen, Gerhard (1965). "Vyšetřování logické dedukce". American Philosophical Quarterly. 2 (3): 204–218.
Untersuchungen über das logische Schließen I
Untersuchungen über das logische Schließen II
Curry, Haskell Brooks (1977) [1963]. Základy matematické logiky. New York: Dover Publications Inc. ISBN 978-0-486-63462-3.CS1 maint: ref = harv (odkaz)
Kleene, Stephen Cole (2009) [1952]. Úvod do metamatematiky. Ishi Press International. ISBN 978-0-923891-57-2.CS1 maint: ref = harv (odkaz)

externí odkazy

Alex Sacharov. "Věta o eliminaci řezu". MathWorld.
Dragalin, A.G. (2001) [1994], „Sequent calculus“, Encyclopedia of Mathematics, Stiskněte EMS

[1] Curry 1977, str. 208–213, poskytuje 5stránkový důkaz věty o eliminaci. Viz také strany 188, 250.

[2] Kleene 2009, str. 453, poskytuje velmi krátký důkaz věty o eliminaci řezu.

[3] Wilfried Buchholz, Beweistheorie (univerzitní přednášky o eliminaci škrtů, němčina, 2002-2003)

[1]

[2]

[3]