1733:
2298:
1310:
1843:
2381:
2221:
1663:
1611:
3052:
Not only does the existence of modal fixed points imply Löb's theorem, but the converse is valid, too. When Löb's theorem is given as an axiom (schema), the existence of a fixed point (up to provable equivalence)
124:
1510:
2064:
1556:
436:
1883:
1085:
1243:
1920:
3147:
2995:
is provable in PA, then the strengthened finite Ramsey theorem is true" is not provable in PA, as "The strengthened finite Ramsey theorem is true" is not provable in PA (despite being true).
2018:
558:
2620:
1960:
477:
2712:
2665:
2567:
2471:
2426:
161:
3086:
1445:
889:
2746:
2502:
2117:
811:
1200:
2089:
1762:
1670:
1377:
1348:
319:
1090:
We will assume the existence of such fixed points for every modal formula with one free variable. This is of course not an obvious thing to assume, but if we interpret
837:
2142:
1174:
915:
504:
863:
785:
719:
3195:
3038:
2986:
2954:
2922:
2887:
2855:
2823:
1465:
1140:
1108:
1041:
380:
360:
340:
291:
245:
213:
1021:
972:
1788:
2766:
2522:
1980:
1400:
992:
935:
762:
742:
696:
673:
653:
630:
606:
2226:
569:
3511:
1253:
1795:
1312:: This rule allows you to do modus ponens inside the provability operator. If it is provable that A implies B, and A is provable, then B is provable.
2303:
2992:
2155:
1618:
568:
Löb's theorem can be proved within modal logic using only some basic rules about the provability operator (the K4 system) plus the existence of
1563:
68:
1471:
2789:
is true" is not provable in PA. Given we know PA is consistent (but PA does not know PA is consistent), here are some simple examples:
2025:
1517:
1143:
391:
1850:
1049:
3312:
3293:
1122:
In addition to the existence of modal fixed points, we assume the following rules of inference for the provability operator
270:
1210:
3489:
3017:": such a reasoner can never believe "my belief in P would imply that P is true", without also believing that P is true.
1890:
3220:
560:, then becomes redundant) and adding the above axiom GL is the most intensely investigated system in provability logic.
3449:
3111:
1991:
528:
2572:
298:
3010:
1933:
450:
3354:
2675:
2628:
2530:
2434:
2389:
133:
3526:
3056:
3506:
1409:
868:
3521:
3285:
2720:
2476:
2096:
3434:
Proceedings of the 1986 conference on
Theoretical aspects of reasoning about knowledge, Monterey (CA)
3388:
3020:
Gödel's second incompleteness theorem follows from Löb's theorem by substituting the false statement
1728:{\displaystyle \vdash \Box (\Box \Psi \rightarrow P)\rightarrow (\Box \Box \Psi \rightarrow \Box P)}
894:
A modal sentence is a formula in this syntax that contains no propositional variables. The notation
790:
1179:
3005:
2071:
1738:
1353:
1324:
301:
816:
609:
441:
known as axiom GL, for Gödel–Löb. This is sometimes formalized by means of the inference rule:
2124:
1350:, so for ease of understanding, the proof below is subdivided to leave the parts depending on
1156:
1110:
as provability in Peano
Arithmetic, then the existence of modal fixed points follows from the
897:
486:
3516:
842:
581:
767:
701:
3168:
3023:
2959:
2927:
2895:
2860:
2828:
2796:
1450:
1125:
1093:
1026:
365:
345:
325:
276:
218:
186:
997:
948:
8:
1767:
3484:
3441:
3413:
3405:
3371:
3322:
Japaridze, Giorgi; De Jongh, Dick (1998). "Chapter VII - The Logic of
Provability". In
3278:
3101:
2751:
2507:
1965:
1385:
977:
920:
747:
727:
681:
658:
638:
615:
591:
255:
20:
3340:
3047:
3445:
3429:
3417:
3308:
3289:
2293:{\displaystyle {\mathit {PA}}\vdash {\neg P\rightarrow \neg \mathrm {Prov} _{PA}(P)}}
266:
3375:
3437:
3425:
3397:
3363:
3335:
28:
3349:
1305:{\displaystyle \vdash \Box (A\rightarrow B)\rightarrow (\Box A\rightarrow \Box B)}
342:
is a logical formula, another formula can be formed by placing a box in front of
3165:
Unless PA is inconsistent (in which case every statement is provable, including
1838:{\displaystyle \vdash \Box \Psi \rightarrow (\Box \Box \Psi \rightarrow \Box P)}
3000:
1111:
168:
3367:
2376:{\displaystyle \{{\mathit {PA}},\neg P\}\vdash {\neg \mathrm {Prov} _{PA}(P)}}
3500:
3273:
32:
3383:
3352:(June 2006). "Note on Some Fixed Point Constructions in Provability Logic".
251:
2216:{\displaystyle {\mathit {PA}}\vdash {\mathrm {Prov} _{PA}(P)\rightarrow P}}
1658:{\displaystyle \vdash \Box \Psi \rightarrow \Box (\Box \Psi \rightarrow P)}
3323:
511:
294:
3436:. San Francisco (CA): Morgan Kaufmann Publishers Inc. pp. 341–352.
1606:{\displaystyle \vdash \Box (\Psi \rightarrow (\Box \Psi \rightarrow P))}
3470:
3409:
3330:. Studies in Logic and the Foundations of Mathematics. Vol. 137.
119:{\displaystyle {\mathit {PA}}\vdash {\mathrm {Prov} (P)\rightarrow P}}
3466:
1505:{\displaystyle \vdash \Psi \leftrightarrow (\Box \Psi \rightarrow P)}
3401:
1202:: Informally, this says that if A is a theorem, then it is provable.
3331:
3104:, Löb's axiom is equivalent to the conjunction of the axiom schema
3048:
Converse: Löb's theorem implies the existence of modal fixed points
2956:" is provable in PA, as is any statement of the form "If X, then
2059:{\displaystyle \vdash (\Box \Psi \rightarrow P)\rightarrow \Psi }
1551:{\displaystyle \vdash \Psi \rightarrow (\Box \Psi \rightarrow P)}
1925:
Now comes the part of the proof where the hypothesis is used.
431:{\displaystyle \Box (\Box P\rightarrow P)\rightarrow \Box P,}
1878:{\displaystyle \vdash \Box \Psi \rightarrow \Box \Box \Psi }
1245:: If A is provable, then it is provable that it is provable.
1982:
is provable, then it is, in fact true. This is a claim of
2687:
2640:
2542:
2446:
2401:
2315:
2235:
2164:
2148:
More informally, we can sketch out the proof as follows.
1406:
Apply the existence of modal fixed points to the formula
1080:{\displaystyle \vdash \Psi \leftrightarrow F(\Box \Psi )}
142:
77:
974:
is a modal formula with only one propositional variable
2672:
By Godel's second incompleteness theorem, this implies
3003:, Löb's theorem shows that any system classified as a
1321:
Much of the proof does not make use of the assumption
510:
The provability logic GL that results from taking the
3171:
3114:
3059:
3026:
2962:
2930:
2898:
2863:
2831:
2799:
2754:
2723:
2678:
2631:
2575:
2533:
2510:
2479:
2437:
2392:
2306:
2229:
2158:
2127:
2099:
2074:
2028:
1994:
1968:
1936:
1893:
1853:
1798:
1770:
1741:
1673:
1621:
1566:
1520:
1474:
1453:
1412:
1388:
1356:
1327:
1256:
1213:
1182:
1159:
1128:
1096:
1052:
1029:
1000:
980:
951:
923:
900:
871:
845:
819:
793:
770:
750:
730:
704:
684:
661:
641:
618:
594:
531:
489:
453:
394:
368:
348:
328:
304:
279:
269:
abstracts away from the details of encodings used in
261:
221:
189:
136:
71:
3250:
2777:
An immediate corollary of Löb's theorem is that, if
1238:{\displaystyle \vdash \Box A\rightarrow \Box \Box A}
3238:
1915:{\displaystyle \vdash \Box \Psi \rightarrow \Box P}
3277:
3189:
3141:
3080:
3032:
2980:
2948:
2916:
2881:
2849:
2817:
2760:
2740:
2706:
2659:
2614:
2561:
2516:
2496:
2465:
2420:
2375:
2292:
2215:
2136:
2111:
2083:
2058:
2012:
1974:
1954:
1914:
1877:
1837:
1782:
1756:
1727:
1657:
1605:
1550:
1504:
1459:
1439:
1394:
1371:
1342:
1304:
1237:
1194:
1168:
1134:
1102:
1079:
1035:
1015:
986:
966:
929:
909:
883:
857:
831:
805:
779:
756:
736:
713:
690:
667:
647:
624:
600:
552:
498:
471:
430:
374:
354:
334:
313:
285:
239:
207:
155:
118:
59:is provable, we may express this more formally as
3321:
385:Then we can formalize Löb's theorem by the axiom
183:is true" is not provable in PA. For example, "If
3498:
3386:(1955). "Solution of a Problem of Leon Henkin".
3142:{\displaystyle (\Box A\rightarrow \Box \Box A)}
1735:, by applying the box distributivity rule with
1447:. It then follows that there exists a sentence
563:
3200:
2013:{\displaystyle \vdash \Box \Psi \rightarrow P}
254:, who formulated it in 1955. It is related to
1962:. Roughly speaking, it is a theorem that if
553:{\displaystyle \Box A\rightarrow \Box \Box A}
3221:"Löb's theorem is (almost) the Y combinator"
2701:
2679:
2654:
2632:
2615:{\displaystyle \neg \mathrm {Prov} _{PA}(P)}
2556:
2534:
2460:
2438:
2415:
2393:
2329:
2307:
1885:, from 6 by the internal necessitation rule.
3149:, and the existence of modal fixed points.
1117:
3512:Theorems in the foundations of mathematics
1955:{\displaystyle \vdash \Box P\rightarrow P}
472:{\displaystyle \vdash \Box P\rightarrow P}
3487:entry by Rineke (L.C.) Verbrugge in the
3348:
3339:
3256:
2707:{\displaystyle \{{\mathit {PA}},\neg P\}}
2660:{\displaystyle \{{\mathit {PA}},\neg P\}}
2562:{\displaystyle \{{\mathit {PA}},\neg P\}}
2466:{\displaystyle \{{\mathit {PA}},\neg P\}}
2421:{\displaystyle \{{\mathit {PA}},\neg P\}}
1665:, from 3 and the box distributivity rule.
1316:
3424:
3244:
3430:"Logicians who reason about themselves"
2889:is not provable in PA (as it is false).
293:in the given system in the language of
3499:
3302:
3272:
2993:the strengthened finite Ramsey theorem
1144:Hilbert–Bernays provability conditions
156:{\displaystyle {\mathit {PA}}\vdash P}
3081:{\displaystyle p\leftrightarrow A(p)}
940:
2119:, from 12 by the necessitation rule.
3490:Stanford Encyclopedia of Philosophy
3382:
3206:
1613:, from 2 by the necessitation rule.
1440:{\displaystyle F(X)=X\rightarrow P}
39:, if it is provable in PA that "if
13:
3442:10.1016/B978-0-934613-04-0.50028-4
3305:Fundamentals of Mathematical Logic
3027:
2733:
2724:
2695:
2684:
2648:
2637:
2590:
2587:
2584:
2581:
2576:
2550:
2539:
2489:
2480:
2454:
2443:
2409:
2398:
2350:
2347:
2344:
2341:
2336:
2323:
2312:
2267:
2264:
2261:
2258:
2253:
2244:
2232:
2184:
2181:
2178:
2175:
2161:
2106:
2078:
2053:
2038:
2001:
1900:
1872:
1860:
1820:
1805:
1751:
1710:
1686:
1643:
1628:
1588:
1576:
1536:
1524:
1490:
1478:
1454:
1071:
1056:
1030:
884:{\displaystyle A\leftrightarrow B}
771:
655:is a propositional constant, then
262:Löb's theorem in provability logic
139:
96:
93:
90:
87:
74:
14:
3538:
3459:
2741:{\displaystyle \neg P\to \bot {}}
2497:{\displaystyle \neg P\to \bot {}}
2112:{\displaystyle \vdash \Box \Psi }
575:
273:by expressing the provability of
2781:is not provable in PA, then "if
2473:is inconsistent, then PA proves
175:is not provable in PA, then "if
362:, and is intended to mean that
271:Gödel's incompleteness theorems
171:) of Löb's theorem is that, if
35:including PA), for any formula
3355:Journal of Philosophical Logic
3212:
3159:
3136:
3124:
3115:
3075:
3069:
3063:
2730:
2609:
2603:
2486:
2369:
2363:
2286:
2280:
2250:
2206:
2203:
2197:
2050:
2047:
2041:
2032:
2004:
1946:
1903:
1863:
1832:
1823:
1811:
1808:
1722:
1713:
1701:
1698:
1695:
1689:
1680:
1652:
1646:
1637:
1631:
1600:
1597:
1591:
1582:
1579:
1573:
1545:
1539:
1530:
1527:
1499:
1493:
1484:
1481:
1431:
1422:
1416:
1363:
1334:
1299:
1290:
1281:
1278:
1275:
1269:
1263:
1223:
1074:
1065:
1059:
1010:
1004:
994:, then a modal fixed point of
961:
955:
875:
806:{\displaystyle A\rightarrow B}
797:
538:
463:
416:
413:
407:
398:
109:
106:
100:
1:
3341:10.1016/S0049-237X(98)80022-0
3266:
1195:{\displaystyle \vdash \Box A}
580:We will assume the following
2857:" is not provable in PA, as
2223:by assumption, we also have
2084:{\displaystyle \vdash \Psi }
1757:{\displaystyle A=\Box \Psi }
564:Modal proof of Löb's theorem
167:An immediate corollary (the
7:
2772:
1372:{\displaystyle \Box P\to P}
1343:{\displaystyle \Box P\to P}
297:, by means of the modality
250:Löb's theorem is named for
51:is provable in PA. If Prov(
10:
3543:
3286:Cambridge University Press
764:are formulas, then so are
314:{\displaystyle \Box \phi }
3389:Journal of Symbolic Logic
3368:10.1007/s10992-005-9013-8
3218:
3013:" reasoner must also be "
832:{\displaystyle A\wedge B}
521:, since the axiom schema
247:" is not provable in PA.
55:) means that the formula
3328:Handbook of Proof Theory
3280:The Logic of Provability
3152:
3100:can be derived. Thus in
2924:is provable in PA, then
2825:is provable in PA, then
2785:is provable in PA, then
2137:{\displaystyle \vdash P}
1206:(internal necessitation)
1169:{\displaystyle \vdash A}
1118:Modal rules of inference
910:{\displaystyle \vdash A}
499:{\displaystyle \vdash P}
215:is provable in PA, then
179:is provable in PA, then
2748:, which is the same as
2504:, which is the same as
2428:can reason as follows:
2386:Now, the hybrid theory
1402:be any modal sentence.
858:{\displaystyle A\vee B}
43:is provable in PA then
3191:
3143:
3082:
3034:
2982:
2950:
2918:
2883:
2851:
2819:
2762:
2742:
2708:
2661:
2616:
2563:
2518:
2498:
2467:
2422:
2377:
2294:
2217:
2138:
2113:
2085:
2060:
2014:
1976:
1956:
1916:
1879:
1839:
1784:
1758:
1729:
1659:
1607:
1552:
1506:
1461:
1441:
1396:
1373:
1344:
1317:Proof of Löb's theorem
1306:
1239:
1196:
1170:
1136:
1104:
1081:
1037:
1017:
988:
968:
931:
911:
885:
859:
833:
807:
781:
780:{\displaystyle \neg A}
758:
738:
715:
714:{\displaystyle \Box A}
692:
669:
649:
626:
610:propositional variable
602:
554:
500:
473:
432:
376:
356:
336:
315:
287:
241:
209:
157:
120:
3192:
3190:{\displaystyle 1+1=3}
3144:
3083:
3035:
3033:{\displaystyle \bot }
2983:
2981:{\displaystyle 1+1=2}
2951:
2949:{\displaystyle 1+1=2}
2919:
2917:{\displaystyle 1+1=2}
2884:
2882:{\displaystyle 1+1=3}
2852:
2850:{\displaystyle 1+1=3}
2820:
2818:{\displaystyle 1+1=3}
2763:
2743:
2709:
2662:
2617:
2564:
2519:
2499:
2468:
2423:
2378:
2295:
2218:
2139:
2114:
2086:
2061:
2015:
1977:
1957:
1917:
1880:
1840:
1785:
1759:
1730:
1660:
1608:
1553:
1507:
1462:
1460:{\displaystyle \Psi }
1442:
1397:
1374:
1345:
1307:
1240:
1197:
1171:
1137:
1135:{\displaystyle \Box }
1105:
1103:{\displaystyle \Box }
1082:
1038:
1036:{\displaystyle \Psi }
1018:
989:
969:
932:
917:is used to mean that
912:
886:
860:
834:
808:
782:
759:
739:
716:
693:
670:
650:
627:
603:
555:
501:
474:
433:
377:
375:{\displaystyle \phi }
357:
355:{\displaystyle \phi }
337:
335:{\displaystyle \phi }
316:
288:
286:{\displaystyle \phi }
242:
240:{\displaystyle 1+1=3}
210:
208:{\displaystyle 1+1=3}
158:
121:
3426:Smullyan, Raymond M.
3334:. pp. 475–546.
3219:Neel, Krishnaswami.
3169:
3112:
3057:
3024:
2960:
2928:
2896:
2861:
2829:
2797:
2752:
2721:
2676:
2629:
2573:
2531:
2508:
2477:
2435:
2390:
2304:
2227:
2156:
2125:
2097:
2072:
2026:
1992:
1966:
1934:
1891:
1851:
1796:
1768:
1739:
1671:
1619:
1564:
1518:
1472:
1451:
1410:
1386:
1354:
1325:
1254:
1249:(box distributivity)
1211:
1180:
1157:
1126:
1094:
1050:
1027:
1016:{\displaystyle F(X)}
998:
978:
967:{\displaystyle F(X)}
949:
921:
898:
869:
843:
817:
791:
768:
748:
728:
702:
682:
659:
639:
616:
592:
529:
487:
451:
392:
366:
346:
326:
302:
277:
219:
187:
134:
69:
3527:Mathematical axioms
3485:"Provability Logic"
3303:Hinman, P. (2005).
2569:already knows that
1783:{\displaystyle B=P}
698:is a formula, then
3507:Mathematical logic
3187:
3139:
3102:normal modal logic
3078:
3030:
2978:
2946:
2914:
2879:
2847:
2815:
2758:
2738:
2704:
2657:
2622:, a contradiction.
2612:
2559:
2514:
2494:
2463:
2418:
2373:
2290:
2213:
2134:
2109:
2081:
2056:
2010:
1972:
1952:
1912:
1875:
1835:
1780:
1754:
1725:
1655:
1603:
1548:
1502:
1457:
1437:
1392:
1369:
1340:
1302:
1235:
1192:
1166:
1132:
1100:
1077:
1033:
1013:
984:
964:
941:Modal fixed points
927:
907:
881:
855:
829:
803:
777:
754:
734:
711:
688:
665:
645:
622:
598:
570:modal fixed points
550:
496:
469:
428:
372:
352:
332:
311:
283:
237:
205:
153:
116:
21:mathematical logic
3522:Provability logic
3469:. 22 March 2013.
3314:978-1-56881-262-5
3295:978-0-521-48325-4
3274:Boolos, George S.
2761:{\displaystyle P}
2517:{\displaystyle P}
2144:, from 13 and 10.
2091:, from 10 and 11.
1975:{\displaystyle P}
1395:{\displaystyle P}
1379:until the end.
987:{\displaystyle X}
930:{\displaystyle A}
757:{\displaystyle B}
737:{\displaystyle A}
691:{\displaystyle A}
668:{\displaystyle K}
648:{\displaystyle K}
625:{\displaystyle X}
601:{\displaystyle X}
267:Provability logic
16:Provability logic
3534:
3481:
3479:
3477:
3455:
3421:
3379:
3345:
3343:
3318:
3299:
3283:
3260:
3254:
3248:
3242:
3236:
3235:
3233:
3231:
3216:
3210:
3204:
3198:
3196:
3194:
3193:
3188:
3163:
3148:
3146:
3145:
3140:
3088:for any formula
3087:
3085:
3084:
3079:
3039:
3037:
3036:
3031:
2987:
2985:
2984:
2979:
2955:
2953:
2952:
2947:
2923:
2921:
2920:
2915:
2888:
2886:
2885:
2880:
2856:
2854:
2853:
2848:
2824:
2822:
2821:
2816:
2767:
2765:
2764:
2759:
2747:
2745:
2744:
2739:
2737:
2717:Thus, PA proves
2714:is inconsistent.
2713:
2711:
2710:
2705:
2691:
2690:
2666:
2664:
2663:
2658:
2644:
2643:
2621:
2619:
2618:
2613:
2602:
2601:
2593:
2568:
2566:
2565:
2560:
2546:
2545:
2523:
2521:
2520:
2515:
2503:
2501:
2500:
2495:
2493:
2472:
2470:
2469:
2464:
2450:
2449:
2427:
2425:
2424:
2419:
2405:
2404:
2382:
2380:
2379:
2374:
2372:
2362:
2361:
2353:
2319:
2318:
2300:, which implies
2299:
2297:
2296:
2291:
2289:
2279:
2278:
2270:
2239:
2238:
2222:
2220:
2219:
2214:
2212:
2196:
2195:
2187:
2168:
2167:
2143:
2141:
2140:
2135:
2118:
2116:
2115:
2110:
2090:
2088:
2087:
2082:
2065:
2063:
2062:
2057:
2019:
2017:
2016:
2011:
1981:
1979:
1978:
1973:
1961:
1959:
1958:
1953:
1921:
1919:
1918:
1913:
1884:
1882:
1881:
1876:
1844:
1842:
1841:
1836:
1789:
1787:
1786:
1781:
1763:
1761:
1760:
1755:
1734:
1732:
1731:
1726:
1664:
1662:
1661:
1656:
1612:
1610:
1609:
1604:
1557:
1555:
1554:
1549:
1511:
1509:
1508:
1503:
1466:
1464:
1463:
1458:
1446:
1444:
1443:
1438:
1401:
1399:
1398:
1393:
1378:
1376:
1375:
1370:
1349:
1347:
1346:
1341:
1311:
1309:
1308:
1303:
1244:
1242:
1241:
1236:
1201:
1199:
1198:
1193:
1175:
1173:
1172:
1167:
1141:
1139:
1138:
1133:
1109:
1107:
1106:
1101:
1086:
1084:
1083:
1078:
1042:
1040:
1039:
1034:
1022:
1020:
1019:
1014:
993:
991:
990:
985:
973:
971:
970:
965:
936:
934:
933:
928:
916:
914:
913:
908:
890:
888:
887:
882:
864:
862:
861:
856:
838:
836:
835:
830:
812:
810:
809:
804:
786:
784:
783:
778:
763:
761:
760:
755:
743:
741:
740:
735:
720:
718:
717:
712:
697:
695:
694:
689:
674:
672:
671:
666:
654:
652:
651:
646:
631:
629:
628:
623:
607:
605:
604:
599:
559:
557:
556:
551:
505:
503:
502:
497:
478:
476:
475:
470:
437:
435:
434:
429:
381:
379:
378:
373:
361:
359:
358:
353:
341:
339:
338:
333:
322:. That is, when
321:
320:
318:
317:
312:
292:
290:
289:
284:
246:
244:
243:
238:
214:
212:
211:
206:
162:
160:
159:
154:
146:
145:
125:
123:
122:
117:
115:
99:
81:
80:
29:Peano arithmetic
3542:
3541:
3537:
3536:
3535:
3533:
3532:
3531:
3497:
3496:
3475:
3473:
3467:"Löb's theorem"
3465:
3462:
3452:
3402:10.2307/2266895
3324:Buss, Samuel R.
3315:
3296:
3269:
3264:
3263:
3255:
3251:
3243:
3239:
3229:
3227:
3225:Semantic Domain
3217:
3213:
3205:
3201:
3170:
3167:
3166:
3164:
3160:
3155:
3113:
3110:
3109:
3058:
3055:
3054:
3050:
3025:
3022:
3021:
2961:
2958:
2957:
2929:
2926:
2925:
2897:
2894:
2893:
2862:
2859:
2858:
2830:
2827:
2826:
2798:
2795:
2794:
2775:
2753:
2750:
2749:
2736:
2722:
2719:
2718:
2683:
2682:
2677:
2674:
2673:
2636:
2635:
2630:
2627:
2626:
2594:
2580:
2579:
2574:
2571:
2570:
2538:
2537:
2532:
2529:
2528:
2509:
2506:
2505:
2492:
2478:
2475:
2474:
2442:
2441:
2436:
2433:
2432:
2397:
2396:
2391:
2388:
2387:
2354:
2340:
2339:
2335:
2311:
2310:
2305:
2302:
2301:
2271:
2257:
2256:
2243:
2231:
2230:
2228:
2225:
2224:
2188:
2174:
2173:
2172:
2160:
2159:
2157:
2154:
2153:
2126:
2123:
2122:
2098:
2095:
2094:
2073:
2070:
2069:
2027:
2024:
2023:
2020:, from 8 and 9.
1993:
1990:
1989:
1967:
1964:
1963:
1935:
1932:
1931:
1927:
1926:
1924:
1923:
1922:, from 6 and 7.
1892:
1889:
1888:
1852:
1849:
1848:
1845:, from 4 and 5.
1797:
1794:
1793:
1769:
1766:
1765:
1740:
1737:
1736:
1672:
1669:
1668:
1620:
1617:
1616:
1565:
1562:
1561:
1519:
1516:
1515:
1473:
1470:
1469:
1468:
1452:
1449:
1448:
1411:
1408:
1407:
1387:
1384:
1383:
1355:
1352:
1351:
1326:
1323:
1322:
1319:
1255:
1252:
1251:
1212:
1209:
1208:
1181:
1178:
1177:
1158:
1155:
1154:
1151:(necessitation)
1127:
1124:
1123:
1120:
1095:
1092:
1091:
1051:
1048:
1047:
1028:
1025:
1024:
999:
996:
995:
979:
976:
975:
950:
947:
946:
943:
922:
919:
918:
899:
896:
895:
870:
867:
866:
844:
841:
840:
818:
815:
814:
792:
789:
788:
769:
766:
765:
749:
746:
745:
729:
726:
725:
703:
700:
699:
683:
680:
679:
660:
657:
656:
640:
637:
636:
617:
614:
613:
593:
590:
589:
578:
566:
530:
527:
526:
488:
485:
484:
452:
449:
448:
393:
390:
389:
367:
364:
363:
347:
344:
343:
327:
324:
323:
303:
300:
299:
278:
275:
274:
264:
256:Curry's paradox
252:Martin Hugo Löb
220:
217:
216:
188:
185:
184:
138:
137:
135:
132:
131:
86:
85:
73:
72:
70:
67:
66:
47:is true", then
27:states that in
17:
12:
11:
5:
3540:
3530:
3529:
3524:
3519:
3514:
3509:
3495:
3494:
3482:
3461:
3460:External links
3458:
3457:
3456:
3450:
3422:
3396:(2): 115–118.
3380:
3362:(3): 225–230.
3350:Lindström, Per
3346:
3319:
3313:
3307:. A K Peters.
3300:
3294:
3268:
3265:
3262:
3261:
3257:Lindström 2006
3249:
3237:
3211:
3199:
3186:
3183:
3180:
3177:
3174:
3157:
3156:
3154:
3151:
3138:
3135:
3132:
3129:
3126:
3123:
3120:
3117:
3098:modalized in p
3077:
3074:
3071:
3068:
3065:
3062:
3049:
3046:
3029:
3001:Doxastic logic
2997:
2996:
2989:
2977:
2974:
2971:
2968:
2965:
2945:
2942:
2939:
2936:
2933:
2913:
2910:
2907:
2904:
2901:
2890:
2878:
2875:
2872:
2869:
2866:
2846:
2843:
2840:
2837:
2834:
2814:
2811:
2808:
2805:
2802:
2774:
2771:
2770:
2769:
2757:
2735:
2732:
2729:
2726:
2715:
2703:
2700:
2697:
2694:
2689:
2686:
2681:
2670:
2669:
2668:
2667:is consistent.
2656:
2653:
2650:
2647:
2642:
2639:
2634:
2623:
2611:
2608:
2605:
2600:
2597:
2592:
2589:
2586:
2583:
2578:
2558:
2555:
2552:
2549:
2544:
2541:
2536:
2525:
2513:
2491:
2488:
2485:
2482:
2462:
2459:
2456:
2453:
2448:
2445:
2440:
2417:
2414:
2411:
2408:
2403:
2400:
2395:
2384:
2371:
2368:
2365:
2360:
2357:
2352:
2349:
2346:
2343:
2338:
2334:
2331:
2328:
2325:
2322:
2317:
2314:
2309:
2288:
2285:
2282:
2277:
2274:
2269:
2266:
2263:
2260:
2255:
2252:
2249:
2246:
2242:
2237:
2234:
2211:
2208:
2205:
2202:
2199:
2194:
2191:
2186:
2183:
2180:
2177:
2171:
2166:
2163:
2146:
2145:
2133:
2130:
2120:
2108:
2105:
2102:
2092:
2080:
2077:
2067:
2055:
2052:
2049:
2046:
2043:
2040:
2037:
2034:
2031:
2021:
2009:
2006:
2003:
2000:
1997:
1987:
1971:
1951:
1948:
1945:
1942:
1939:
1928:
1911:
1908:
1905:
1902:
1899:
1896:
1886:
1874:
1871:
1868:
1865:
1862:
1859:
1856:
1846:
1834:
1831:
1828:
1825:
1822:
1819:
1816:
1813:
1810:
1807:
1804:
1801:
1791:
1779:
1776:
1773:
1753:
1750:
1747:
1744:
1724:
1721:
1718:
1715:
1712:
1709:
1706:
1703:
1700:
1697:
1694:
1691:
1688:
1685:
1682:
1679:
1676:
1666:
1654:
1651:
1648:
1645:
1642:
1639:
1636:
1633:
1630:
1627:
1624:
1614:
1602:
1599:
1596:
1593:
1590:
1587:
1584:
1581:
1578:
1575:
1572:
1569:
1559:
1547:
1544:
1541:
1538:
1535:
1532:
1529:
1526:
1523:
1513:
1501:
1498:
1495:
1492:
1489:
1486:
1483:
1480:
1477:
1456:
1436:
1433:
1430:
1427:
1424:
1421:
1418:
1415:
1391:
1368:
1365:
1362:
1359:
1339:
1336:
1333:
1330:
1318:
1315:
1314:
1313:
1301:
1298:
1295:
1292:
1289:
1286:
1283:
1280:
1277:
1274:
1271:
1268:
1265:
1262:
1259:
1246:
1234:
1231:
1228:
1225:
1222:
1219:
1216:
1203:
1191:
1188:
1185:
1165:
1162:
1131:
1119:
1116:
1112:diagonal lemma
1099:
1088:
1087:
1076:
1073:
1070:
1067:
1064:
1061:
1058:
1055:
1032:
1023:is a sentence
1012:
1009:
1006:
1003:
983:
963:
960:
957:
954:
942:
939:
937:is a theorem.
926:
906:
903:
892:
891:
880:
877:
874:
854:
851:
848:
828:
825:
822:
802:
799:
796:
776:
773:
753:
733:
722:
710:
707:
687:
676:
664:
644:
633:
621:
597:
584:for formulas:
577:
576:Modal formulas
574:
565:
562:
549:
546:
543:
540:
537:
534:
508:
507:
495:
492:
482:
479:
468:
465:
462:
459:
456:
446:
439:
438:
427:
424:
421:
418:
415:
412:
409:
406:
403:
400:
397:
371:
351:
331:
310:
307:
282:
263:
260:
236:
233:
230:
227:
224:
204:
201:
198:
195:
192:
169:contrapositive
165:
164:
152:
149:
144:
141:
129:
126:
114:
111:
108:
105:
102:
98:
95:
92:
89:
84:
79:
76:
64:
15:
9:
6:
4:
3:
2:
3539:
3528:
3525:
3523:
3520:
3518:
3515:
3513:
3510:
3508:
3505:
3504:
3502:
3492:
3491:
3486:
3483:
3472:
3468:
3464:
3463:
3453:
3451:9780934613040
3447:
3443:
3439:
3435:
3431:
3427:
3423:
3419:
3415:
3411:
3407:
3403:
3399:
3395:
3391:
3390:
3385:
3381:
3377:
3373:
3369:
3365:
3361:
3357:
3356:
3351:
3347:
3342:
3337:
3333:
3329:
3325:
3320:
3316:
3310:
3306:
3301:
3297:
3291:
3287:
3282:
3281:
3275:
3271:
3270:
3258:
3253:
3246:
3245:Smullyan 1986
3241:
3226:
3222:
3215:
3208:
3203:
3184:
3181:
3178:
3175:
3172:
3162:
3158:
3150:
3133:
3130:
3127:
3121:
3118:
3107:
3103:
3099:
3095:
3091:
3072:
3066:
3060:
3045:
3043:
3018:
3016:
3012:
3008:
3007:
3002:
2994:
2990:
2975:
2972:
2969:
2966:
2963:
2943:
2940:
2937:
2934:
2931:
2911:
2908:
2905:
2902:
2899:
2891:
2876:
2873:
2870:
2867:
2864:
2844:
2841:
2838:
2835:
2832:
2812:
2809:
2806:
2803:
2800:
2792:
2791:
2790:
2788:
2784:
2780:
2755:
2727:
2716:
2698:
2692:
2671:
2651:
2645:
2624:
2606:
2598:
2595:
2553:
2547:
2526:
2511:
2483:
2457:
2451:
2430:
2429:
2412:
2406:
2385:
2366:
2358:
2355:
2332:
2326:
2320:
2283:
2275:
2272:
2247:
2240:
2209:
2200:
2192:
2189:
2169:
2151:
2150:
2149:
2131:
2128:
2121:
2103:
2100:
2093:
2075:
2068:
2044:
2035:
2029:
2022:
2007:
1998:
1995:
1988:
1985:
1969:
1949:
1943:
1940:
1937:
1929:
1909:
1906:
1897:
1894:
1887:
1869:
1866:
1857:
1854:
1847:
1829:
1826:
1817:
1814:
1802:
1799:
1792:
1777:
1774:
1771:
1748:
1745:
1742:
1719:
1716:
1707:
1704:
1692:
1683:
1677:
1674:
1667:
1649:
1640:
1634:
1625:
1622:
1615:
1594:
1585:
1570:
1567:
1560:
1542:
1533:
1521:
1514:
1496:
1487:
1475:
1434:
1428:
1425:
1419:
1413:
1405:
1404:
1403:
1389:
1380:
1366:
1360:
1357:
1337:
1331:
1328:
1296:
1293:
1287:
1284:
1272:
1266:
1260:
1257:
1250:
1247:
1232:
1229:
1226:
1220:
1217:
1214:
1207:
1204:
1189:
1186:
1183:
1163:
1160:
1152:
1149:
1148:
1147:
1145:
1129:
1115:
1113:
1097:
1068:
1062:
1053:
1046:
1045:
1044:
1007:
1001:
981:
958:
952:
938:
924:
904:
901:
878:
872:
852:
849:
846:
826:
823:
820:
800:
794:
774:
751:
731:
723:
721:is a formula.
708:
705:
685:
677:
675:is a formula.
662:
642:
634:
632:is a formula.
619:
611:
595:
587:
586:
585:
583:
573:
571:
561:
547:
544:
541:
535:
532:
524:
520:
516:
513:
493:
490:
483:
480:
466:
460:
457:
454:
447:
444:
443:
442:
425:
422:
419:
410:
404:
401:
395:
388:
387:
386:
383:
382:is provable.
369:
349:
329:
308:
305:
296:
280:
272:
268:
259:
257:
253:
248:
234:
231:
228:
225:
222:
202:
199:
196:
193:
190:
182:
178:
174:
170:
150:
147:
130:
127:
112:
103:
82:
65:
62:
61:
60:
58:
54:
50:
46:
42:
38:
34:
33:formal system
31:(PA) (or any
30:
26:
25:Löb's theorem
22:
3517:Metatheorems
3488:
3474:. Retrieved
3433:
3393:
3387:
3359:
3353:
3327:
3304:
3279:
3252:
3240:
3228:. Retrieved
3224:
3214:
3202:
3161:
3105:
3097:
3093:
3089:
3051:
3041:
3019:
3014:
3004:
2998:
2786:
2782:
2778:
2776:
2147:
1983:
1930:Assume that
1381:
1320:
1248:
1205:
1150:
1121:
1089:
944:
893:
579:
567:
522:
518:
514:
509:
440:
384:
265:
249:
180:
176:
172:
166:
56:
52:
48:
44:
40:
36:
24:
18:
3476:14 December
3384:Löb, Martin
2625:Therefore,
1142:, known as
512:modal logic
295:modal logic
3501:Categories
3471:PlanetMath
3267:References
1467:such that
1043:such that
3418:250348262
3131:◻
3128:◻
3125:→
3119:◻
3064:↔
3028:⊥
3006:reflexive
2734:⊥
2731:→
2725:¬
2696:¬
2649:¬
2577:¬
2551:¬
2527:However,
2490:⊥
2487:→
2481:¬
2455:¬
2410:¬
2337:¬
2333:⊢
2324:¬
2254:¬
2251:→
2245:¬
2241:⊢
2207:→
2170:⊢
2129:⊢
2107:Ψ
2104:◻
2101:⊢
2079:Ψ
2076:⊢
2066:, from 1.
2054:Ψ
2051:→
2042:→
2039:Ψ
2036:◻
2030:⊢
2005:→
2002:Ψ
1999:◻
1996:⊢
1984:soundness
1947:→
1941:◻
1938:⊢
1907:◻
1904:→
1901:Ψ
1898:◻
1895:⊢
1873:Ψ
1870:◻
1867:◻
1864:→
1861:Ψ
1858:◻
1855:⊢
1827:◻
1824:→
1821:Ψ
1818:◻
1815:◻
1809:→
1806:Ψ
1803:◻
1800:⊢
1752:Ψ
1749:◻
1717:◻
1714:→
1711:Ψ
1708:◻
1705:◻
1699:→
1690:→
1687:Ψ
1684:◻
1678:◻
1675:⊢
1647:→
1644:Ψ
1641:◻
1635:◻
1632:→
1629:Ψ
1626:◻
1623:⊢
1592:→
1589:Ψ
1586:◻
1580:→
1577:Ψ
1571:◻
1568:⊢
1558:, from 1.
1540:→
1537:Ψ
1534:◻
1528:→
1525:Ψ
1522:⊢
1494:→
1491:Ψ
1488:◻
1482:↔
1479:Ψ
1476:⊢
1455:Ψ
1432:→
1364:→
1358:◻
1335:→
1329:◻
1294:◻
1291:→
1285:◻
1279:→
1270:→
1261:◻
1258:⊢
1230:◻
1227:◻
1224:→
1218:◻
1215:⊢
1187:◻
1184:⊢
1176:conclude
1161:⊢
1130:◻
1098:◻
1072:Ψ
1069:◻
1060:↔
1057:Ψ
1054:⊢
1031:Ψ
902:⊢
876:↔
850:∨
824:∧
798:→
772:¬
706:◻
545:◻
542:◻
539:→
533:◻
491:⊢
464:→
458:◻
455:⊢
420:◻
417:→
408:→
402:◻
396:◻
370:ϕ
350:ϕ
330:ϕ
309:ϕ
306:◻
281:ϕ
148:⊢
110:→
83:⊢
3428:(1986).
3376:11038803
3332:Elsevier
3276:(1995).
3207:Löb 1955
2773:Examples
2431:Suppose
3410:2266895
3326:(ed.).
3230:9 April
612:, then
582:grammar
3493:, 2017
3448:
3416:
3408:
3374:
3311:
3292:
3015:modest
3011:type 4
2152:Since
865:, and
3414:S2CID
3406:JSTOR
3372:S2CID
3153:Notes
1153:From
608:is a
3478:2023
3446:ISBN
3309:ISBN
3290:ISBN
3232:2024
3040:for
2991:"If
2892:"If
2793:"If
1764:and
1382:Let
744:and
517:(or
481:then
128:then
3438:doi
3398:doi
3364:doi
3336:doi
2999:In
945:If
724:If
678:If
635:If
588:If
19:In
3503::
3444:.
3432:.
3412:.
3404:.
3394:20
3392:.
3370:.
3360:35
3358:.
3288:.
3284:.
3223:.
3197:).
3108:,
3044:.
2988:".
1146::
1114:.
839:,
813:,
787:,
572:.
525:,
515:K4
445:If
258:.
63:If
23:,
3480:.
3454:.
3440::
3420:.
3400::
3378:.
3366::
3344:.
3338::
3317:.
3298:.
3259:.
3247:.
3234:.
3209:.
3185:3
3182:=
3179:1
3176:+
3173:1
3137:)
3134:A
3122:A
3116:(
3106:4
3096:)
3094:p
3092:(
3090:A
3076:)
3073:p
3070:(
3067:A
3061:p
3042:P
3009:"
2976:2
2973:=
2970:1
2967:+
2964:1
2944:2
2941:=
2938:1
2935:+
2932:1
2912:2
2909:=
2906:1
2903:+
2900:1
2877:3
2874:=
2871:1
2868:+
2865:1
2845:3
2842:=
2839:1
2836:+
2833:1
2813:3
2810:=
2807:1
2804:+
2801:1
2787:P
2783:P
2779:P
2768:.
2756:P
2728:P
2702:}
2699:P
2693:,
2688:A
2685:P
2680:{
2655:}
2652:P
2646:,
2641:A
2638:P
2633:{
2610:)
2607:P
2604:(
2599:A
2596:P
2591:v
2588:o
2585:r
2582:P
2557:}
2554:P
2548:,
2543:A
2540:P
2535:{
2524:.
2512:P
2484:P
2461:}
2458:P
2452:,
2447:A
2444:P
2439:{
2416:}
2413:P
2407:,
2402:A
2399:P
2394:{
2383:.
2370:)
2367:P
2364:(
2359:A
2356:P
2351:v
2348:o
2345:r
2342:P
2330:}
2327:P
2321:,
2316:A
2313:P
2308:{
2287:)
2284:P
2281:(
2276:A
2273:P
2268:v
2265:o
2262:r
2259:P
2248:P
2236:A
2233:P
2210:P
2204:)
2201:P
2198:(
2193:A
2190:P
2185:v
2182:o
2179:r
2176:P
2165:A
2162:P
2132:P
2048:)
2045:P
2033:(
2008:P
1986:.
1970:P
1950:P
1944:P
1910:P
1833:)
1830:P
1812:(
1790:.
1778:P
1775:=
1772:B
1746:=
1743:A
1723:)
1720:P
1702:(
1696:)
1693:P
1681:(
1653:)
1650:P
1638:(
1601:)
1598:)
1595:P
1583:(
1574:(
1546:)
1543:P
1531:(
1512:.
1500:)
1497:P
1485:(
1435:P
1429:X
1426:=
1423:)
1420:X
1417:(
1414:F
1390:P
1367:P
1361:P
1338:P
1332:P
1300:)
1297:B
1288:A
1282:(
1276:)
1273:B
1267:A
1264:(
1233:A
1221:A
1190:A
1164:A
1075:)
1066:(
1063:F
1011:)
1008:X
1005:(
1002:F
982:X
962:)
959:X
956:(
953:F
925:A
905:A
879:B
873:A
853:B
847:A
827:B
821:A
801:B
795:A
775:A
752:B
732:A
709:A
686:A
663:K
643:K
620:X
596:X
548:A
536:A
523:4
519:K
506:.
494:P
467:P
461:P
426:,
423:P
414:)
411:P
405:P
399:(
235:3
232:=
229:1
226:+
223:1
203:3
200:=
197:1
194:+
191:1
181:P
177:P
173:P
163:.
151:P
143:A
140:P
113:P
107:)
104:P
101:(
97:v
94:o
91:r
88:P
78:A
75:P
57:P
53:P
49:P
45:P
41:P
37:P
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.