Löbsova věta - Löbs theorem - Wikipedia

v matematická logika, Löbova věta uvádí, že v Peano aritmetika (PA) (nebo jakýkoli formální systém včetně PA) pro jakýkoli vzorec P, pokud je v PA prokazatelné, že "pokud P je tedy prokazatelné v PA P je tedy pravda “ P je prokazatelné v PA. Více formálně, pokud Prov (P) znamená, že vzorec P je tedy prokazatelné

{ displaystyle mathrm {if} PA vdash ({ rm {Prov}} (P) rightarrow P) mathrm {, pak} PA vdash P,}

nebo

{ displaystyle { dfrac {PA vdash { rm {Prov}} (P) rightarrow P} {PA vdash P}}.}

Okamžitý důsledek ( kontrapozitivní ) Löbovy věty je, že pokud P není prokazatelné v PA, pak „pokud P je tedy prokazatelné v PA P je pravda „není v PA prokazatelné. Například„ Pokud ${ displaystyle 1 + 1 = 3}$ je tedy prokazatelné v PA ${ displaystyle 1 + 1 = 3}$ „není prokazatelné v PA.^{[poznámka 1]}

Löbova věta je pojmenována pro Martin Hugo Löb, který jej formuloval v roce 1955.

Löbova věta v logice prokazatelnosti

Logika prokazatelnosti abstrahuje od podrobností použitých kódování v Gödelovy věty o neúplnosti vyjádřením prokazatelnosti ${ displaystyle phi}$ v daném systému v jazyce modální logika pomocí modality ${ displaystyle Box phi}$ .

Pak můžeme formovat Löbovu větu pomocí axiomu

{ displaystyle Box ( Box P rightarrow P) rightarrow Box P,}

známý jako axiom GL, pro Gödel – Löb. To je někdy formalizováno pomocí odvozovacího pravidla, které vyvozuje

{ displaystyle P}

z

{ displaystyle Box P rightarrow P.}

Logika prokazatelnosti GL, která je výsledkem převzetí modální logika K4 (nebo K., protože schéma axiomu 4, ${ displaystyle Box A rightarrow Box Box A}$ , poté se stane nadbytečným) a přidání výše uvedeného axiomu GL je nejintenzivněji zkoumaným systémem v logice prokazatelnosti.

Modální důkaz Löbovy věty

Löbovu větu lze dokázat v rámci modální logiky pouze za použití několika základních pravidel o operátoru prokazatelnosti (systém K4) plus existence modálních pevných bodů.

Modální vzorce

U vzorců předpokládáme následující gramatiku:

Li ${ displaystyle X}$ je výroková proměnná, pak ${ displaystyle X}$ je vzorec.
Li ${ displaystyle K}$ je tedy výroková konstanta ${ displaystyle K}$ je vzorec.
Li ${ displaystyle A}$ je tedy vzorec ${ displaystyle Box A}$ je vzorec.
Li ${ displaystyle A}$ a ${ displaystyle B}$ jsou vzorce, tak jsou ${ displaystyle neg A}$ , ${ displaystyle A rightarrow B}$ , ${ displaystyle A klín B}$ , ${ displaystyle A vee B}$ , a ${ displaystyle A leftrightarrow B}$

Modální věta je modální vzorec, který neobsahuje žádné výrokové proměnné. Používáme ${ displaystyle vdash A}$ znamenat ${ displaystyle A}$ je věta.

Modální pevné body

Li ${ displaystyle F (X)}$ je modální vzorec s pouze jednou výrokovou proměnnou ${ displaystyle X}$ , pak modální pevný bod ${ displaystyle F (X)}$ je věta ${ displaystyle Psi}$ takhle

{ displaystyle vdash Psi leftrightarrow F ( Box Psi)}

