2960:
265:
25:
480:) or its negation, we will always halt, and furthermore, the answer it gives us will be true (by soundness). This means that this gives us an algorithm to decide the halting problem. Since we know that there cannot be such an algorithm, it follows that the assumption that there is a consistent and complete axiomatization of all true first-order logic statements about natural numbers must be false.
169:. For decision problems on natural numbers, the set consists of those numbers that the decision problem answers "yes" to. For example, the decision problem "is the input even?" is formalized as the set of even numbers. A decision problem whose input consists of strings or more complex values is formalized as the set of numbers that, via a specific
731:, which has applications in computer science, is also undecidable from the Peano axioms but provable in set theory. In fact Kruskal's tree theorem (or its finite form) is undecidable in a much stronger system codifying the principles acceptable on basis of a philosophy of mathematics called predicativism.
321:
are very similar to those raised by the halting problem, and the proofs are quite similar. In fact, a weaker form of the First
Incompleteness Theorem is an easy consequence of the undecidability of the halting problem. This weaker form differs from the standard statement of the incompleteness theorem
632:
the axiom of choice). These results do not require the incompleteness theorem. Gödel proved in 1940 that neither of these statements could be disproved in ZF or ZFC set theory. In the 1960s, Cohen proved that neither is provable from ZF, and the continuum hypothesis cannot be proven from ZFC.
581:
of the statement is well-defined, or whether it can be determined by other means. Undecidability only implies that the particular deductive system being considered does not prove the truth or falsity of the statement. Whether there exist so-called "absolutely undecidable" statements, whose truth
342:
of the strong form. It is important to observe that the statement of the standard form of Gödel's First
Incompleteness Theorem is completely unconcerned with the truth value of a statement, but only concerns the issue of whether it is possible to find it through a
153:
A decision problem is a question which, for every input in some infinite set of inputs, answers "yes" or "no". Those inputs can be numbers (for example, the decision problem "is the input a prime number?") or other values of some other kind, such as
573:
is sometimes used instead of undecidable for the "neither provable nor refutable" sense. The usage of "independent" is also ambiguous, however. It can mean just "not provable", leaving open whether an independent statement might be refuted.
532:
There are two distinct senses of the word "undecidable" in contemporary use. The first of these is the sense used in relation to Gödel's theorems, that of a statement being neither provable nor refutable in a specified
549:
that correctly answers every question in the problem set. The connection between these two is that if a decision problem is undecidable (in the recursion theoretical sense) then there is no consistent, effective
785:
In 2019, Ben-David and colleagues constructed an example of a learning model (named EMX), and showed a family of functions whose learnability in EMX is undecidable in standard set theory.
668:; however, the problem becomes impossible if solutions are constrained to integer values only. Matiyasevich showed this problem to be unsolvable by mapping a Diophantine equation to a
887:
350:
The weaker form of the theorem can be proved from the undecidability of the halting problem as follows. Assume that we have a sound (and hence consistent) and complete
751:
and proved another incompleteness theorem in that setting. Chaitin's theorem states that for any theory that can represent enough arithmetic, there is an upper bound
644:, posed in 1900 as a challenge to the next century of mathematicians, cannot be solved. Hilbert's challenge sought an algorithm which finds all solutions of a
1091:, in Proceedings of the 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007, held in Shanghai, China in May 2007.
1339:
989:
2014:
889:, only countably many of which can be decided by algorithms. However, also only countably many decision problems can be stated in any language.
145:
is an example: it can be proven that there is no algorithm that correctly determines whether an arbitrary program eventually halts when run.
545:, which are countably infinite sets of questions each requiring a yes or no answer. Such a problem is said to be undecidable if there is no
2097:
1238:
89:
2411:
61:
577:
Undecidability of a statement in a particular deductive system does not, in and of itself, address the question of whether the
2569:
523:
374:, computes a true first-order logic statement about natural numbers, and that for all true statements, there is at least one
1357:
2424:
1747:
282:
68:
42:
330:
is impossible. The "sound" part is the weakening: it means that we require the axiomatic system in question to prove only
318:
2989:
2429:
2419:
2156:
2009:
1362:
910:
1353:
2565:
1096:
601:
for which no algorithm exists to determine whether two words are equivalent. This was shown to be the case in 1955.
570:
527:
304:
108:
75:
1907:
2662:
2406:
1231:
1967:
1660:
625:
126:
1401:
57:
2923:
2625:
2388:
2383:
2208:
1629:
1313:
748:
687:
halts on a given program—is undecidable, in the second sense of the term. This result was later generalized by
286:
46:
934:
2994:
2984:
2918:
2701:
2618:
2331:
2262:
2139:
1381:
1045:
362:. Then we can build an algorithm that enumerates all these statements. This means that there is an algorithm
2843:
2669:
2355:
1989:
1588:
489:
2721:
2716:
2326:
2065:
1994:
1323:
1224:
192:
is called undecidable. A problem is called partially decidable, semi-decidable, solvable, or provable if
2650:
2240:
1634:
1602:
1293:
1024:
669:
641:
605:
197:
2940:
2889:
2786:
2284:
2245:
1722:
1367:
728:
583:
155:
1396:
2781:
2711:
2250:
2102:
2085:
1808:
1288:
710:
649:
2613:
2590:
2551:
2437:
2378:
2024:
1944:
1788:
1732:
1345:
853:
722:
590:
275:
82:
35:
608:
has given two concrete examples of undecidable statements (in the first sense of the term): The
589:
One of the first problems suspected to be undecidable, in the second sense of the term, was the
2903:
2630:
2608:
2575:
2468:
2314:
2299:
2272:
2223:
2107:
2042:
1867:
1833:
1828:
1702:
1533:
1510:
804:
734:
2833:
2686:
2478:
2196:
1932:
1838:
1697:
1682:
1563:
1538:
1043:
Shelah, Saharon (1974). "Infinite
Abelian groups, Whitehead problem and some constructions".
756:
386:) yields that statement. Now suppose we want to decide if the algorithm with representation
2806:
2768:
2645:
2449:
2289:
2213:
2191:
2019:
1977:
1876:
1843:
1707:
1495:
1406:
1176:
1116:
Ben-David, Shai; Hrubeš, Pavel; Moran, Shay; Shpilka, Amir; Yehudayoff, Amir (2019-01-07).
1066:
799:
794:
660:
in any number of variables with integer coefficients. Since we have only one equation but
645:
609:
538:
209:
122:
1002:
8:
2935:
2826:
2791:
2748:
2635:
2585:
2511:
2456:
2393:
2186:
2181:
2129:
1897:
1886:
1558:
1458:
1386:
1377:
1373:
1308:
1303:
598:
546:
1180:
394:. We know that this statement can be expressed with a first-order logic statement, say
2964:
2733:
2696:
2681:
2674:
2657:
2461:
2443:
2309:
2235:
2218:
2171:
1984:
1893:
1727:
1712:
1672:
1624:
1609:
1597:
1553:
1528:
1298:
1247:
1145:
1088:
1070:
775:
768:
741:
of the natural numbers that Kirby and Paris showed is undecidable in Peano arithmetic.
511:
344:
1917:
170:
2959:
2899:
2706:
2516:
2506:
2398:
2279:
2114:
2090:
1871:
1855:
1760:
1737:
1614:
1583:
1548:
1443:
1278:
1202:
1194:
1149:
1137:
1092:
1074:
1015:
699:
688:
637:
582:
value can never be known or is ill-specified, is a controversial point among various
355:
335:
247:
possible program-input pairs necessarily cannot exist. Hence, the halting problem is
1117:
228:
and a finite input, decide whether the program finishes running or will run forever.
2913:
2908:
2801:
2758:
2580:
2541:
2536:
2521:
2347:
2304:
2201:
1999:
1949:
1523:
1485:
1184:
1129:
1100:
1054:
998:
833:
This means that there exists an algorithm that halts eventually when the answer is
542:
534:
499:
225:
217:
134:
2894:
2884:
2838:
2821:
2776:
2738:
2640:
2560:
2367:
2294:
2267:
2255:
2161:
2075:
2049:
2004:
1972:
1773:
1575:
1518:
1468:
1433:
1391:
1104:
1062:
779:
744:
680:
621:
507:
213:
166:
159:
142:
987:(1955), "On the algorithmic unsolvability of the word problem in group theory",
2879:
2858:
2816:
2796:
2691:
2546:
2144:
2134:
2124:
2119:
2053:
1927:
1803:
1692:
1687:
1665:
1266:
1189:
1164:
814:
714:
695:
684:
653:
359:
351:
323:
240:
1133:
2978:
2853:
2531:
2038:
1823:
1813:
1783:
1768:
1438:
1198:
1141:
984:
809:
738:
665:
551:
185:
406:). Since the axiomatization is complete it follows that either there is an
2753:
2600:
2501:
2493:
2373:
2321:
2230:
2166:
2149:
2080:
1939:
1798:
1500:
1283:
1206:
764:
718:
703:
2863:
2743:
1922:
1912:
1859:
1543:
1463:
1448:
1328:
1273:
676:
664:
variables, infinitely many solutions exist (and are easy to find) in the
578:
232:
706:
is undecidable, in the first sense of the term, in standard set theory.
1793:
1648:
1619:
1425:
1058:
657:
617:
289: in this section. Unsourced material may be challenged and removed.
203:
2945:
2848:
1901:
1818:
1778:
1742:
1678:
1490:
1480:
1453:
1216:
339:
327:
236:
180:
is called decidable or effectively solvable if the formalized set of
173:, correspond to inputs that satisfy the decision problem's criteria.
138:
959:
264:
24:
2930:
2728:
2176:
1881:
1475:
594:
503:
254:
165:
The formal representation of a decision problem is a subset of the
774:
In 2007, researchers Kurtz and Simon, building on earlier work by
755:
such that no specific number can be proven in that theory to have
717:, is undecidable in the axiomatization of arithmetic given by the
2526:
1318:
494:
Undecidable problems can be related to different topics, such as
461:
569:
Because of the two meanings of the word undecidable, the term
2070:
1416:
1261:
495:
1115:
16:
Yes-or-no question that cannot ever be solved by a computer
778:
in the 1970s, proved that a natural generalization of the
334:
statements about natural numbers. Since soundness implies
613:
137:
for which it is proved to be impossible to construct an
1089:"The Undecidability of the Generalized Collatz Problem"
856:
721:
but can be proven to be true in the larger system of
597:
in 1911, which asks if there is a finitely presented
517:
141:
that always leads to a correct yes-or-no answer. The
648:. A Diophantine equation is a more general case of
204:
Example: the halting problem in computability theory
990:
Proceedings of the
Steklov Institute of Mathematics
483:
49:. Unsourced material may be challenged and removed.
881:
510:many undecidable problems, any list, even one of
326:of the natural numbers that is both complete and
2976:
255:Relationship with Gödel's incompleteness theorem
911:"Formal Computational Models and Computability"
709:In 1977, Paris and Harrington proved that the
1232:
672:and invoking Gödel's Incompleteness Theorem.
1014:
870:
857:
1022:[Enumerable sets are Diophantine].
1424:
1239:
1225:
763:. While Gödel's theorem is related to the
537:. The second sense is used in relation to
1188:
1165:"Unprovability comes to machine learning"
305:Learn how and when to remove this message
109:Learn how and when to remove this message
957:
983:
2977:
1246:
1162:
1042:
960:"Rosser's Theorem via Turing machines"
850:There are uncountably many subsets of
224:Given the description of an arbitrary
1220:
837:but may run forever if the answer is
624:can neither be proved nor refuted in
612:can neither be proved nor refuted in
558:in the problem either "the answer to
541:and applies not to statements but to
524:List of statements independent of ZFC
338:, this weaker form can be seen as a
287:adding citations to reliable sources
258:
243:that solves the halting problem for
47:adding citations to reliable sources
18:
1020:Диофантовость перечислимых множеств
747:produced undecidable statements in
13:
683:—the question of whether or not a
518:Examples of undecidable statements
14:
3006:
1118:"Learnability can be undecidable"
767:, Chaitin's result is related to
528:Independence (mathematical logic)
2958:
1087:Kurtz, Stuart A.; Simon, Janos,
958:Aaronson, Scott (21 July 2011).
616:(the standard axiomatization of
554:which proves for every question
484:Examples of undecidable problems
263:
220:which can be stated as follows:
23:
1156:
1109:
636:In 1970, Russian mathematician
604:The combined work of Gödel and
370:) that, given a natural number
319:Gödel's incompleteness theorems
274:needs additional citations for
127:computational complexity theory
34:needs additional citations for
1081:
1036:
1008:
977:
951:
927:
903:
844:
827:
749:algorithmic information theory
235:proved in 1936 that a general
1:
2919:History of mathematical logic
1046:Israel Journal of Mathematics
896:
628:(which is all the ZFC axioms
514:, is necessarily incomplete.
148:
2844:Primitive recursive function
1105:10.1007/978-3-540-72504-6_49
490:List of undecidable problems
7:
1122:Nature Machine Intelligence
882:{\displaystyle \{0,1\}^{*}}
788:
10:
3011:
1908:Schröder–Bernstein theorem
1635:Monadic predicate calculus
1294:Foundations of mathematics
1190:10.1038/d41586-019-00012-4
1025:Doklady Akademii Nauk SSSR
711:Paris-Harrington principle
670:recursively enumerable set
562:is yes" or "the answer to
521:
487:
198:recursively enumerable set
2990:Logic in computer science
2954:
2941:Philosophy of mathematics
2890:Automated theorem proving
2872:
2767:
2599:
2492:
2344:
2061:
2037:
2015:Von Neumann–Bernays–Gödel
1960:
1854:
1758:
1656:
1647:
1574:
1509:
1415:
1337:
1254:
1134:10.1038/s42256-018-0002-3
737:is a statement about the
1019:
820:
2591:Self-verifying theories
2412:Tarski's axiomatization
1363:Tarski's undefinability
1358:incompleteness theorems
723:second-order arithmetic
642:Hilbert's Tenth Problem
591:word problem for groups
317:The concepts raised by
2965:Mathematics portal
2576:Proof of impossibility
2224:propositional variable
1534:Propositional calculus
883:
805:Proof of impossibility
729:Kruskal's tree theorem
2834:Kolmogorov complexity
2787:Computably enumerable
2687:Model complete theory
2479:Principia Mathematica
1539:Propositional formula
1368:Banach–Tarski paradox
884:
757:Kolmogorov complexity
650:Fermat's Last Theorem
584:philosophical schools
468:until we either find
322:by asserting that an
251:for Turing machines.
58:"Undecidable problem"
2995:Undecidable problems
2985:Computability theory
2782:Church–Turing thesis
2769:Computability theory
1978:continuum hypothesis
1496:Square of opposition
1354:Gödel's completeness
1163:Reyzin, Lev (2019).
915:www.cs.rochester.edu
854:
800:Entscheidungsproblem
795:Decidability (logic)
646:Diophantine equation
610:continuum hypothesis
539:computability theory
283:improve this article
210:computability theory
123:computability theory
43:improve this article
2936:Mathematical object
2827:P versus NP problem
2792:Computable function
2586:Reverse mathematics
2512:Logical consequence
2389:primitive recursive
2384:elementary function
2157:Free/bound variable
2010:Tarski–Grothendieck
1529:Logical connectives
1459:Logical equivalence
1309:Logical consequence
1181:2019Natur.565..166R
735:Goodstein's theorem
713:, a version of the
547:computable function
176:A decision problem
131:undecidable problem
2734:Transfer principle
2697:Semantics of logic
2682:Categorical theory
2658:Non-standard model
2172:Logical connective
1299:Information theory
1248:Mathematical logic
1059:10.1007/BF02757281
1016:Matiyasevich, Yuri
935:"decision problem"
879:
506:. Since there are
345:mathematical proof
2972:
2971:
2904:Abstract category
2707:Theories of truth
2517:Rule of inference
2507:Natural deduction
2488:
2487:
2033:
2032:
1738:Cartesian product
1643:
1642:
1549:Many-valued logic
1524:Boolean functions
1407:Russell's paradox
1382:diagonal argument
1279:First-order logic
1175:(7738): 166–167.
985:Novikov, Pyotr S.
700:Whitehead problem
638:Yuri Matiyasevich
593:, first posed by
543:decision problems
500:abstract machines
430:) or there is an
358:statements about
356:first-order logic
315:
314:
307:
119:
118:
111:
93:
3002:
2963:
2962:
2914:History of logic
2909:Category of sets
2802:Decision problem
2581:Ordinal analysis
2522:Sequent calculus
2420:Boolean algebras
2360:
2359:
2334:
2305:logical/constant
2059:
2058:
2045:
1968:Zermelo–Fraenkel
1719:Set operations:
1654:
1653:
1591:
1422:
1421:
1402:Löwenheim–Skolem
1289:Formal semantics
1241:
1234:
1227:
1218:
1217:
1211:
1210:
1192:
1160:
1154:
1153:
1113:
1107:
1085:
1079:
1078:
1040:
1034:
1033:
1012:
1006:
1005:
981:
975:
974:
972:
970:
964:Shtetl-Optimized
955:
949:
948:
946:
945:
939:Oxford Reference
931:
925:
924:
922:
921:
907:
890:
888:
886:
885:
880:
878:
877:
848:
842:
831:
782:is undecidable.
679:proved that the
535:deductive system
446:
435:
310:
303:
299:
296:
290:
267:
259:
218:decision problem
135:decision problem
114:
107:
103:
100:
94:
92:
51:
27:
19:
3010:
3009:
3005:
3004:
3003:
3001:
3000:
2999:
2975:
2974:
2973:
2968:
2957:
2950:
2895:Category theory
2885:Algebraic logic
2868:
2839:Lambda calculus
2777:Church encoding
2763:
2739:Truth predicate
2595:
2561:Complete theory
2484:
2353:
2349:
2345:
2340:
2332:
2052: and
2048:
2043:
2029:
2005:New Foundations
1973:axiom of choice
1956:
1918:Gödel numbering
1858: and
1850:
1754:
1639:
1589:
1570:
1519:Boolean algebra
1505:
1469:Equiconsistency
1434:Classical logic
1411:
1392:Halting problem
1380: and
1356: and
1344: and
1343:
1338:Theorems (
1333:
1250:
1245:
1215:
1214:
1161:
1157:
1114:
1110:
1086:
1082:
1041:
1037:
1021:
1013:
1009:
982:
978:
968:
966:
956:
952:
943:
941:
933:
932:
928:
919:
917:
909:
908:
904:
899:
894:
893:
873:
869:
855:
852:
851:
849:
845:
832:
828:
823:
791:
780:Collatz problem
769:Berry's paradox
745:Gregory Chaitin
681:halting problem
622:axiom of choice
530:
520:
512:infinite length
492:
486:
444:
433:
390:halts on input
360:natural numbers
311:
300:
294:
291:
280:
268:
257:
214:halting problem
206:
171:Gödel numbering
167:natural numbers
160:formal language
151:
143:halting problem
115:
104:
98:
95:
52:
50:
40:
28:
17:
12:
11:
5:
3008:
2998:
2997:
2992:
2987:
2970:
2969:
2955:
2952:
2951:
2949:
2948:
2943:
2938:
2933:
2928:
2927:
2926:
2916:
2911:
2906:
2897:
2892:
2887:
2882:
2880:Abstract logic
2876:
2874:
2870:
2869:
2867:
2866:
2861:
2859:Turing machine
2856:
2851:
2846:
2841:
2836:
2831:
2830:
2829:
2824:
2819:
2814:
2809:
2799:
2797:Computable set
2794:
2789:
2784:
2779:
2773:
2771:
2765:
2764:
2762:
2761:
2756:
2751:
2746:
2741:
2736:
2731:
2726:
2725:
2724:
2719:
2714:
2704:
2699:
2694:
2692:Satisfiability
2689:
2684:
2679:
2678:
2677:
2667:
2666:
2665:
2655:
2654:
2653:
2648:
2643:
2638:
2633:
2623:
2622:
2621:
2616:
2609:Interpretation
2605:
2603:
2597:
2596:
2594:
2593:
2588:
2583:
2578:
2573:
2563:
2558:
2557:
2556:
2555:
2554:
2544:
2539:
2529:
2524:
2519:
2514:
2509:
2504:
2498:
2496:
2490:
2489:
2486:
2485:
2483:
2482:
2474:
2473:
2472:
2471:
2466:
2465:
2464:
2459:
2454:
2434:
2433:
2432:
2430:minimal axioms
2427:
2416:
2415:
2414:
2403:
2402:
2401:
2396:
2391:
2386:
2381:
2376:
2363:
2361:
2342:
2341:
2339:
2338:
2337:
2336:
2324:
2319:
2318:
2317:
2312:
2307:
2302:
2292:
2287:
2282:
2277:
2276:
2275:
2270:
2260:
2259:
2258:
2253:
2248:
2243:
2233:
2228:
2227:
2226:
2221:
2216:
2206:
2205:
2204:
2199:
2194:
2189:
2184:
2179:
2169:
2164:
2159:
2154:
2153:
2152:
2147:
2142:
2137:
2127:
2122:
2120:Formation rule
2117:
2112:
2111:
2110:
2105:
2095:
2094:
2093:
2083:
2078:
2073:
2068:
2062:
2056:
2039:Formal systems
2035:
2034:
2031:
2030:
2028:
2027:
2022:
2017:
2012:
2007:
2002:
1997:
1992:
1987:
1982:
1981:
1980:
1975:
1964:
1962:
1958:
1957:
1955:
1954:
1953:
1952:
1942:
1937:
1936:
1935:
1928:Large cardinal
1925:
1920:
1915:
1910:
1905:
1891:
1890:
1889:
1884:
1879:
1864:
1862:
1852:
1851:
1849:
1848:
1847:
1846:
1841:
1836:
1826:
1821:
1816:
1811:
1806:
1801:
1796:
1791:
1786:
1781:
1776:
1771:
1765:
1763:
1756:
1755:
1753:
1752:
1751:
1750:
1745:
1740:
1735:
1730:
1725:
1717:
1716:
1715:
1710:
1700:
1695:
1693:Extensionality
1690:
1688:Ordinal number
1685:
1675:
1670:
1669:
1668:
1657:
1651:
1645:
1644:
1641:
1640:
1638:
1637:
1632:
1627:
1622:
1617:
1612:
1607:
1606:
1605:
1595:
1594:
1593:
1580:
1578:
1572:
1571:
1569:
1568:
1567:
1566:
1561:
1556:
1546:
1541:
1536:
1531:
1526:
1521:
1515:
1513:
1507:
1506:
1504:
1503:
1498:
1493:
1488:
1483:
1478:
1473:
1472:
1471:
1461:
1456:
1451:
1446:
1441:
1436:
1430:
1428:
1419:
1413:
1412:
1410:
1409:
1404:
1399:
1394:
1389:
1384:
1372:Cantor's
1370:
1365:
1360:
1350:
1348:
1335:
1334:
1332:
1331:
1326:
1321:
1316:
1311:
1306:
1301:
1296:
1291:
1286:
1281:
1276:
1271:
1270:
1269:
1258:
1256:
1252:
1251:
1244:
1243:
1236:
1229:
1221:
1213:
1212:
1155:
1108:
1080:
1053:(3): 243–256.
1035:
1028:(in Russian).
1007:
993:(in Russian),
976:
950:
926:
901:
900:
898:
895:
892:
891:
876:
872:
868:
865:
862:
859:
843:
825:
824:
822:
819:
818:
817:
815:Wicked problem
812:
807:
802:
797:
790:
787:
715:Ramsey theorem
696:Saharon Shelah
689:Rice's theorem
685:Turing machine
652:; we seek the
519:
516:
488:Main article:
485:
482:
352:axiomatization
324:axiomatization
313:
312:
271:
269:
262:
256:
253:
241:Turing machine
230:
229:
205:
202:
150:
147:
117:
116:
31:
29:
22:
15:
9:
6:
4:
3:
2:
3007:
2996:
2993:
2991:
2988:
2986:
2983:
2982:
2980:
2967:
2966:
2961:
2953:
2947:
2944:
2942:
2939:
2937:
2934:
2932:
2929:
2925:
2922:
2921:
2920:
2917:
2915:
2912:
2910:
2907:
2905:
2901:
2898:
2896:
2893:
2891:
2888:
2886:
2883:
2881:
2878:
2877:
2875:
2871:
2865:
2862:
2860:
2857:
2855:
2854:Recursive set
2852:
2850:
2847:
2845:
2842:
2840:
2837:
2835:
2832:
2828:
2825:
2823:
2820:
2818:
2815:
2813:
2810:
2808:
2805:
2804:
2803:
2800:
2798:
2795:
2793:
2790:
2788:
2785:
2783:
2780:
2778:
2775:
2774:
2772:
2770:
2766:
2760:
2757:
2755:
2752:
2750:
2747:
2745:
2742:
2740:
2737:
2735:
2732:
2730:
2727:
2723:
2720:
2718:
2715:
2713:
2710:
2709:
2708:
2705:
2703:
2700:
2698:
2695:
2693:
2690:
2688:
2685:
2683:
2680:
2676:
2673:
2672:
2671:
2668:
2664:
2663:of arithmetic
2661:
2660:
2659:
2656:
2652:
2649:
2647:
2644:
2642:
2639:
2637:
2634:
2632:
2629:
2628:
2627:
2624:
2620:
2617:
2615:
2612:
2611:
2610:
2607:
2606:
2604:
2602:
2598:
2592:
2589:
2587:
2584:
2582:
2579:
2577:
2574:
2571:
2570:from ZFC
2567:
2564:
2562:
2559:
2553:
2550:
2549:
2548:
2545:
2543:
2540:
2538:
2535:
2534:
2533:
2530:
2528:
2525:
2523:
2520:
2518:
2515:
2513:
2510:
2508:
2505:
2503:
2500:
2499:
2497:
2495:
2491:
2481:
2480:
2476:
2475:
2470:
2469:non-Euclidean
2467:
2463:
2460:
2458:
2455:
2453:
2452:
2448:
2447:
2445:
2442:
2441:
2439:
2435:
2431:
2428:
2426:
2423:
2422:
2421:
2417:
2413:
2410:
2409:
2408:
2404:
2400:
2397:
2395:
2392:
2390:
2387:
2385:
2382:
2380:
2377:
2375:
2372:
2371:
2369:
2365:
2364:
2362:
2357:
2351:
2346:Example
2343:
2335:
2330:
2329:
2328:
2325:
2323:
2320:
2316:
2313:
2311:
2308:
2306:
2303:
2301:
2298:
2297:
2296:
2293:
2291:
2288:
2286:
2283:
2281:
2278:
2274:
2271:
2269:
2266:
2265:
2264:
2261:
2257:
2254:
2252:
2249:
2247:
2244:
2242:
2239:
2238:
2237:
2234:
2232:
2229:
2225:
2222:
2220:
2217:
2215:
2212:
2211:
2210:
2207:
2203:
2200:
2198:
2195:
2193:
2190:
2188:
2185:
2183:
2180:
2178:
2175:
2174:
2173:
2170:
2168:
2165:
2163:
2160:
2158:
2155:
2151:
2148:
2146:
2143:
2141:
2138:
2136:
2133:
2132:
2131:
2128:
2126:
2123:
2121:
2118:
2116:
2113:
2109:
2106:
2104:
2103:by definition
2101:
2100:
2099:
2096:
2092:
2089:
2088:
2087:
2084:
2082:
2079:
2077:
2074:
2072:
2069:
2067:
2064:
2063:
2060:
2057:
2055:
2051:
2046:
2040:
2036:
2026:
2023:
2021:
2018:
2016:
2013:
2011:
2008:
2006:
2003:
2001:
1998:
1996:
1993:
1991:
1990:Kripke–Platek
1988:
1986:
1983:
1979:
1976:
1974:
1971:
1970:
1969:
1966:
1965:
1963:
1959:
1951:
1948:
1947:
1946:
1943:
1941:
1938:
1934:
1931:
1930:
1929:
1926:
1924:
1921:
1919:
1916:
1914:
1911:
1909:
1906:
1903:
1899:
1895:
1892:
1888:
1885:
1883:
1880:
1878:
1875:
1874:
1873:
1869:
1866:
1865:
1863:
1861:
1857:
1853:
1845:
1842:
1840:
1837:
1835:
1834:constructible
1832:
1831:
1830:
1827:
1825:
1822:
1820:
1817:
1815:
1812:
1810:
1807:
1805:
1802:
1800:
1797:
1795:
1792:
1790:
1787:
1785:
1782:
1780:
1777:
1775:
1772:
1770:
1767:
1766:
1764:
1762:
1757:
1749:
1746:
1744:
1741:
1739:
1736:
1734:
1731:
1729:
1726:
1724:
1721:
1720:
1718:
1714:
1711:
1709:
1706:
1705:
1704:
1701:
1699:
1696:
1694:
1691:
1689:
1686:
1684:
1680:
1676:
1674:
1671:
1667:
1664:
1663:
1662:
1659:
1658:
1655:
1652:
1650:
1646:
1636:
1633:
1631:
1628:
1626:
1623:
1621:
1618:
1616:
1613:
1611:
1608:
1604:
1601:
1600:
1599:
1596:
1592:
1587:
1586:
1585:
1582:
1581:
1579:
1577:
1573:
1565:
1562:
1560:
1557:
1555:
1552:
1551:
1550:
1547:
1545:
1542:
1540:
1537:
1535:
1532:
1530:
1527:
1525:
1522:
1520:
1517:
1516:
1514:
1512:
1511:Propositional
1508:
1502:
1499:
1497:
1494:
1492:
1489:
1487:
1484:
1482:
1479:
1477:
1474:
1470:
1467:
1466:
1465:
1462:
1460:
1457:
1455:
1452:
1450:
1447:
1445:
1442:
1440:
1439:Logical truth
1437:
1435:
1432:
1431:
1429:
1427:
1423:
1420:
1418:
1414:
1408:
1405:
1403:
1400:
1398:
1395:
1393:
1390:
1388:
1385:
1383:
1379:
1375:
1371:
1369:
1366:
1364:
1361:
1359:
1355:
1352:
1351:
1349:
1347:
1341:
1336:
1330:
1327:
1325:
1322:
1320:
1317:
1315:
1312:
1310:
1307:
1305:
1302:
1300:
1297:
1295:
1292:
1290:
1287:
1285:
1282:
1280:
1277:
1275:
1272:
1268:
1265:
1264:
1263:
1260:
1259:
1257:
1253:
1249:
1242:
1237:
1235:
1230:
1228:
1223:
1222:
1219:
1208:
1204:
1200:
1196:
1191:
1186:
1182:
1178:
1174:
1170:
1166:
1159:
1151:
1147:
1143:
1139:
1135:
1131:
1127:
1123:
1119:
1112:
1106:
1102:
1098:
1097:3-540-72503-2
1094:
1090:
1084:
1076:
1072:
1068:
1064:
1060:
1056:
1052:
1048:
1047:
1039:
1031:
1027:
1026:
1017:
1011:
1004:
1000:
996:
992:
991:
986:
980:
965:
961:
954:
940:
936:
930:
916:
912:
906:
902:
874:
866:
863:
860:
847:
840:
836:
830:
826:
816:
813:
811:
810:Unknowability
808:
806:
803:
801:
798:
796:
793:
792:
786:
783:
781:
777:
772:
770:
766:
762:
759:greater than
758:
754:
750:
746:
742:
740:
739:Ramsey theory
736:
732:
730:
726:
724:
720:
716:
712:
707:
705:
701:
697:
692:
690:
686:
682:
678:
673:
671:
667:
666:complex plane
663:
659:
655:
654:integer roots
651:
647:
643:
639:
634:
631:
627:
623:
619:
615:
611:
607:
602:
600:
596:
592:
587:
585:
580:
575:
572:
567:
565:
561:
557:
553:
552:formal system
548:
544:
540:
536:
529:
525:
515:
513:
509:
505:
501:
497:
491:
481:
479:
475:
471:
467:
463:
460:). So if we
459:
455:
451:
447:
440:
436:
429:
425:
421:
417:
413:
409:
405:
401:
397:
393:
389:
385:
381:
377:
373:
369:
365:
361:
357:
353:
348:
346:
341:
337:
333:
329:
325:
320:
309:
306:
298:
288:
284:
278:
277:
272:This section
270:
266:
261:
260:
252:
250:
246:
242:
239:running on a
238:
234:
227:
223:
222:
221:
219:
215:
211:
201:
199:
195:
191:
188:. Otherwise,
187:
186:recursive set
183:
179:
174:
172:
168:
163:
161:
157:
146:
144:
140:
136:
132:
128:
124:
113:
110:
102:
91:
88:
84:
81:
77:
74:
70:
67:
63:
60: –
59:
55:
54:Find sources:
48:
44:
38:
37:
32:This article
30:
26:
21:
20:
2956:
2811:
2754:Ultraproduct
2601:Model theory
2566:Independence
2502:Formal proof
2494:Proof theory
2477:
2450:
2407:real numbers
2379:second-order
2290:Substitution
2167:Metalanguage
2108:conservative
2081:Axiom schema
2025:Constructive
1995:Morse–Kelley
1961:Set theories
1940:Aleph number
1933:inaccessible
1839:Grothendieck
1723:intersection
1610:Higher-order
1598:Second-order
1544:Truth tables
1501:Venn diagram
1284:Formal proof
1172:
1168:
1158:
1128:(1): 44–48.
1125:
1121:
1111:
1083:
1050:
1044:
1038:
1029:
1023:
1010:
994:
988:
979:
967:. Retrieved
963:
953:
942:. Retrieved
938:
929:
918:. Retrieved
914:
905:
846:
838:
834:
829:
784:
773:
765:liar paradox
760:
752:
743:
733:
727:
719:Peano axioms
708:
704:group theory
693:
674:
661:
640:showed that
635:
629:
603:
588:
576:
568:
563:
559:
555:
531:
493:
477:
473:
469:
465:
457:
453:
449:
442:
438:
431:
427:
423:
419:
415:
411:
407:
403:
399:
395:
391:
387:
383:
379:
375:
371:
367:
363:
354:of all true
349:
331:
316:
301:
292:
281:Please help
276:verification
273:
248:
244:
231:
207:
193:
189:
181:
177:
175:
164:
152:
130:
120:
105:
96:
86:
79:
72:
65:
53:
41:Please help
36:verification
33:
2864:Type theory
2812:undecidable
2744:Truth value
2631:equivalence
2310:non-logical
1923:Enumeration
1913:Isomorphism
1860:cardinality
1844:Von Neumann
1809:Ultrafilter
1774:Uncountable
1708:equivalence
1625:Quantifiers
1615:Fixed-point
1584:First-order
1464:Consistency
1449:Proposition
1426:Traditional
1397:Lindström's
1387:Compactness
1329:Type theory
1274:Cardinality
776:J.H. Conway
698:showed the
677:Alan Turing
620:), and the
579:truth value
571:independent
508:uncountably
336:consistency
295:August 2019
249:undecidable
233:Alan Turing
2979:Categories
2675:elementary
2368:arithmetic
2236:Quantifier
2214:functional
2086:Expression
1804:Transitive
1748:identities
1733:complement
1666:hereditary
1649:Set theory
1032:: 279–282.
1003:0068.01301
969:2 November
944:2022-06-12
920:2022-06-12
897:References
658:polynomial
618:set theory
606:Paul Cohen
522:See also:
437:such that
410:such that
378:such that
149:Background
69:newspapers
2946:Supertask
2849:Recursion
2807:decidable
2641:saturated
2619:of models
2542:deductive
2537:axiomatic
2457:Hilbert's
2444:Euclidean
2425:canonical
2348:axiomatic
2280:Signature
2209:Predicate
2098:Extension
2020:Ackermann
1945:Operation
1824:Universal
1814:Recursive
1789:Singleton
1784:Inhabited
1769:Countable
1759:Types of
1743:power set
1713:partition
1630:Predicate
1576:Predicate
1491:Syllogism
1481:Soundness
1454:Inference
1444:Tautology
1346:paradoxes
1199:0028-0836
1150:257109887
1142:2522-5839
1075:123351674
1018:(1970).
997:: 1–143,
875:∗
694:In 1973,
675:In 1936,
464:over all
340:corollary
237:algorithm
139:algorithm
99:July 2019
2931:Logicism
2924:timeline
2900:Concrete
2759:Validity
2729:T-schema
2722:Kripke's
2717:Tarski's
2712:semantic
2702:Strength
2651:submodel
2646:spectrum
2614:function
2462:Tarski's
2451:Elements
2438:geometry
2394:Robinson
2315:variable
2300:function
2273:spectrum
2263:Sentence
2219:variable
2162:Language
2115:Relation
2076:Automata
2066:Alphabet
2050:language
1904:-jection
1882:codomain
1868:Function
1829:Universe
1799:Infinite
1703:Relation
1486:Validity
1476:Argument
1374:theorem,
1207:30617250
789:See also
595:Max Dehn
566:is no".
504:topology
2873:Related
2670:Diagram
2568: (
2547:Hilbert
2532:Systems
2527:Theorem
2405:of the
2350:systems
2130:Formula
2125:Grammar
2041: (
1985:General
1698:Forcing
1683:Element
1603:Monadic
1378:paradox
1319:Theorem
1255:General
1177:Bibcode
1067:0357114
462:iterate
226:program
156:strings
83:scholar
2636:finite
2399:Skolem
2352:
2327:Theory
2295:Symbol
2285:String
2268:atomic
2145:ground
2140:closed
2135:atomic
2091:ground
2054:syntax
1950:binary
1877:domain
1794:Finite
1559:finite
1417:Logics
1376:
1324:Theory
1205:
1197:
1169:Nature
1148:
1140:
1095:
1073:
1065:
1001:
630:except
448:) = ¬
212:, the
85:
78:
71:
64:
56:
2626:Model
2374:Peano
2231:Proof
2071:Arity
2000:Naive
1887:image
1819:Fuzzy
1779:Empty
1728:union
1673:Class
1314:Model
1304:Lemma
1262:Axiom
1146:S2CID
1071:S2CID
821:Notes
656:of a
599:group
496:logic
418:) =
328:sound
216:is a
196:is a
184:is a
158:of a
133:is a
129:, an
90:JSTOR
76:books
2749:Type
2552:list
2356:list
2333:list
2322:Term
2256:rank
2150:open
2044:list
1856:Maps
1761:sets
1620:Free
1590:list
1340:list
1267:list
1203:PMID
1195:ISSN
1138:ISSN
1093:ISBN
971:2022
526:and
332:true
125:and
62:news
2436:of
2418:of
2366:of
1898:Sur
1872:Map
1679:Ur-
1661:Set
1185:doi
1173:565
1130:doi
1101:doi
1055:doi
1030:191
999:Zbl
835:yes
702:in
614:ZFC
502:or
285:by
245:all
208:In
162:.
121:In
45:by
2981::
2822:NP
2446::
2440::
2370::
2047:),
1902:Bi
1894:In
1201:.
1193:.
1183:.
1171:.
1167:.
1144:.
1136:.
1124:.
1120:.
1099:.
1069:.
1063:MR
1061:.
1051:18
1049:.
995:44
962:.
937:.
913:.
839:no
771:.
725:.
691:.
626:ZF
586:.
498:,
476:,
456:,
426:,
402:,
347:.
200:.
2902:/
2817:P
2572:)
2358:)
2354:(
2251:∀
2246:!
2241:∃
2202:=
2197:↔
2192:→
2187:∧
2182:∨
2177:¬
1900:/
1896:/
1870:/
1681:)
1677:(
1564:∞
1554:3
1342:)
1240:e
1233:t
1226:v
1209:.
1187::
1179::
1152:.
1132::
1126:1
1103::
1077:.
1057::
973:.
947:.
923:.
871:}
867:1
864:,
861:0
858:{
841:.
761:c
753:c
662:n
564:A
560:A
556:A
478:i
474:a
472:(
470:H
466:n
458:i
454:a
452:(
450:H
445:′
443:n
441:(
439:N
434:′
432:n
428:i
424:a
422:(
420:H
416:n
414:(
412:N
408:n
404:i
400:a
398:(
396:H
392:i
388:a
384:n
382:(
380:N
376:n
372:n
368:n
366:(
364:N
308:)
302:(
297:)
293:(
279:.
194:A
190:A
182:A
178:A
112:)
106:(
101:)
97:(
87:·
80:·
73:·
66:·
39:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
