Knowledge

Gödel's completeness theorem

Source 📝

3756: 27: 1443:
The compactness theorem says that if a formula φ is a logical consequence of a (possibly infinite) set of formulas Γ then it is a logical consequence of a finite subset of Γ. This is an immediate consequence of the completeness theorem, because only a finite number of axioms from Γ can be mentioned
1474:
without axiom of choice, and thus the completeness and compactness theorems for countable languages are provable in ZF. However the situation is different when the language is of arbitrary large cardinality since then, though the completeness and compactness theorems remain provably equivalent to
237:
if every logically valid formula is the conclusion of some formal deduction, and the completeness theorem for a particular deductive system is the theorem that it is complete in this sense. Thus, in a sense, there is a different completeness theorem for each deductive system. A converse to
247:
If some specific deductive system of first-order logic is sound and complete, then it is "perfect" (a formula is provable if and only if it is logically valid), thus equivalent to any other deductive system with the same quality (any proof in one system can be converted into the other).
1503:), and the set of logically-valid formulas in second-order logic is not recursively enumerable. The same is true of all higher-order logics. It is possible to produce sound deductive systems for higher-order logics, but no such system can be complete. 232:
for the language of the formula (i.e. for any assignment of values to the variables of the formula). To formally state, and then prove, the completeness theorem, it is necessary to also define a deductive system. A deductive system is called
1279:, i.e. it states that some finitistic property is true of all natural numbers; so if it is false, then some natural number is a counterexample. If this counterexample existed within the standard natural numbers, its existence would disprove 1483:. In particular, no theory extending ZF can prove either the completeness or compactness theorems over arbitrary (possibly uncountable) languages without also proving the ultrafilter lemma on a set of the same cardinality. 1392:
non-standard with a non-equivalent provability predicate and a non-equivalent way to interpret its own construction, so that this construction is non-recursive (as recursive definitions would be unambiguous).
1444:
in a formal deduction of φ, and the soundness of the deductive system then implies φ is a logical consequence of this finite set. This proof of the compactness theorem is originally due to Gödel.
877:
This comes in contrast with the direct meaning of the notion of semantic consequence, that quantifies over all structures in a particular language, which is clearly not a recursive definition.
273:, the fact that only logically valid formulae are provable in the deductive system. Together with soundness (whose verification is easy), this theorem implies that a formula is logically valid 880:
Also, it makes the concept of "provability", and thus of "theorem", a clear concept that only depends on the chosen system of axioms of the theory, and not on the choice of a proof system.
799: 256:
We first fix a deductive system of first-order predicate calculus, choosing any of the well-known equivalent systems. Gödel's original proof assumed the Hilbert-Ackermann proof system.
891:
show that there are inherent limitations to what can be proven within any given first-order theory in mathematics. The "incompleteness" in their name refers to another meaning of
267:
Thus, the deductive system is "complete" in the sense that no additional inference rules are required to prove all the logically valid formulae. A converse to completeness is
1012: 758: 709: 680: 651: 483: 428: 371: 983: 825: 511: 454: 325: 1454:. When considered over a countable language, the completeness and compactness theorems are equivalent to each other and equivalent to a weak form of choice known as 1371: 1304: 1269: 1242: 1175: 1125: 1078: 729: 847:
by an arithmetical formula whose free variables are the arguments of the symbol. (In many cases, we will need to assume, as a hypothesis of the construction, that
874:
first-order theory, by enumerating all the possible formal deductions from the axioms of the theory, and use this to produce an enumeration of their conclusions.
1414: 1344: 1324: 1215: 1195: 1145: 1098: 1035: 957: 937: 917: 608: 588: 1569: 1533: 3780: 2135: 851:
is consistent, since Peano arithmetic may not prove that fact.) However, the definition expressed by this formula is not recursive (but is, in general,
852: 1845: 1447:
Conversely, for many deductive systems, it is possible to prove the completeness theorem as an effective consequence of the compactness theorem.
2810: 2893: 2034: 1656:
Gisbert F. R. Hasenjaeger (Mar 1953). "Eine Bemerkung zu Henkin's Beweis für die Vollständigkeit des Prädikatenkalküls der Ersten Stufe".
1326:; but the incompleteness theorem showed this to be impossible, so the counterexample must not be a standard number, and thus any model of 1707: 175:
that the hard part of the proof can be presented as the Model Existence Theorem (published in 1949). Henkin's proof was simplified by
1782:
The same material as the dissertation, except with briefer proofs, more succinct explanations, and omitting the lengthy introduction.
264:
The completeness theorem says that if a formula is logically valid then there is a finite deduction (a formal proof) of the formula.
1509:
states that first-order logic is the strongest (subject to certain constraints) logic satisfying both compactness and completeness.
1536:
proceeded by reducing the problem to a special case for formulas in a certain syntactic form, and then handling this form with an
3207: 1499:, for example, does not have a completeness theorem for its standard semantics (though does have the completeness property for 1480: 3365: 2153: 1951: 1564: 888: 20: 3220: 2543: 896: 126: 1883: 1827: 3225: 3215: 2952: 2805: 2158: 516:
This more general theorem is used implicitly, for example, when a sentence is shown to be provable from the axioms of
3361: 1991: 2703: 3458: 3202: 2027: 1374: 2763: 2456: 1471: 763: 3800: 2197: 1976: 614: 3719: 3421: 3184: 3179: 3004: 2425: 2109: 1798: 229: 196: 76: 1551:
for any consistent first-order theory. James Margetson (2004) developed a computerized formal proof using the
3714: 3497: 3414: 3127: 3058: 2935: 2177: 1613: 1748: 3639: 3465: 3151: 2785: 2384: 125:
as axioms. One sometimes says this as "anything true in all models is provable". (This does not contradict
3517: 3512: 3122: 2861: 2790: 2119: 2020: 2001: 1436:
are two cornerstones of first-order logic. While neither of these theorems can be proven in a completely
110: 1842: 3446: 3036: 2430: 2398: 2089: 1996: 1934: 378: 57: 3736: 3685: 3582: 3080: 3041: 2518: 2163: 1552: 523:
Gödel's original formulation is deduced by taking the particular case of a theory without any axiom.
2192: 1506: 988: 3577: 3507: 3046: 2898: 2881: 2604: 2084: 1919: 734: 685: 656: 31: 1455: 3409: 3386: 3347: 3233: 3174: 2820: 2740: 2584: 2528: 2141: 1939: 1876: 1421: 839:. Precisely, we can systematically define a model of any consistent effective first-order theory 630: 462: 407: 350: 3699: 3426: 3404: 3371: 3264: 3110: 3095: 3068: 3019: 2903: 2838: 2663: 2629: 2624: 2498: 2329: 2306: 1971: 1437: 1272: 1042: 962: 871: 804: 490: 433: 304: 536: 219:, for example, or by hand) that a given sequence (or tree) of formulae is indeed a deduction. 3795: 3790: 3785: 3629: 3482: 3274: 2992: 2728: 2634: 2493: 2478: 2359: 2334: 1700: 520:
by considering an arbitrary group and showing that the sentence is satisfied by that group.
211:. The definition of a deduction is such that it is finite and that it is possible to verify 3602: 3564: 3441: 3245: 3085: 3009: 2987: 2815: 2773: 2672: 2639: 2503: 2291: 2202: 1966: 1961: 1913: 1517: 1349: 1282: 1247: 1220: 1153: 1103: 1056: 714: 563:
in our deductive system. The model existence theorem says that for any first-order theory
79:(only the simplest 8 are shown left). By Gödel's completeness result, it must hence have a 50: 1769: 8: 3731: 3622: 3607: 3587: 3544: 3431: 3381: 3307: 3252: 3189: 2982: 2977: 2925: 2693: 2682: 2354: 2254: 2182: 2173: 2169: 2104: 2099: 1907: 1451: 1433: 1046: 513:, and thus that syntactic and semantic consequence are equivalent for first-order logic. 286: 176: 1547:'s proof, rather than with Gödel's original proof. Henkin's proof directly constructs a 1388:
obtained by the systematic construction of the arithmetical model existence theorem, is
3760: 3529: 3492: 3477: 3470: 3453: 3257: 3239: 3105: 3031: 3014: 2967: 2780: 2689: 2523: 2508: 2468: 2420: 2405: 2393: 2349: 2324: 2094: 2043: 1869: 1773: 1681: 1673: 1638: 1630: 1590: 1496: 1399: 1329: 1309: 1200: 1180: 1130: 1083: 1020: 942: 922: 902: 593: 573: 91: 2713: 3755: 3695: 3502: 3312: 3302: 3194: 3075: 2910: 2886: 2667: 2651: 2556: 2533: 2410: 2379: 2344: 2239: 2074: 1804: 1794: 1777: 1492: 269: 240: 192: 103: 99: 80: 1685: 1642: 244:, the fact that only logically valid formulas are provable in the deductive system. 3709: 3704: 3597: 3554: 3376: 3337: 3332: 3317: 3143: 3100: 2997: 2795: 2745: 2319: 2281: 1929: 1835: 1765: 1757: 1665: 1622: 1611:
Leon Henkin (Sep 1949). "The completeness of the first-order functional calculus".
1521: 1500: 1463: 1450:
The ineffectiveness of the completeness theorem can be measured along the lines of
836: 224: 188: 26: 121:
is a model of φ, then there is a (first-order) proof of φ using the statements of
3690: 3680: 3634: 3617: 3572: 3534: 3436: 3356: 3163: 3090: 3063: 3051: 2957: 2871: 2845: 2800: 2768: 2569: 2371: 2314: 2264: 2229: 2187: 1896: 1849: 1476: 1861: 835:
The model existence theorem and its proof can be formalized in the framework of
117:
is such a theory, and φ is a sentence (in the same language) and every model of
3675: 3654: 3612: 3592: 3487: 3342: 2940: 2930: 2920: 2915: 2849: 2723: 2599: 2488: 2483: 2461: 2062: 1986: 867: 866:
An important consequence of the completeness theorem is that it is possible to
485: 274: 204: 627:
Given Henkin's theorem, the completeness theorem can be proved as follows: If
3774: 3649: 3327: 2834: 2619: 2609: 2579: 2564: 2234: 1808: 157: 1831: 1743: 1728: 164: 3549: 3396: 3297: 3289: 3169: 3117: 3026: 2962: 2945: 2876: 2735: 2594: 2296: 2079: 1543:
In modern logic texts, Gödel's completeness theorem is usually proved with
1053:") must be incomplete in this sense, by explicitly constructing a sentence 517: 172: 153: 149: 1746:(1930). "Die Vollständigkeit der Axiome des logischen Funktionenkalküls". 1475:
each other in ZF, they are also provably equivalent to a weak form of the
3659: 3539: 2718: 2708: 2655: 2339: 2259: 2244: 2124: 2069: 1981: 1924: 1786: 1544: 1513: 532: 168: 1732: 1100:. The second incompleteness theorem extends this result by showing that 2589: 2444: 2415: 2221: 1761: 1677: 1634: 1548: 1420:(e.g. if it includes induction for bounded existential formulas), then 1038: 390: 682:
does not have models. By the contrapositive of Henkin's theorem, then
385:. The completeness theorem then says that for any first-order theory 3741: 3644: 2697: 2614: 2574: 2538: 2474: 2286: 2276: 2249: 2012: 1956: 1892: 621: 212: 95: 1669: 1626: 3726: 3524: 2972: 2677: 2271: 1595: 216: 3322: 2114: 19:
For the subsequent theories about the limits of provability, see
1855: 1470:
formulas). Weak Kőnig's lemma is provable in ZF, the system of
1197:, the completeness theorem implies the existence of a model of 1080:
which is demonstrably neither provable nor disprovable within
897:
model theory – Using the compactness and completeness theorems
883: 2866: 2212: 2057: 1589:
Batzoglou, Serafim (2021). "Gödel's Incompleteness Theorem".
1440:
manner, each one can be effectively obtained from the other.
531:
The completeness theorem can also be understood in terms of
459:
Since the converse (soundness) also holds, it follows that
1427: 156:, which studies what can be formally proven in particular 137:
but true in the "standard" model of the natural numbers: φ
1655: 152:, which deals with what is true in different models, and 285:
The theorem can be expressed more generally in terms of
1737:(Thesis). Doctoral dissertation. University Of Vienna. 1127:
can be chosen so that it expresses the consistency of
801:, and then by the properties of the deductive system, 1793:. Hochschultext (Springer-Verlag). London: Springer. 1402: 1352: 1332: 1312: 1285: 1250: 1223: 1203: 1183: 1156: 1133: 1106: 1086: 1059: 1023: 991: 965: 945: 925: 905: 807: 766: 737: 717: 688: 659: 633: 596: 576: 493: 465: 436: 410: 353: 307: 199:. Common to all deductive systems is the notion of a 1701:
Proving the Completeness Theorem within Isabelle/HOL
1424:
shows that it has no recursive non-standard models.
148:
The completeness theorem makes a close link between
109:
The completeness theorem applies to any first-order
843:in Peano arithmetic by interpreting each symbol of 711:
is syntactically inconsistent. So a contradiction (
624:
first-order theory has a finite or countable model.
1491:The completeness theorem is a central property of 1408: 1365: 1338: 1318: 1298: 1263: 1236: 1209: 1189: 1169: 1139: 1119: 1092: 1072: 1029: 1006: 977: 951: 931: 911: 819: 793: 752: 723: 703: 674: 645: 602: 582: 505: 477: 448: 422: 365: 319: 203:. This is a sequence (or, in some cases, a finite 1891: 1017:The first incompleteness theorem states that any 141:is false in some other, "non-standard" models of 3772: 1698: 1486: 259: 1570:Original proof of Gödel's completeness theorem 2028: 1877: 1555:theorem prover. Other proofs are also known. 919:is complete (or decidable) if every sentence 830: 1739:The first proof of the completeness theorem. 277:it is the conclusion of a formal deduction. 191:for first-order logic, including systems of 1785: 1610: 884:Relationship to the incompleteness theorems 794:{\displaystyle (T\cup \lnot s)\vdash \bot } 3781:Theorems in the foundations of mathematics 2220: 2035: 2021: 1884: 1870: 526: 207:) of formulae with a specially designated 94:that establishes a correspondence between 1734:Über die Vollständigkeit des Logikkalküls 1594: 1588: 1512:A completeness theorem can be proved for 613:Another version, with connections to the 16:Fundamental theorem in mathematical logic 1854:Detlovs, Vilnis, and Podnieks, Karlis, " 25: 1428:Relationship to the compactness theorem 133:that is unprovable in a certain theory 3773: 2042: 1458:, with the equivalence provable in RCA 335:in our deductive system. We say that 2016: 1865: 1742: 1727: 167:in 1929. It was then simplified when 280: 1856:Introduction to mathematical logic. 1828:Stanford Encyclopedia of Philosophy 1495:that does not hold for all logics. 1416:is at least slightly stronger than 13: 1791:Introduction to Mathematical Logic 1721: 998: 788: 776: 744: 718: 695: 666: 590:is syntactically consistent, then 14: 3812: 1821: 1432:The completeness theorem and the 870:the semantic consequences of any 3754: 1713:from the original on 2006-02-22. 620:Every syntactically consistent, 567:with a well-orderable language, 222:A first-order formula is called 182: 1952:Gödel's incompleteness theorems 1565:Gödel's incompleteness theorems 1466:restricted to induction over Σ 889:Gödel's incompleteness theorems 861: 760:in the deductive system. Hence 535:, as a consequence of Henkin's 127:Gödel's incompleteness theorem 21:Gödel's incompleteness theorems 1815:"Gödel's completeness theorem" 1692: 1649: 1604: 1582: 1007:{\displaystyle T\vdash \neg S} 782: 767: 1: 3715:History of mathematical logic 1658:The Journal of Symbolic Logic 1614:The Journal of Symbolic Logic 1575: 1534:original proof of the theorem 753:{\displaystyle T\cup \lnot s} 704:{\displaystyle T\cup \lnot s} 675:{\displaystyle T\cup \lnot s} 3640:Primitive recursive function 1947:Gödel's completeness theorem 1699:James Margetson (Sep 2004). 1601:(p.17). Accessed 2022-12-01. 1487:Completeness in other logics 260:Gödel's original formulation 251: 129:, which is about a formula φ 90:is a fundamental theorem in 88:Gödel's completeness theorem 7: 1558: 1472:Zermelo–Fraenkel set theory 1462:(a second-order variant of 393:language, and any sentence 10: 3817: 2704:Schröder–Bernstein theorem 2431:Monadic predicate calculus 2090:Foundations of mathematics 1935:Foundations of mathematics 1749:Monatshefte für Mathematik 831:As a theorem of arithmetic 646:{\displaystyle T\models s} 478:{\displaystyle T\models s} 423:{\displaystyle T\models s} 366:{\displaystyle T\models s} 289:. We say that a sentence 18: 3750: 3737:Philosophy of mathematics 3686:Automated theorem proving 3668: 3563: 3395: 3288: 3140: 2857: 2833: 2811:Von Neumann–Bernays–Gödel 2756: 2650: 2554: 2452: 2443: 2370: 2305: 2211: 2133: 2050: 1903: 1527: 978:{\displaystyle T\vdash S} 820:{\displaystyle T\vdash s} 506:{\displaystyle T\vdash s} 449:{\displaystyle T\vdash s} 320:{\displaystyle T\vdash s} 1977:Löwenheim–Skolem theorem 615:Löwenheim–Skolem theorem 547:if there is no sentence 545:syntactically consistent 539:. We say that a theory 3387:Self-verifying theories 3208:Tarski's axiomatization 2159:Tarski's undefinability 2154:incompleteness theorems 2002:Use–mention distinction 537:model existence theorem 527:Model existence theorem 228:if it is true in every 163:It was first proved by 3761:Mathematics portal 3372:Proof of impossibility 3020:propositional variable 2330:Propositional calculus 1997:Type–token distinction 1410: 1380:In fact, the model of 1373:is false must include 1367: 1340: 1320: 1300: 1265: 1238: 1211: 1191: 1171: 1141: 1121: 1094: 1074: 1031: 1008: 979: 953: 933: 913: 821: 795: 754: 725: 705: 676: 647: 604: 584: 507: 479: 450: 424: 367: 321: 84: 3630:Kolmogorov complexity 3583:Computably enumerable 3483:Model complete theory 3275:Principia Mathematica 2335:Propositional formula 2164:Banach–Tarski paradox 1481:the ultrafilter lemma 1411: 1368: 1366:{\displaystyle S_{T}} 1341: 1321: 1301: 1299:{\displaystyle S_{T}} 1266: 1264:{\displaystyle S_{T}} 1239: 1237:{\displaystyle S_{T}} 1212: 1192: 1172: 1170:{\displaystyle S_{T}} 1142: 1122: 1120:{\displaystyle S_{T}} 1095: 1075: 1073:{\displaystyle S_{T}} 1032: 1009: 980: 954: 934: 914: 868:recursively enumerate 822: 796: 755: 726: 724:{\displaystyle \bot } 706: 677: 648: 605: 585: 508: 480: 451: 425: 368: 322: 295:syntactic consequence 197:Hilbert-style systems 29: 3578:Church–Turing thesis 3565:Computability theory 2774:continuum hypothesis 2292:Square of opposition 2150:Gödel's completeness 1920:Church–Turing thesis 1914:Entscheidungsproblem 1841:MacTutor biography: 1706:(Technical Report). 1518:intuitionistic logic 1422:Tennenbaum's theorem 1400: 1375:non-standard numbers 1350: 1330: 1310: 1283: 1248: 1221: 1201: 1181: 1177:cannot be proven in 1154: 1131: 1104: 1084: 1057: 1021: 989: 963: 959:is either provable ( 943: 923: 903: 805: 764: 735: 715: 686: 657: 631: 594: 574: 491: 463: 434: 408: 351: 341:semantic consequence 305: 98:truth and syntactic 83:proof (shown right). 3801:Works by Kurt Gödel 3732:Mathematical object 3623:P versus NP problem 3588:Computable function 3382:Reverse mathematics 3308:Logical consequence 3185:primitive recursive 3180:elementary function 2953:Free/bound variable 2806:Tarski–Grothendieck 2325:Logical connectives 2255:Logical equivalence 2105:Logical consequence 1507:Lindström's theorem 1452:reverse mathematics 1434:compactness theorem 1244:is false. In fact, 1047:Robinson arithmetic 939:in the language of 731:) is provable from 397:in the language of 287:logical consequence 187:There are numerous 177:Gisbert Hasenjaeger 3530:Transfer principle 3493:Semantics of logic 3478:Categorical theory 3454:Non-standard model 2968:Logical connective 2095:Information theory 2044:Mathematical logic 1848:2005-10-13 at the 1762:10.1007/BF01696781 1497:Second-order logic 1456:weak Kőnig's lemma 1406: 1384:theory containing 1363: 1336: 1316: 1296: 1261: 1234: 1207: 1187: 1167: 1137: 1117: 1090: 1070: 1027: 1004: 985:) or disprovable ( 975: 949: 929: 909: 817: 791: 750: 721: 701: 672: 643: 600: 580: 559:are provable from 555:and its negation ¬ 503: 475: 446: 420: 363: 317: 92:mathematical logic 85: 3768: 3767: 3700:Abstract category 3503:Theories of truth 3313:Rule of inference 3303:Natural deduction 3284: 3283: 2829: 2828: 2534:Cartesian product 2439: 2438: 2345:Many-valued logic 2320:Boolean functions 2203:Russell's paradox 2178:diagonal argument 2075:First-order logic 2010: 2009: 1493:first-order logic 1409:{\displaystyle T} 1339:{\displaystyle T} 1319:{\displaystyle T} 1210:{\displaystyle T} 1190:{\displaystyle T} 1140:{\displaystyle T} 1093:{\displaystyle T} 1030:{\displaystyle T} 952:{\displaystyle T} 932:{\displaystyle S} 912:{\displaystyle T} 603:{\displaystyle T} 583:{\displaystyle T} 331:is provable from 281:More general form 193:natural deduction 189:deductive systems 104:first-order logic 81:natural deduction 3808: 3759: 3758: 3710:History of logic 3705:Category of sets 3598:Decision problem 3377:Ordinal analysis 3318:Sequent calculus 3216:Boolean algebras 3156: 3155: 3130: 3101:logical/constant 2855: 2854: 2841: 2764:Zermelo–Fraenkel 2515:Set operations: 2450: 2449: 2387: 2218: 2217: 2198:Löwenheim–Skolem 2085:Formal semantics 2037: 2030: 2023: 2014: 2013: 1930:Effective method 1908:Cantor's theorem 1886: 1879: 1872: 1863: 1862: 1836:Juliette Kennedy 1812: 1781: 1738: 1715: 1714: 1712: 1705: 1696: 1690: 1689: 1653: 1647: 1646: 1608: 1602: 1600: 1598: 1586: 1522:Kripke semantics 1520:with respect to 1501:Henkin semantics 1464:Peano arithmetic 1415: 1413: 1412: 1407: 1372: 1370: 1369: 1364: 1362: 1361: 1345: 1343: 1342: 1337: 1325: 1323: 1322: 1317: 1305: 1303: 1302: 1297: 1295: 1294: 1270: 1268: 1267: 1262: 1260: 1259: 1243: 1241: 1240: 1235: 1233: 1232: 1216: 1214: 1213: 1208: 1196: 1194: 1193: 1188: 1176: 1174: 1173: 1168: 1166: 1165: 1146: 1144: 1143: 1138: 1126: 1124: 1123: 1118: 1116: 1115: 1099: 1097: 1096: 1091: 1079: 1077: 1076: 1071: 1069: 1068: 1036: 1034: 1033: 1028: 1013: 1011: 1010: 1005: 984: 982: 981: 976: 958: 956: 955: 950: 938: 936: 935: 930: 918: 916: 915: 910: 837:Peano arithmetic 826: 824: 823: 818: 800: 798: 797: 792: 759: 757: 756: 751: 730: 728: 727: 722: 710: 708: 707: 702: 681: 679: 678: 673: 652: 650: 649: 644: 609: 607: 606: 601: 589: 587: 586: 581: 512: 510: 509: 504: 484: 482: 481: 476: 455: 453: 452: 447: 429: 427: 426: 421: 372: 370: 369: 364: 326: 324: 323: 318: 238:completeness is 201:formal deduction 171:observed in his 75:)) holds in all 3816: 3815: 3811: 3810: 3809: 3807: 3806: 3805: 3771: 3770: 3769: 3764: 3753: 3746: 3691:Category theory 3681:Algebraic logic 3664: 3635:Lambda calculus 3573:Church encoding 3559: 3535:Truth predicate 3391: 3357:Complete theory 3280: 3149: 3145: 3141: 3136: 3128: 2848: and  2844: 2839: 2825: 2801:New Foundations 2769:axiom of choice 2752: 2714:Gödel numbering 2654: and  2646: 2550: 2435: 2385: 2366: 2315:Boolean algebra 2301: 2265:Equiconsistency 2230:Classical logic 2207: 2188:Halting problem 2176: and  2152: and  2140: and  2139: 2134:Theorems ( 2129: 2046: 2041: 2011: 2006: 1899: 1897:metamathematics 1890: 1850:Wayback Machine 1824: 1801: 1724: 1722:Further reading 1719: 1718: 1710: 1703: 1697: 1693: 1670:10.2307/2266326 1654: 1650: 1627:10.2307/2267044 1609: 1605: 1587: 1583: 1578: 1561: 1530: 1489: 1477:axiom of choice 1469: 1461: 1430: 1401: 1398: 1397: 1357: 1353: 1351: 1348: 1347: 1331: 1328: 1327: 1311: 1308: 1307: 1290: 1286: 1284: 1281: 1280: 1276: 1255: 1251: 1249: 1246: 1245: 1228: 1224: 1222: 1219: 1218: 1202: 1199: 1198: 1182: 1179: 1178: 1161: 1157: 1155: 1152: 1151: 1132: 1129: 1128: 1111: 1107: 1105: 1102: 1101: 1085: 1082: 1081: 1064: 1060: 1058: 1055: 1054: 1022: 1019: 1018: 990: 987: 986: 964: 961: 960: 944: 941: 940: 924: 921: 920: 904: 901: 900: 886: 864: 856: 833: 806: 803: 802: 765: 762: 761: 736: 733: 732: 716: 713: 712: 687: 684: 683: 658: 655: 654: 632: 629: 628: 625: 611: 595: 592: 591: 575: 572: 571: 551:such that both 529: 492: 489: 488: 464: 461: 460: 457: 435: 432: 431: 409: 406: 405: 377:holds in every 352: 349: 348: 306: 303: 302: 283: 262: 254: 225:logically valid 213:algorithmically 185: 140: 132: 24: 17: 12: 11: 5: 3814: 3804: 3803: 3798: 3793: 3788: 3783: 3766: 3765: 3751: 3748: 3747: 3745: 3744: 3739: 3734: 3729: 3724: 3723: 3722: 3712: 3707: 3702: 3693: 3688: 3683: 3678: 3676:Abstract logic 3672: 3670: 3666: 3665: 3663: 3662: 3657: 3655:Turing machine 3652: 3647: 3642: 3637: 3632: 3627: 3626: 3625: 3620: 3615: 3610: 3605: 3595: 3593:Computable set 3590: 3585: 3580: 3575: 3569: 3567: 3561: 3560: 3558: 3557: 3552: 3547: 3542: 3537: 3532: 3527: 3522: 3521: 3520: 3515: 3510: 3500: 3495: 3490: 3488:Satisfiability 3485: 3480: 3475: 3474: 3473: 3463: 3462: 3461: 3451: 3450: 3449: 3444: 3439: 3434: 3429: 3419: 3418: 3417: 3412: 3405:Interpretation 3401: 3399: 3393: 3392: 3390: 3389: 3384: 3379: 3374: 3369: 3359: 3354: 3353: 3352: 3351: 3350: 3340: 3335: 3325: 3320: 3315: 3310: 3305: 3300: 3294: 3292: 3286: 3285: 3282: 3281: 3279: 3278: 3270: 3269: 3268: 3267: 3262: 3261: 3260: 3255: 3250: 3230: 3229: 3228: 3226:minimal axioms 3223: 3212: 3211: 3210: 3199: 3198: 3197: 3192: 3187: 3182: 3177: 3172: 3159: 3157: 3138: 3137: 3135: 3134: 3133: 3132: 3120: 3115: 3114: 3113: 3108: 3103: 3098: 3088: 3083: 3078: 3073: 3072: 3071: 3066: 3056: 3055: 3054: 3049: 3044: 3039: 3029: 3024: 3023: 3022: 3017: 3012: 3002: 3001: 3000: 2995: 2990: 2985: 2980: 2975: 2965: 2960: 2955: 2950: 2949: 2948: 2943: 2938: 2933: 2923: 2918: 2916:Formation rule 2913: 2908: 2907: 2906: 2901: 2891: 2890: 2889: 2879: 2874: 2869: 2864: 2858: 2852: 2835:Formal systems 2831: 2830: 2827: 2826: 2824: 2823: 2818: 2813: 2808: 2803: 2798: 2793: 2788: 2783: 2778: 2777: 2776: 2771: 2760: 2758: 2754: 2753: 2751: 2750: 2749: 2748: 2738: 2733: 2732: 2731: 2724:Large cardinal 2721: 2716: 2711: 2706: 2701: 2687: 2686: 2685: 2680: 2675: 2660: 2658: 2648: 2647: 2645: 2644: 2643: 2642: 2637: 2632: 2622: 2617: 2612: 2607: 2602: 2597: 2592: 2587: 2582: 2577: 2572: 2567: 2561: 2559: 2552: 2551: 2549: 2548: 2547: 2546: 2541: 2536: 2531: 2526: 2521: 2513: 2512: 2511: 2506: 2496: 2491: 2489:Extensionality 2486: 2484:Ordinal number 2481: 2471: 2466: 2465: 2464: 2453: 2447: 2441: 2440: 2437: 2436: 2434: 2433: 2428: 2423: 2418: 2413: 2408: 2403: 2402: 2401: 2391: 2390: 2389: 2376: 2374: 2368: 2367: 2365: 2364: 2363: 2362: 2357: 2352: 2342: 2337: 2332: 2327: 2322: 2317: 2311: 2309: 2303: 2302: 2300: 2299: 2294: 2289: 2284: 2279: 2274: 2269: 2268: 2267: 2257: 2252: 2247: 2242: 2237: 2232: 2226: 2224: 2215: 2209: 2208: 2206: 2205: 2200: 2195: 2190: 2185: 2180: 2168:Cantor's  2166: 2161: 2156: 2146: 2144: 2131: 2130: 2128: 2127: 2122: 2117: 2112: 2107: 2102: 2097: 2092: 2087: 2082: 2077: 2072: 2067: 2066: 2065: 2054: 2052: 2048: 2047: 2040: 2039: 2032: 2025: 2017: 2008: 2007: 2005: 2004: 1999: 1994: 1989: 1987:Satisfiability 1984: 1979: 1974: 1972:Interpretation 1969: 1964: 1959: 1954: 1949: 1944: 1943: 1942: 1932: 1927: 1922: 1917: 1910: 1904: 1901: 1900: 1889: 1888: 1881: 1874: 1866: 1860: 1859: 1852: 1839: 1823: 1822:External links 1820: 1819: 1818: 1799: 1783: 1756:(1): 349–360. 1740: 1723: 1720: 1717: 1716: 1691: 1648: 1621:(3): 159–166. 1603: 1580: 1579: 1577: 1574: 1573: 1572: 1567: 1560: 1557: 1529: 1526: 1488: 1485: 1467: 1459: 1429: 1426: 1405: 1360: 1356: 1335: 1315: 1293: 1289: 1274: 1258: 1254: 1231: 1227: 1206: 1186: 1164: 1160: 1136: 1114: 1110: 1089: 1067: 1063: 1026: 1003: 1000: 997: 994: 974: 971: 968: 948: 928: 908: 885: 882: 863: 860: 854: 832: 829: 816: 813: 810: 790: 787: 784: 781: 778: 775: 772: 769: 749: 746: 743: 740: 720: 700: 697: 694: 691: 671: 668: 665: 662: 642: 639: 636: 619: 599: 579: 569: 528: 525: 502: 499: 496: 486:if and only if 474: 471: 468: 445: 442: 439: 419: 416: 413: 403: 391:well-orderable 362: 359: 356: 316: 313: 310: 282: 279: 275:if and only if 261: 258: 253: 250: 184: 181: 158:formal systems 138: 130: 15: 9: 6: 4: 3: 2: 3813: 3802: 3799: 3797: 3794: 3792: 3789: 3787: 3784: 3782: 3779: 3778: 3776: 3763: 3762: 3757: 3749: 3743: 3740: 3738: 3735: 3733: 3730: 3728: 3725: 3721: 3718: 3717: 3716: 3713: 3711: 3708: 3706: 3703: 3701: 3697: 3694: 3692: 3689: 3687: 3684: 3682: 3679: 3677: 3674: 3673: 3671: 3667: 3661: 3658: 3656: 3653: 3651: 3650:Recursive set 3648: 3646: 3643: 3641: 3638: 3636: 3633: 3631: 3628: 3624: 3621: 3619: 3616: 3614: 3611: 3609: 3606: 3604: 3601: 3600: 3599: 3596: 3594: 3591: 3589: 3586: 3584: 3581: 3579: 3576: 3574: 3571: 3570: 3568: 3566: 3562: 3556: 3553: 3551: 3548: 3546: 3543: 3541: 3538: 3536: 3533: 3531: 3528: 3526: 3523: 3519: 3516: 3514: 3511: 3509: 3506: 3505: 3504: 3501: 3499: 3496: 3494: 3491: 3489: 3486: 3484: 3481: 3479: 3476: 3472: 3469: 3468: 3467: 3464: 3460: 3459:of arithmetic 3457: 3456: 3455: 3452: 3448: 3445: 3443: 3440: 3438: 3435: 3433: 3430: 3428: 3425: 3424: 3423: 3420: 3416: 3413: 3411: 3408: 3407: 3406: 3403: 3402: 3400: 3398: 3394: 3388: 3385: 3383: 3380: 3378: 3375: 3373: 3370: 3367: 3366:from ZFC 3363: 3360: 3358: 3355: 3349: 3346: 3345: 3344: 3341: 3339: 3336: 3334: 3331: 3330: 3329: 3326: 3324: 3321: 3319: 3316: 3314: 3311: 3309: 3306: 3304: 3301: 3299: 3296: 3295: 3293: 3291: 3287: 3277: 3276: 3272: 3271: 3266: 3265:non-Euclidean 3263: 3259: 3256: 3254: 3251: 3249: 3248: 3244: 3243: 3241: 3238: 3237: 3235: 3231: 3227: 3224: 3222: 3219: 3218: 3217: 3213: 3209: 3206: 3205: 3204: 3200: 3196: 3193: 3191: 3188: 3186: 3183: 3181: 3178: 3176: 3173: 3171: 3168: 3167: 3165: 3161: 3160: 3158: 3153: 3147: 3142:Example  3139: 3131: 3126: 3125: 3124: 3121: 3119: 3116: 3112: 3109: 3107: 3104: 3102: 3099: 3097: 3094: 3093: 3092: 3089: 3087: 3084: 3082: 3079: 3077: 3074: 3070: 3067: 3065: 3062: 3061: 3060: 3057: 3053: 3050: 3048: 3045: 3043: 3040: 3038: 3035: 3034: 3033: 3030: 3028: 3025: 3021: 3018: 3016: 3013: 3011: 3008: 3007: 3006: 3003: 2999: 2996: 2994: 2991: 2989: 2986: 2984: 2981: 2979: 2976: 2974: 2971: 2970: 2969: 2966: 2964: 2961: 2959: 2956: 2954: 2951: 2947: 2944: 2942: 2939: 2937: 2934: 2932: 2929: 2928: 2927: 2924: 2922: 2919: 2917: 2914: 2912: 2909: 2905: 2902: 2900: 2899:by definition 2897: 2896: 2895: 2892: 2888: 2885: 2884: 2883: 2880: 2878: 2875: 2873: 2870: 2868: 2865: 2863: 2860: 2859: 2856: 2853: 2851: 2847: 2842: 2836: 2832: 2822: 2819: 2817: 2814: 2812: 2809: 2807: 2804: 2802: 2799: 2797: 2794: 2792: 2789: 2787: 2786:Kripke–Platek 2784: 2782: 2779: 2775: 2772: 2770: 2767: 2766: 2765: 2762: 2761: 2759: 2755: 2747: 2744: 2743: 2742: 2739: 2737: 2734: 2730: 2727: 2726: 2725: 2722: 2720: 2717: 2715: 2712: 2710: 2707: 2705: 2702: 2699: 2695: 2691: 2688: 2684: 2681: 2679: 2676: 2674: 2671: 2670: 2669: 2665: 2662: 2661: 2659: 2657: 2653: 2649: 2641: 2638: 2636: 2633: 2631: 2630:constructible 2628: 2627: 2626: 2623: 2621: 2618: 2616: 2613: 2611: 2608: 2606: 2603: 2601: 2598: 2596: 2593: 2591: 2588: 2586: 2583: 2581: 2578: 2576: 2573: 2571: 2568: 2566: 2563: 2562: 2560: 2558: 2553: 2545: 2542: 2540: 2537: 2535: 2532: 2530: 2527: 2525: 2522: 2520: 2517: 2516: 2514: 2510: 2507: 2505: 2502: 2501: 2500: 2497: 2495: 2492: 2490: 2487: 2485: 2482: 2480: 2476: 2472: 2470: 2467: 2463: 2460: 2459: 2458: 2455: 2454: 2451: 2448: 2446: 2442: 2432: 2429: 2427: 2424: 2422: 2419: 2417: 2414: 2412: 2409: 2407: 2404: 2400: 2397: 2396: 2395: 2392: 2388: 2383: 2382: 2381: 2378: 2377: 2375: 2373: 2369: 2361: 2358: 2356: 2353: 2351: 2348: 2347: 2346: 2343: 2341: 2338: 2336: 2333: 2331: 2328: 2326: 2323: 2321: 2318: 2316: 2313: 2312: 2310: 2308: 2307:Propositional 2304: 2298: 2295: 2293: 2290: 2288: 2285: 2283: 2280: 2278: 2275: 2273: 2270: 2266: 2263: 2262: 2261: 2258: 2256: 2253: 2251: 2248: 2246: 2243: 2241: 2238: 2236: 2235:Logical truth 2233: 2231: 2228: 2227: 2225: 2223: 2219: 2216: 2214: 2210: 2204: 2201: 2199: 2196: 2194: 2191: 2189: 2186: 2184: 2181: 2179: 2175: 2171: 2167: 2165: 2162: 2160: 2157: 2155: 2151: 2148: 2147: 2145: 2143: 2137: 2132: 2126: 2123: 2121: 2118: 2116: 2113: 2111: 2108: 2106: 2103: 2101: 2098: 2096: 2093: 2091: 2088: 2086: 2083: 2081: 2078: 2076: 2073: 2071: 2068: 2064: 2061: 2060: 2059: 2056: 2055: 2053: 2049: 2045: 2038: 2033: 2031: 2026: 2024: 2019: 2018: 2015: 2003: 2000: 1998: 1995: 1993: 1990: 1988: 1985: 1983: 1980: 1978: 1975: 1973: 1970: 1968: 1965: 1963: 1960: 1958: 1955: 1953: 1950: 1948: 1945: 1941: 1938: 1937: 1936: 1933: 1931: 1928: 1926: 1923: 1921: 1918: 1916: 1915: 1911: 1909: 1906: 1905: 1902: 1898: 1894: 1887: 1882: 1880: 1875: 1873: 1868: 1867: 1864: 1857: 1853: 1851: 1847: 1844: 1840: 1837: 1833: 1829: 1826: 1825: 1816: 1810: 1806: 1802: 1796: 1792: 1788: 1784: 1779: 1775: 1771: 1767: 1763: 1759: 1755: 1752:(in German). 1751: 1750: 1745: 1741: 1736: 1735: 1730: 1726: 1725: 1709: 1702: 1695: 1687: 1683: 1679: 1675: 1671: 1667: 1663: 1659: 1652: 1644: 1640: 1636: 1632: 1628: 1624: 1620: 1616: 1615: 1607: 1597: 1592: 1585: 1581: 1571: 1568: 1566: 1563: 1562: 1556: 1554: 1550: 1546: 1541: 1539: 1535: 1525: 1523: 1519: 1515: 1510: 1508: 1504: 1502: 1498: 1494: 1484: 1482: 1478: 1473: 1465: 1457: 1453: 1448: 1445: 1441: 1439: 1435: 1425: 1423: 1419: 1403: 1394: 1391: 1387: 1383: 1378: 1376: 1358: 1354: 1333: 1313: 1291: 1287: 1278: 1256: 1252: 1229: 1225: 1204: 1184: 1162: 1158: 1148: 1134: 1112: 1108: 1087: 1065: 1061: 1052: 1048: 1045:and contains 1044: 1040: 1024: 1015: 1001: 995: 992: 972: 969: 966: 946: 926: 906: 898: 894: 890: 881: 878: 875: 873: 869: 859: 857: 850: 846: 842: 838: 828: 814: 811: 808: 785: 779: 773: 770: 747: 741: 738: 698: 692: 689: 669: 663: 660: 640: 637: 634: 623: 618: 616: 597: 577: 568: 566: 562: 558: 554: 550: 546: 542: 538: 534: 524: 521: 519: 514: 500: 497: 494: 487: 472: 469: 466: 443: 440: 437: 417: 414: 411: 402: 400: 396: 392: 388: 384: 380: 376: 360: 357: 354: 346: 342: 338: 334: 330: 314: 311: 308: 300: 296: 292: 288: 278: 276: 272: 271: 265: 257: 249: 245: 243: 242: 236: 231: 227: 226: 220: 218: 214: 210: 206: 202: 198: 194: 190: 183:Preliminaries 180: 178: 174: 170: 166: 161: 159: 155: 151: 146: 144: 136: 128: 124: 120: 116: 112: 107: 105: 101: 97: 93: 89: 82: 78: 74: 70: 66: 62: 59: 56: 52: 48: 44: 40: 36: 33: 30:The formula ( 28: 22: 3796:Proof theory 3791:Model theory 3786:Metatheorems 3752: 3550:Ultraproduct 3397:Model theory 3362:Independence 3298:Formal proof 3290:Proof theory 3273: 3246: 3203:real numbers 3175:second-order 3086:Substitution 2963:Metalanguage 2904:conservative 2877:Axiom schema 2821:Constructive 2791:Morse–Kelley 2757:Set theories 2736:Aleph number 2729:inaccessible 2635:Grothendieck 2519:intersection 2406:Higher-order 2394:Second-order 2340:Truth tables 2297:Venn diagram 2149: 2080:Formal proof 1992:Independence 1967:Decidability 1962:Completeness 1946: 1912: 1814: 1790: 1753: 1747: 1733: 1694: 1664:(1): 42–48. 1661: 1657: 1651: 1618: 1612: 1606: 1584: 1542: 1537: 1531: 1511: 1505: 1490: 1449: 1446: 1442: 1431: 1417: 1395: 1389: 1385: 1381: 1379: 1149: 1050: 1016: 899:): A theory 892: 887: 879: 876: 865: 862:Consequences 848: 844: 840: 834: 626: 612: 610:has a model. 564: 560: 556: 552: 548: 544: 540: 530: 522: 518:group theory 515: 458: 398: 394: 386: 382: 374: 344: 340: 336: 332: 328: 298: 297:of a theory 294: 290: 284: 268: 266: 263: 255: 246: 239: 234: 223: 221: 208: 200: 186: 173:Ph.D. thesis 162: 154:proof theory 150:model theory 147: 142: 134: 122: 118: 114: 108: 87: 86: 72: 68: 64: 60: 54: 46: 42: 38: 34: 3660:Type theory 3608:undecidable 3540:Truth value 3427:equivalence 3106:non-logical 2719:Enumeration 2709:Isomorphism 2656:cardinality 2640:Von Neumann 2605:Ultrafilter 2570:Uncountable 2504:equivalence 2421:Quantifiers 2411:Fixed-point 2380:First-order 2260:Consistency 2245:Proposition 2222:Traditional 2193:Lindström's 2183:Compactness 2125:Type theory 2070:Cardinality 1982:Metatheorem 1940:of geometry 1925:Consistency 1843:Kurt Gödel. 1813:Chapter 5: 1787:Hans Hermes 1514:modal logic 533:consistency 169:Leon Henkin 100:provability 3775:Categories 3471:elementary 3164:arithmetic 3032:Quantifier 3010:functional 2882:Expression 2600:Transitive 2544:identities 2529:complement 2462:hereditary 2445:Set theory 1832:Kurt Gödel 1800:3540058192 1770:56.0046.04 1596:2112.06641 1576:References 1549:term model 1540:argument. 1039:consistent 347:, denoted 301:, denoted 209:conclusion 165:Kurt Gödel 77:structures 3742:Supertask 3645:Recursion 3603:decidable 3437:saturated 3415:of models 3338:deductive 3333:axiomatic 3253:Hilbert's 3240:Euclidean 3221:canonical 3144:axiomatic 3076:Signature 3005:Predicate 2894:Extension 2816:Ackermann 2741:Operation 2620:Universal 2610:Recursive 2585:Singleton 2580:Inhabited 2565:Countable 2555:Types of 2539:power set 2509:partition 2426:Predicate 2372:Predicate 2287:Syllogism 2277:Soundness 2250:Inference 2240:Tautology 2142:paradoxes 1957:Soundness 1893:Metalogic 1809:1431-4657 1778:123343522 1479:known as 1438:effective 1396:Also, if 1346:in which 1217:in which 1043:effective 1037:which is 999:¬ 996:⊢ 970:⊢ 872:effective 812:⊢ 789:⊥ 786:⊢ 777:¬ 774:∪ 745:¬ 742:∪ 719:⊥ 696:¬ 693:∪ 667:¬ 664:∪ 638:⊨ 622:countable 498:⊢ 470:⊨ 441:⊢ 415:⊨ 358:⊨ 312:⊢ 270:soundness 252:Statement 241:soundness 230:structure 179:in 1953. 3727:Logicism 3720:timeline 3696:Concrete 3555:Validity 3525:T-schema 3518:Kripke's 3513:Tarski's 3508:semantic 3498:Strength 3447:submodel 3442:spectrum 3410:function 3258:Tarski's 3247:Elements 3234:geometry 3190:Robinson 3111:variable 3096:function 3069:spectrum 3059:Sentence 3015:variable 2958:Language 2911:Relation 2872:Automata 2862:Alphabet 2846:language 2700:-jection 2678:codomain 2664:Function 2625:Universe 2595:Infinite 2499:Relation 2282:Validity 2272:Argument 2170:theorem, 1846:Archived 1789:(1973). 1744:Gödel, K 1731:(1929). 1729:Gödel, K 1708:Archived 1686:45705695 1643:28935946 1559:See also 1553:Isabelle 1532:Gödel's 1277:sentence 1147:itself. 893:complete 617:, says: 235:complete 217:computer 96:semantic 3669:Related 3466:Diagram 3364: ( 3343:Hilbert 3328:Systems 3323:Theorem 3201:of the 3146:systems 2926:Formula 2921:Grammar 2837: ( 2781:General 2494:Forcing 2479:Element 2399:Monadic 2174:paradox 2115:Theorem 2051:General 1678:2266326 1635:2267044 1306:within 653:, then 430:, then 389:with a 3432:finite 3195:Skolem 3148:  3123:Theory 3091:Symbol 3081:String 3064:atomic 2941:ground 2936:closed 2931:atomic 2887:ground 2850:syntax 2746:binary 2673:domain 2590:Finite 2355:finite 2213:Logics 2172:  2120:Theory 1807:  1797:  1776:  1768:  1684:  1676:  1641:  1633:  1545:Henkin 1538:ad hoc 1528:Proofs 1390:always 1150:Since 215:(by a 111:theory 3422:Model 3170:Peano 3027:Proof 2867:Arity 2796:Naive 2683:image 2615:Fuzzy 2575:Empty 2524:union 2469:Class 2110:Model 2100:Lemma 2058:Axiom 1834:"—by 1774:S2CID 1711:(PDF) 1704:(PDF) 1682:S2CID 1674:JSTOR 1639:S2CID 1631:JSTOR 1591:arXiv 1271:is a 895:(see 379:model 373:, if 339:is a 327:, if 293:is a 113:: If 3545:Type 3348:list 3152:list 3129:list 3118:Term 3052:rank 2946:open 2840:list 2652:Maps 2557:sets 2416:Free 2386:list 2136:list 2063:list 1895:and 1805:ISSN 1795:ISBN 205:tree 195:and 3232:of 3214:of 3162:of 2694:Sur 2668:Map 2475:Ur- 2457:Set 1830:: " 1766:JFM 1758:doi 1666:doi 1623:doi 1516:or 1382:any 1014:). 858:). 570:if 543:is 404:if 381:of 343:of 145:.) 102:in 49:)) 3777:: 3618:NP 3242:: 3236:: 3166:: 2843:), 2698:Bi 2690:In 1803:. 1772:. 1764:. 1754:37 1680:. 1672:. 1662:18 1660:. 1637:. 1629:. 1619:14 1617:. 1524:. 1377:. 1049:(" 1041:, 827:. 401:, 160:. 106:. 63:. 53:(∀ 37:. 3698:/ 3613:P 3368:) 3154:) 3150:( 3047:∀ 3042:! 3037:∃ 2998:= 2993:↔ 2988:→ 2983:∧ 2978:∨ 2973:¬ 2696:/ 2692:/ 2666:/ 2477:) 2473:( 2360:∞ 2350:3 2138:) 2036:e 2029:t 2022:v 1885:e 1878:t 1871:v 1858:" 1838:. 1817:. 1811:. 1780:. 1760:: 1688:. 1668:: 1645:. 1625:: 1599:. 1593:: 1468:1 1460:0 1418:Q 1404:T 1386:Q 1359:T 1355:S 1334:T 1314:T 1292:T 1288:S 1275:1 1273:Π 1257:T 1253:S 1230:T 1226:S 1205:T 1185:T 1163:T 1159:S 1135:T 1113:T 1109:S 1088:T 1066:T 1062:S 1051:Q 1025:T 1002:S 993:T 973:S 967:T 947:T 927:S 907:T 855:2 853:Δ 849:T 845:T 841:T 815:s 809:T 783:) 780:s 771:T 768:( 748:s 739:T 699:s 690:T 670:s 661:T 641:s 635:T 598:T 578:T 565:T 561:T 557:s 553:s 549:s 541:T 501:s 495:T 473:s 467:T 456:. 444:s 438:T 418:s 412:T 399:T 395:s 387:T 383:T 375:s 361:s 355:T 345:T 337:s 333:T 329:s 315:s 309:T 299:T 291:s 143:T 139:u 135:T 131:u 123:T 119:T 115:T 73:y 71:, 69:x 67:( 65:R 61:y 58:∃ 55:x 51:→ 47:x 45:, 43:x 41:( 39:R 35:x 32:∀ 23:.

Index

Gödel's incompleteness theorems




structures
natural deduction
mathematical logic
semantic
provability
first-order logic
theory
Gödel's incompleteness theorem
model theory
proof theory
formal systems
Kurt Gödel
Leon Henkin
Ph.D. thesis
Gisbert Hasenjaeger
deductive systems
natural deduction
Hilbert-style systems
tree
algorithmically
computer
logically valid
structure
soundness
soundness

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.