Budeme předpokládat existenci takových pevných bodů pro každý modální vzorec s jednou volnou proměnnou. To samozřejmě není samozřejmé předpokládat, ale pokud interpretujeme ${ displaystyle Box}$ jako prokazatelnost v Peano Arithmetic, pak existence modálních pevných bodů vyplývá z diagonální lemma.

Modální pravidla odvození

Kromě existence modálních pevných bodů předpokládáme následující pravidla odvození pro operátora prokazatelnosti ${ displaystyle Box}$ , známý jako Hilbert – Bernays podmínky prokazatelnosti:

(nutnost) Z ${ displaystyle vdash A}$ uzavřít ${ displaystyle vdash rámeček A}$ : Neformálně to říká, že pokud A je věta, pak je to dokázatelné.
(vnitřní nutnost) ${ displaystyle vdash box A rightarrow box box A}$ : Pokud je A prokazatelné, pak je prokazatelné, že je prokazatelné.
(krabicová distribuce) ${ displaystyle vdash Box (A rightarrow B) rightarrow ( Box A rightarrow Box B)}$ : Toto pravidlo vám umožňuje dělat modus ponens uvnitř operátora prokazatelnosti. Pokud je prokazatelné, že A znamená B, a A je prokazatelné, pak B je prokazatelné.

Důkaz Löbovy věty

Předpokládejme, že existuje modální věta ${ displaystyle P}$ takhle ${ displaystyle vdash box P rightarrow P}$ .
Zhruba řečeno, je to věta, že pokud ${ displaystyle P}$ je prokazatelné, pak je to ve skutečnosti pravda.
Toto je tvrzení zdravost.
Z existence modálních pevných bodů pro každý vzorec (zejména vzorec ${ displaystyle X rightarrow P}$ ) z toho vyplývá, že existuje věta ${ displaystyle Psi}$ takhle ${ displaystyle vdash Psi leftrightarrow ( Box Psi rightarrow P)}$ .
Z 2 to vyplývá ${ displaystyle vdash Psi rightarrow ( Box Psi rightarrow P)}$ .
Z pravidla nezbytnosti to vyplývá ${ displaystyle vdash Box ( Psi rightarrow ( Box Psi rightarrow P))}$ .
Ze 4 a pravidla distribuce boxů to vyplývá ${ displaystyle vdash Box Psi rightarrow Box ( Box Psi rightarrow P)}$ .
Použití pravidla distribuce pole pomocí ${ displaystyle A = Box Psi}$ a ${ displaystyle B = P}$ nám dává ${ displaystyle vdash Box ( Box Psi rightarrow P) rightarrow ( Box Box Psi rightarrow Box P)}$ .
Z 5 a 6 z toho vyplývá ${ displaystyle vdash Box Psi rightarrow ( Box Box Psi rightarrow Box P)}$ .
Z pravidla vnitřní nezbytnosti to vyplývá ${ displaystyle vdash Box Psi rightarrow Box Box Psi}$ .
Z bodů 7 a 8 z toho vyplývá ${ displaystyle vdash Box Psi rightarrow Box P}$ .
Z bodů 1 a 9 z toho vyplývá ${ displaystyle vdash Box Psi rightarrow P}$ .
Z 2 to vyplývá ${ displaystyle vdash ( Box Psi rightarrow P) rightarrow Psi}$ .
Z 10 a 11 z toho vyplývá ${ displaystyle vdash Psi}$
Z 12 a pravidla nezbytnosti to vyplývá ${ displaystyle vdash Box Psi}$ .
Z 13 a 10 z toho vyplývá ${ displaystyle vdash P}$ .

Příklady

Okamžitým důsledkem Löbovy věty je, že pokud P není prokazatelné v PA, pak „pokud P je tedy prokazatelné v PA P is true "není dokázatelné v PA. Vzhledem k tomu, že víme, že PA je konzistentní (ale PA neví, že PA je konzistentní), zde je několik jednoduchých příkladů:

