Twierdzenie Löba

W logice matematycznej twierdzenie Löba stwierdza, że ​​​​w arytmetyce Peano (PA) (lub dowolnym systemie formalnym, w tym PA), dla dowolnej formuły P , jeśli można udowodnić w PA, że „jeśli P można udowodnić w PA, to P jest prawdziwe”, to P jest do udowodnienia w PA. Jeśli Prov( P ) oznacza, że ​​formuła P jest dowodliwa, możemy to wyrazić bardziej formalnie jako

${\ Displaystyle PA \, \ vdash \, {{\ rm {Prz.}} (P) \ strzałka w prawo P}}, a$

ZA

P

$\ Displaystyle PA \, \vdash \,P}$

Bezpośrednim wnioskiem (kontrapozytywem ) twierdzenia Löba jest to, że jeśli P nie jest dowodliwe w PA, to „jeśli P jest dowodliwe w PA, to P jest prawdziwe” nie jest dowodliwe w PA. $przykład$ Jeśli $udowodnić$ , to da się

Twierdzenie Löba nosi imię Martina Hugo Löba , który sformułował je w 1955 roku. Jest ono związane z paradoksem Curry'ego .

Twierdzenie Löba w logice dowodzenia

Logika dowodzenia abstrahuje od szczegółów kodowania używanych w twierdzeniach Gödla o niezupełności, wyrażając możliwość udowodnienia w danym systemie w języku logiki modalnej za pomocą modalności $Box \ fi }$$Displaystyle$ .

Następnie możemy sformalizować twierdzenie Löba za pomocą aksjomatu

${\ Displaystyle \ Box (\ Box P \ rightarrow P) \ rightarrow \ Box P,}$

znany jako aksjomat GL dla Gödel – Löb. Czasami jest to sformalizowane za pomocą reguły wnioskowania, która wnioskuje

${\ displaystyle P.}$

z

${\ Displaystyle \ Box P \ rightarrow P.}$

Logika możliwości udowodnienia GL, która wynika z przyjęcia $4$ ( lub , ponieważ aksjomatu , wtedy staje zbędny) i dodaniu powyższy aksjomat GL jest najintensywniej badanym systemem w logice dowodliwości.

Modalny dowód twierdzenia Löba

Twierdzenie Löba można udowodnić w ramach logiki modalnej, używając tylko kilku podstawowych reguł dotyczących operatora dowodzenia (system K4) oraz istnienia modalnych punktów stałych.

Formuły modalne

Przyjmiemy następującą gramatykę dla formuł:

1. Jeśli jest zmienną $zdaniową$ , $formułą$ .
2. Jeśli $jest$ stałą zdaniową, $to$ .
3. Jeśli $formułą$ , $formułą$ .
4. ZA $\ Displaystyle A}$ i ${\ displaystyle B}$ są formułami, więc nimi są ${\ Displaystyle \ neg A}$ , ${\ Displaystyle A \ rightarrow B}$ , ${\ Displaystyle A \ klin B}$ , ${\ Displaystyle A \ vee B}$ i ${\ Displaystyle A \ leftrightarrow B}$

Zdanie modalne to formuła modalna, która nie zawiera zmiennych zdaniowych. Używamy ${\ displaystyle \ vdash A}$$w$ znaczeniu, że twierdzeniem.

Modalne punkty stałe

Jeśli jest $formułą$ modalną z tylko jedną zmienną zdaniową $\ Displaystyle$ to modalny punkt stały zdaniem $)}$${\ Displaystyle \ Psi}$ takie, że

${\ Displaystyle \ vdash \ psi \ strzałka w lewo F (\ pudełko \ psi)}$

Założymy istnienie takich punktów stałych dla każdej formuły modalnej z jedną zmienną wolną. Oczywiście nie jest to oczywiste do założenia, ale jeśli zinterpretujemy $arytmetyce$ Peano, to istnienie modalnych punktów stałych wynika z lematu o przekątnej .

Modalne reguły wnioskowania

Oprócz istnienia modalnych punktów stałych, zakładamy następujące reguły wnioskowania dla operatora możliwości udowodnienia , znanego jako warunki możliwości udowodnienia Hilberta – Bernaysa : ${\ displaystyle \ Box}$