"Li ${ displaystyle 1 + 1 = 3}$ je tedy prokazatelné v PA ${ displaystyle 1 + 1 = 3}$ "není prokazatelné v PA, as ${ displaystyle 1 + 1 = 3}$ není prokazatelné v PA (protože je nepravdivé).
"Li ${ displaystyle 1 + 1 = 2}$ je tedy prokazatelné v PA ${ displaystyle 1 + 1 = 2}$ „je prokazatelné v PA, stejně jako jakékoli prohlášení ve formuláři„ Pokud X, pak ${ displaystyle 1 + 1 = 2}$ ".
"Li zesílená konečná Ramseyova věta je prokazatelný v PA, pak zesílený konečný Ramseyho teorém je pravdivý "není prokazatelný v PA, protože" Posílený konečný Ramseyho teorém je pravdivý "není prokazatelný v PA (přestože je pravdivý).

v Doxastická logika, Löbova věta ukazuje, že jakýkoli systém klasifikovaný jako a reflexní "typ 4 „rozumný musí být také“skromný„: takový uvažovatel nikdy nemůže uvěřit„ moje víra v P by znamenala, že P je pravda “, aniž by nejprve věřil, že P je pravda.^[1]

Gödelova druhá věta o neúplnosti vyplývá z Löbovy věty nahrazením falešného tvrzení ${ displaystyle bot}$ pro P.

Converse: Löbova věta naznačuje existenci modálních pevných bodů

Nejenže existence modálních pevných bodů implikuje Löbovu větu, ale platí i obráceně. Když je Löbova věta uvedena jako axiom (schéma), existence pevného bodu (až do prokazatelné ekvivalence) ${ displaystyle p leftrightarrow A (p)}$ pro jakýkoli vzorec A(p) upraveno v str lze odvodit.^[2] Tak dovnitř normální modální logika, Löbův axiom je ekvivalentní konjunkci schématu axiomu 4, ${ displaystyle ( Box A rightarrow Box Box A)}$ a existence modálních pevných bodů.

Poznámky

^ Pokud PA není nekonzistentní (v takovém případě je každé prohlášení prokazatelné, včetně ${ displaystyle 1 + 1 = 3}$ ).

Citace

^ Smullyan, Raymond M., (1986) Logici, kteří o sobě uvažují, Sborník konference z roku 1986 o teoretických aspektech uvažování o znalostech, Monterey (CA), Morgan Kaufmann Publishers Inc., San Francisco (CA), str. 341-352
^ Per Lindström (červen 2006). Msgstr "Poznámka k některým konstrukcím pevných bodů v logice." Journal of Philosophical Logic. 35 (3): 225–230. doi:10.1007 / s10992-005-9013-8.

Reference

Boolos, George S. (1995). Logika prokazatelnosti. Cambridge University Press. ISBN 978-0-521-48325-4.
Löb, Martin (1955), „Řešení problému Leona Henkina“, Journal of Symbolic Logic, 20 (2): 115–118, JSTOR 2266895
Hinman, P. (2005). Základy matematické logiky. A K Peters. ISBN 978-1-56881-262-5.
Verbrugge, Rineke (L.C.) (1. ledna 2016). „Logika zabezpečení“. Stanfordská encyklopedie filozofie. Citováno 6. dubna 2016.

externí odkazy

[1] Pokud PA není nekonzistentní (v takovém případě je každé prohlášení prokazatelné, včetně ${ displaystyle 1 + 1 = 3}$ ).

[2] Smullyan, Raymond M., (1986) Logici, kteří o sobě uvažují, Sborník konference z roku 1986 o teoretických aspektech uvažování o znalostech, Monterey (CA), Morgan Kaufmann Publishers Inc., San Francisco (CA), str. 341-352

[3] Per Lindström (červen 2006). Msgstr "Poznámka k některým konstrukcím pevných bodů v logice." Journal of Philosophical Logic. 35 (3): 225–230. doi:10.1007 / s10992-005-9013-8.

[poznámka 1]

[1]

[2]