1. $} : Nieformalnie mówi$ konieczność) Z wniosku ${\ displaystyle \ vdash A$ , że jeśli A jest twierdzeniem, to można to udowodnić
2. (wewnętrzna konieczność) ${\ Displaystyle \ vdash \ Box A \ rightarrow \ Box \ Box A}$ : Jeśli A jest do udowodnienia, to jest do udowodnienia, że ​​jest do udowodnienia.
3. (rozdzielność pudełka) ${\ Displaystyle \ vdash \ Box (A \ rightarrow B) \ rightarrow (\ Box A \ rightarrow \ Box B)}$ : Ta reguła pozwala zrobić modus ponens wewnątrz operatora udowodnienia. Jeśli można udowodnić, że A implikuje B, a A jest możliwe do udowodnienia, to B jest możliwe do udowodnienia.

Dowód twierdzenia Löba

Wiele dowodów nie wykorzystuje założenia , więc dla $P \ do$ zrozumienia poniższy dowód jest podzielony, aby pozostawić części w zależności od $\Box P\do P}$${\ Displaystyle \$ do końca.

Niech będzie $zdaniem$ modalnym.

1. 
   Z istnienia modalnych punktów stałych dla każdej formuły (w szczególności formuły $​​istnieje$${\ Displaystyle \ vdash \ Psi \ leftrightarrow (\ Box \ Psi \ rightarrow P)}$$zdanie$ takie , że .
2. ${\ Displaystyle \ vdash \ Psi \ rightarrow (\ Box \ Psi \ rightarrow P)}$ od 1.
3. ${\ Displaystyle \ vdash \ Box (\ Psi \ rightarrow (\ Box \ Psi \ rightarrow P))}$ , od 2 według zasady konieczności.
4. ${\ Displaystyle \ vdash \ Box \ Psi \ rightarrow \ Box (\ Box \ Psi \ rightarrow P)}$ , od 3 i zasady rozdzielności pudełka.
5. ${\ Displaystyle \ vdash \ Box (\ Box \ Psi \ rightarrow P) \ rightarrow (\ Box \ Box \ Psi \ rightarrow \ Box P)}$ , stosując regułę rozdzielności pudełkowej z $P$ = $=$ displaystyle
6. $_$ _
7. ${\ Displaystyle \ vdash \ Box \ Psi \ rightarrow \ Box \ Box \ Psi}$ , od 6 według wewnętrznej reguły konieczności.
8. 
   
   ${\ Displaystyle \ vdash \ Box \ Psi \ rightarrow \ Box P}.$ , od 6 i 7. Teraz przychodzi część dowodu, w której używana jest hipoteza.
   
   
9. Załóżmy, że ${\ Displaystyle \ vdash \ Box P \ rightarrow P}$ . Z grubsza mówiąc, jest to twierdzenie, że jeśli $udowodnić$ , to w rzeczywistości jest to prawda. To jest twierdzenie o solidności .
10. ${\ Displaystyle \ vdash \ Box \ Psi \ rightarrow P}$ , od 8 i 9.
11. ${\ Displaystyle \ vdash (\ Box \ Psi \ rightarrow P) \ rightarrow \ Psi}$ , od 1.
12. ${\ Displaystyle \ vdash \ psi}$ , od 10 i 11.
13. ${\ Displaystyle \ vdash \ Box \ Psi}$ , od 12 według zasady konieczności.
14. ${\ Displaystyle \ vdash P}$ , od 13 do 10.

Przykłady

Bezpośrednim następstwem twierdzenia Löba jest to, że jeśli P nie jest dowodliwe w PA, to „jeśli P jest dowodliwe w PA, to P jest prawdziwe” nie jest dowodliwe w PA. Biorąc pod uwagę, że wiemy, że PA jest spójne (ale PA nie wie, że PA jest spójne), oto kilka prostych przykładów:

• „Jeśli można udowodnić w PA, to $Displaystyle$$\$$1$ w PA, ponieważ nie da się udowodnić w PA (ponieważ jest fałszywe).
• „Jeśli ${\ Displaystyle 1 + 1 = 2}$ jest do udowodnienia w PA, to ${\ Displaystyle 1 + 1 = 2}$ „jest do udowodnienia w PA, podobnie jak każde stwierdzenie w postaci” Jeśli X, to ${\ Displaystyle 1 + 1 = 2}$ ".
• „Jeżeli wzmocnione twierdzenie Ramseya o skończonej rzeczywistości jest dowodliwe w PA, to wzmocnione twierdzenie Ramseya o skończonej rzeczywistości jest prawdziwe” nie jest dowodliwe w PA, ponieważ „Wzmocnione twierdzenie Ramseya o skończonej rzeczywistości jest prawdziwe” nie jest dowodliwe w PA (mimo że jest prawdziwe).

W logice doksastycznej twierdzenie Löba pokazuje, że każdy system sklasyfikowany jako refleksyjny rozumujący „ typu 4 ” musi być również „ skromny ”: taki rozumujący nigdy nie może uwierzyć, że „moja wiara w P oznaczałaby, że P jest prawdziwe”, nie wierząc jednocześnie, że P jest prawdziwy.

Drugie twierdzenie Gödla o niezupełności wynika z twierdzenia Löba poprzez zastąpienie P . $stwierdzeniem$ .

Odwrotnie: Twierdzenie Löba implikuje istnienie modalnych punktów stałych

Nie tylko istnienie modalnych punktów stałych implikuje twierdzenie Löba, ale obowiązuje również sytuacja odwrotna. Kiedy twierdzenie $)$ podane jako (schemat), istnienie punktu stałego (do możliwej do udowodnienia równoważności) A ( p w p można wyprowadzić. Zatem w normalnej logice modalnej aksjomat Löba jest równoważny koniunkcji schematu aksjomatu 4 , ${\ Displaystyle (\ Box A \ rightarrow \ Box \ Box A)}$ i istnienie modalnych punktów stałych.

Cytaty

•   Boolos, George S. (1995). Logika możliwości udowodnienia . Wydawnictwo Uniwersytetu Cambridge. ISBN 978-0-521-48325-4 .
•   Löb, Martin (1955), „Rozwiązanie problemu Leona Henkina”, Journal of Symbolic Logic , 20 (2): 115–118, doi : 10,2307/2266895 , JSTOR 2266895
•   Hinman, P. (2005). Podstawy logiki matematycznej . AK Peters. ISBN 978-1-56881-262-5 .
• Verbrugge, Rineke (LC) (1 stycznia 2016). „Logika możliwości udowodnienia” . Stanford Encyklopedia filozofii . Źródło 6 kwietnia 2016 r .

Linki zewnętrzne

• Twierdzenie Löba w PlanetMath
• Przewodnik animowany po twierdzeniu Löba autorstwa Eliezera Yudkowsky'ego