2509:
31:
451:.) If this decision problem were effectively solvable then the function problem would be as well. This reduction does not respect computational complexity, however. For example, it is possible for the graph of a function to be decidable in polynomial time (in which case running time is computed as a function of the pair (
482:
of the set associated to the decision problem. If this function is computable then the associated decision problem is decidable. However, this reduction is more liberal than the standard reduction used in computational complexity (sometimes called polynomial-time many-one reduction); for example,
531:
a given value. This allows the complexity of the corresponding decision problem to be studied; and in many cases the original function or optimization problem can be solved by solving its corresponding decision problem. For example, in the traveling salesman problem, the optimization problem is to
543:
Because the theory of decision problems is very well developed, research in complexity theory has typically focused on decision problems. Optimization problems themselves are still of interest in computability theory, as well as in fields such as
234:
A classic example of a decidable decision problem is the set of prime numbers. It is possible to effectively decide whether a given natural number is prime by testing every possible nontrivial factor. Although much more efficient methods of
222:, any string can be encoded as a natural number, via which a decision problem can be defined as a subset of the natural numbers. Therefore, the algorithm of a decision problem is to compute the
427:
Every function problem can be turned into a decision problem; the decision problem is just the graph of the associated function. (The graph of a function
888:
196:
of inputs. It is traditional to define the decision problem as the set of possible inputs together with the set of inputs for which the answer is
1563:
1646:
787:
508:
Unlike decision problems, for which there is only one correct answer for each input, optimization problems are concerned with finding the
752:
494:
is exactly the same even though the underlying decision problems may not be considered equivalent in some typical models of computation.
138:. If the remainder is zero the answer is 'yes', otherwise it is 'no'. A decision problem which can be solved by an algorithm is called
523:
Function and optimization problems are often transformed into decision problems by considering the question of whether the output is
390:, which can have answers that are more complex than a simple 'yes' or 'no'. A corresponding function problem is "given two numbers
1960:
2118:
726:
701:
652:
630:
611:
153:
to determine the existence of some object or its membership in a set; some of the most important problems in mathematics are
906:
1973:
1296:
1978:
1968:
1705:
1558:
911:
902:
2114:
673:
1456:
2211:
1955:
780:
2533:
1516:
1209:
357:
55:
950:
2472:
2174:
1937:
1932:
1757:
1178:
862:
365:
164:
decision problems by how difficult they are to solve. "Difficult", in this sense, is described in terms of the
601:
2538:
2467:
2250:
2167:
1880:
1811:
1688:
930:
582:
19:
This article is about decision problems in complexity theory. For the decision problem in formal logic, see
2392:
2218:
1904:
1538:
1137:
301:
2270:
2265:
1875:
1614:
1543:
872:
773:
208:
2199:
1789:
1183:
1151:
842:
587:
513:
512:
answer to a particular input. Optimization problems arise naturally in many applications, such as the
286:
540:. By repeatedly answering the decision problem, it is possible to find the minimal weight of a tour.
2489:
2438:
2335:
1833:
1794:
1271:
916:
323:
204:
945:
2330:
2260:
1799:
1651:
1634:
1357:
837:
2162:
2139:
2100:
1986:
1927:
1573:
1493:
1337:
1281:
894:
491:
293:. For those it is not possible to create an algorithm, efficient or otherwise, that solves them.
2452:
2179:
2157:
2124:
2017:
1863:
1848:
1821:
1772:
1656:
1591:
1416:
1382:
1377:
1251:
1082:
1059:
745:
165:
2382:
2235:
2027:
1745:
1481:
1387:
1246:
1231:
1112:
1087:
562:
63:
716:
691:
663:
203:
These inputs can be natural numbers, but can also be values of some other kind, like binary
2355:
2317:
2194:
1998:
1838:
1762:
1740:
1568:
1526:
1425:
1392:
1256:
1044:
955:
567:
503:
252:
146:
51:
20:
8:
2484:
2375:
2360:
2340:
2297:
2184:
2134:
2060:
2005:
1942:
1735:
1730:
1678:
1446:
1435:
1107:
1007:
935:
926:
922:
857:
852:
545:
248:
154:
67:
2513:
2282:
2245:
2230:
2223:
2206:
2010:
1992:
1858:
1784:
1767:
1720:
1533:
1442:
1276:
1261:
1221:
1173:
1158:
1146:
1102:
1077:
847:
796:
517:
479:
319:
223:
1466:
239:
are known, the existence of any effective method is enough to establish decidability.
219:
2508:
2448:
2255:
2065:
2055:
1947:
1828:
1663:
1639:
1420:
1404:
1309:
1286:
1163:
1132:
1097:
992:
827:
722:
697:
669:
648:
626:
607:
236:
2462:
2457:
2307:
2129:
2090:
2085:
2070:
1896:
1853:
1750:
1548:
1498:
1072:
1034:
557:
478:
Every decision problem can be converted into the function problem of computing the
414:
410:
387:
381:
361:
332:
313:
169:
150:
110:
for that problem. A decision procedure for the decision problem "given two numbers
2443:
2433:
2387:
2370:
2325:
2287:
2189:
2109:
1916:
1843:
1816:
1804:
1710:
1624:
1598:
1553:
1521:
1322:
1124:
1067:
1017:
982:
940:
683:
532:
produce a tour with minimal weight. The associated decision problem is: for each
460:
369:
297:
212:
70:
of the input values. An example of a decision problem is deciding by means of an
24:
2428:
2407:
2365:
2345:
2240:
2095:
1693:
1683:
1673:
1668:
1602:
1476:
1352:
1241:
1236:
1214:
815:
687:
640:
577:
571:
488:
2527:
2402:
2080:
1587:
1372:
1362:
1332:
1317:
987:
266:
177:
135:
570:– for the problem of deciding whether a formula is a consequence of a
2302:
2149:
2050:
2042:
1922:
1870:
1779:
1715:
1698:
1629:
1488:
1347:
1049:
832:
285:
if the set of inputs (or natural numbers) for which the answer is yes is a
265:
if the set of inputs (or natural numbers) for which the answer is yes is a
193:
168:
needed by the most efficient algorithm for a certain problem. The field of
75:
2412:
2292:
1471:
1461:
1408:
1092:
1012:
997:
877:
822:
712:
484:
1342:
1197:
1168:
974:
180:, which is a measure of the noncomputability inherent in any solution.
2494:
2397:
1450:
1367:
1327:
1291:
1227:
1039:
1029:
1002:
765:
300:
is an important undecidable decision problem; for more examples, see
103:
94:?". The answer is either 'yes' or 'no' depending upon the values of
71:
2479:
2277:
1725:
1430:
1024:
102:. A method for solving a decision problem, given in the form of an
30:
2075:
867:
536:, to decide whether the graph has any tour with weight less than
211:. The subset of strings for which the problem returns "yes" is a
145:
Decision problems typically appear in mathematical questions of
215:, and often decision problems are defined as formal languages.
1619:
965:
810:
623:
The Theory of
Recursive Functions and Effective Computability
463:(in which case running time is computed as a function of
372:
of decision problems under polynomial-time reducibility.
483:
the complexity of the characteristic functions of an
420:; the informal "problem" is to compute the values of
23:. For analysis of the process of making choices, see
160:The field of computational complexity categorizes
682:
2525:
126:?" would give the steps for determining whether
149:, that is, the question of the existence of an
318:Decision problems can be ordered according to
781:
746:"CS254: Computational Complexity: Lecture 2"
710:
78:. Another is the problem "given two numbers
322:and related to feasible reductions such as
973:
788:
774:
459:)) when the function is not computable in
645:Introduction to the Theory of Computation
386:Decision problems are closely related to
356:. Complete decision problems are used in
497:
29:
665:Recursively Enumerable Sets and Degrees
620:
424:on the inputs for which it is defined.
364:of decision problems. For example, the
2526:
795:
639:
289:. Problems that are not decidable are
769:
661:
599:
375:
307:
226:of a subset of the natural numbers.
13:
74:whether a given natural number is
16:Yes/no problem in computer science
14:
2550:
2507:
758:from the original on 2015-10-10.
358:computational complexity theory
336:for a set of decision problems
242:
56:computational complexity theory
38:has only two possible outputs (
738:
366:Boolean satisfiability problem
192:is a yes-or-no question on an
1:
2468:History of mathematical logic
593:
583:Counting problem (complexity)
183:
2393:Primitive recursive function
302:list of undecidable problems
7:
718:The calculus of computation
621:Hartley, Rogers Jr (1987).
551:
229:
207:or strings over some other
10:
2555:
1457:SchröderâBernstein theorem
1184:Monadic predicate calculus
843:Foundations of mathematics
603:Automata and Computability
588:Word problem (mathematics)
514:traveling salesman problem
501:
379:
368:is complete for the class
324:polynomial-time reductions
311:
287:recursively enumerable set
246:
218:Using an encoding such as
18:
2503:
2490:Philosophy of mathematics
2439:Automated theorem proving
2421:
2316:
2148:
2041:
1893:
1610:
1586:
1564:Von NeumannâBernaysâGödel
1509:
1403:
1307:
1205:
1196:
1123:
1058:
964:
886:
803:
662:Soare, Robert I. (1987).
475:) = 2 has this property.
172:, meanwhile, categorizes
134:. One such algorithm is
2140:Self-verifying theories
1961:Tarski's axiomatization
912:Tarski's undefinability
907:incompleteness theorems
480:characteristic function
224:characteristic function
166:computational resources
66:that can be posed as a
2534:Computational problems
2514:Mathematics portal
2125:Proof of impossibility
1773:propositional variable
1083:Propositional calculus
516:and many questions in
467:alone). The function
257:A decision problem is
47:
2383:Kolmogorov complexity
2336:Computably enumerable
2236:Model complete theory
2028:Principia Mathematica
1088:Propositional formula
917:BanachâTarski paradox
563:Computational problem
529:less than or equal to
498:Optimization problems
431:is the set of pairs (
348:and every problem in
326:. A decision problem
320:many-one reducibility
176:decision problems by
64:computational problem
33:
2539:Computability theory
2331:ChurchâTuring thesis
2318:Computability theory
1527:continuum hypothesis
1045:Square of opposition
903:Gödel's completeness
715:(3 September 2007).
647:. Cengage Learning.
600:Kozen, D.C. (2012).
568:Decidability (logic)
504:Optimization problem
263:effectively solvable
253:Decidability (logic)
52:computability theory
21:Entscheidungsproblem
2485:Mathematical object
2376:P versus NP problem
2341:Computable function
2135:Reverse mathematics
2061:Logical consequence
1938:primitive recursive
1933:elementary function
1706:Free/bound variable
1559:TarskiâGrothendieck
1078:Logical connectives
1008:Logical equivalence
858:Logical consequence
693:Decision procedures
546:operations research
271:partially decidable
249:Undecidable problem
2283:Transfer principle
2246:Semantics of logic
2231:Categorical theory
2207:Non-standard model
1721:Logical connective
848:Information theory
797:Mathematical logic
518:linear programming
362:complexity classes
352:can be reduced to
108:decision procedure
48:
2521:
2520:
2453:Abstract category
2256:Theories of truth
2066:Rule of inference
2056:Natural deduction
2037:
2036:
1582:
1581:
1287:Cartesian product
1192:
1191:
1098:Many-valued logic
1073:Boolean functions
956:Russell's paradox
931:diagonal argument
828:First-order logic
728:978-3-540-74112-1
703:978-3-540-74104-6
654:978-0-357-67058-3
632:978-0-262-68052-3
613:978-1-4612-1844-9
388:function problems
376:Function problems
308:Complete problems
237:primality testing
2546:
2512:
2511:
2463:History of logic
2458:Category of sets
2351:Decision problem
2130:Ordinal analysis
2071:Sequent calculus
1969:Boolean algebras
1909:
1908:
1883:
1854:logical/constant
1608:
1607:
1594:
1517:ZermeloâFraenkel
1268:Set operations:
1203:
1202:
1140:
971:
970:
951:LöwenheimâSkolem
838:Formal semantics
790:
783:
776:
767:
766:
760:
759:
757:
750:
742:
732:
711:Bradley, Aaron;
707:
684:Kroening, Daniel
679:
658:
636:
617:
558:ALL (complexity)
487:problem and its
415:partial function
411:function problem
382:Function problem
360:to characterize
314:Complete problem
190:decision problem
170:recursion theory
151:effective method
60:decision problem
36:decision problem
2554:
2553:
2549:
2548:
2547:
2545:
2544:
2543:
2524:
2523:
2522:
2517:
2506:
2499:
2444:Category theory
2434:Algebraic logic
2417:
2388:Lambda calculus
2326:Church encoding
2312:
2288:Truth predicate
2144:
2110:Complete theory
2033:
1902:
1898:
1894:
1889:
1881:
1601: and
1597:
1592:
1578:
1554:New Foundations
1522:axiom of choice
1505:
1467:Gödel numbering
1407: and
1399:
1303:
1188:
1138:
1119:
1068:Boolean algebra
1054:
1018:Equiconsistency
983:Classical logic
960:
941:Halting problem
929: and
905: and
893: and
892:
887:Theorems (
882:
799:
794:
764:
763:
755:
748:
744:
743:
739:
729:
704:
690:(23 May 2008).
688:Strichman, Ofer
676:
655:
633:
614:
596:
554:
506:
500:
461:polynomial time
384:
378:
344:is a member of
316:
310:
298:halting problem
269:. A problem is
255:
247:Main articles:
245:
232:
220:Gödel numbering
213:formal language
186:
130:evenly divides
68:yesâno question
46:) on any input.
28:
25:Decision theory
17:
12:
11:
5:
2552:
2542:
2541:
2536:
2519:
2518:
2504:
2501:
2500:
2498:
2497:
2492:
2487:
2482:
2477:
2476:
2475:
2465:
2460:
2455:
2446:
2441:
2436:
2431:
2429:Abstract logic
2425:
2423:
2419:
2418:
2416:
2415:
2410:
2408:Turing machine
2405:
2400:
2395:
2390:
2385:
2380:
2379:
2378:
2373:
2368:
2363:
2358:
2348:
2346:Computable set
2343:
2338:
2333:
2328:
2322:
2320:
2314:
2313:
2311:
2310:
2305:
2300:
2295:
2290:
2285:
2280:
2275:
2274:
2273:
2268:
2263:
2253:
2248:
2243:
2241:Satisfiability
2238:
2233:
2228:
2227:
2226:
2216:
2215:
2214:
2204:
2203:
2202:
2197:
2192:
2187:
2182:
2172:
2171:
2170:
2165:
2158:Interpretation
2154:
2152:
2146:
2145:
2143:
2142:
2137:
2132:
2127:
2122:
2112:
2107:
2106:
2105:
2104:
2103:
2093:
2088:
2078:
2073:
2068:
2063:
2058:
2053:
2047:
2045:
2039:
2038:
2035:
2034:
2032:
2031:
2023:
2022:
2021:
2020:
2015:
2014:
2013:
2008:
2003:
1983:
1982:
1981:
1979:minimal axioms
1976:
1965:
1964:
1963:
1952:
1951:
1950:
1945:
1940:
1935:
1930:
1925:
1912:
1910:
1891:
1890:
1888:
1887:
1886:
1885:
1873:
1868:
1867:
1866:
1861:
1856:
1851:
1841:
1836:
1831:
1826:
1825:
1824:
1819:
1809:
1808:
1807:
1802:
1797:
1792:
1782:
1777:
1776:
1775:
1770:
1765:
1755:
1754:
1753:
1748:
1743:
1738:
1733:
1728:
1718:
1713:
1708:
1703:
1702:
1701:
1696:
1691:
1686:
1676:
1671:
1669:Formation rule
1666:
1661:
1660:
1659:
1654:
1644:
1643:
1642:
1632:
1627:
1622:
1617:
1611:
1605:
1588:Formal systems
1584:
1583:
1580:
1579:
1577:
1576:
1571:
1566:
1561:
1556:
1551:
1546:
1541:
1536:
1531:
1530:
1529:
1524:
1513:
1511:
1507:
1506:
1504:
1503:
1502:
1501:
1491:
1486:
1485:
1484:
1477:Large cardinal
1474:
1469:
1464:
1459:
1454:
1440:
1439:
1438:
1433:
1428:
1413:
1411:
1401:
1400:
1398:
1397:
1396:
1395:
1390:
1385:
1375:
1370:
1365:
1360:
1355:
1350:
1345:
1340:
1335:
1330:
1325:
1320:
1314:
1312:
1305:
1304:
1302:
1301:
1300:
1299:
1294:
1289:
1284:
1279:
1274:
1266:
1265:
1264:
1259:
1249:
1244:
1242:Extensionality
1239:
1237:Ordinal number
1234:
1224:
1219:
1218:
1217:
1206:
1200:
1194:
1193:
1190:
1189:
1187:
1186:
1181:
1176:
1171:
1166:
1161:
1156:
1155:
1154:
1144:
1143:
1142:
1129:
1127:
1121:
1120:
1118:
1117:
1116:
1115:
1110:
1105:
1095:
1090:
1085:
1080:
1075:
1070:
1064:
1062:
1056:
1055:
1053:
1052:
1047:
1042:
1037:
1032:
1027:
1022:
1021:
1020:
1010:
1005:
1000:
995:
990:
985:
979:
977:
968:
962:
961:
959:
958:
953:
948:
943:
938:
933:
921:Cantor's
919:
914:
909:
899:
897:
884:
883:
881:
880:
875:
870:
865:
860:
855:
850:
845:
840:
835:
830:
825:
820:
819:
818:
807:
805:
801:
800:
793:
792:
785:
778:
770:
762:
761:
736:
735:
734:
733:
727:
708:
702:
680:
674:
659:
653:
637:
631:
618:
612:
595:
592:
591:
590:
585:
580:
578:Search problem
575:
572:logical theory
565:
560:
553:
550:
502:Main article:
499:
496:
489:co-NP-complete
413:consists of a
380:Main article:
377:
374:
330:is said to be
312:Main article:
309:
306:
244:
241:
231:
228:
185:
182:
122:evenly divide
106:, is called a
90:evenly divide
15:
9:
6:
4:
3:
2:
2551:
2540:
2537:
2535:
2532:
2531:
2529:
2516:
2515:
2510:
2502:
2496:
2493:
2491:
2488:
2486:
2483:
2481:
2478:
2474:
2471:
2470:
2469:
2466:
2464:
2461:
2459:
2456:
2454:
2450:
2447:
2445:
2442:
2440:
2437:
2435:
2432:
2430:
2427:
2426:
2424:
2420:
2414:
2411:
2409:
2406:
2404:
2403:Recursive set
2401:
2399:
2396:
2394:
2391:
2389:
2386:
2384:
2381:
2377:
2374:
2372:
2369:
2367:
2364:
2362:
2359:
2357:
2354:
2353:
2352:
2349:
2347:
2344:
2342:
2339:
2337:
2334:
2332:
2329:
2327:
2324:
2323:
2321:
2319:
2315:
2309:
2306:
2304:
2301:
2299:
2296:
2294:
2291:
2289:
2286:
2284:
2281:
2279:
2276:
2272:
2269:
2267:
2264:
2262:
2259:
2258:
2257:
2254:
2252:
2249:
2247:
2244:
2242:
2239:
2237:
2234:
2232:
2229:
2225:
2222:
2221:
2220:
2217:
2213:
2212:of arithmetic
2210:
2209:
2208:
2205:
2201:
2198:
2196:
2193:
2191:
2188:
2186:
2183:
2181:
2178:
2177:
2176:
2173:
2169:
2166:
2164:
2161:
2160:
2159:
2156:
2155:
2153:
2151:
2147:
2141:
2138:
2136:
2133:
2131:
2128:
2126:
2123:
2120:
2119:from ZFC
2116:
2113:
2111:
2108:
2102:
2099:
2098:
2097:
2094:
2092:
2089:
2087:
2084:
2083:
2082:
2079:
2077:
2074:
2072:
2069:
2067:
2064:
2062:
2059:
2057:
2054:
2052:
2049:
2048:
2046:
2044:
2040:
2030:
2029:
2025:
2024:
2019:
2018:non-Euclidean
2016:
2012:
2009:
2007:
2004:
2002:
2001:
1997:
1996:
1994:
1991:
1990:
1988:
1984:
1980:
1977:
1975:
1972:
1971:
1970:
1966:
1962:
1959:
1958:
1957:
1953:
1949:
1946:
1944:
1941:
1939:
1936:
1934:
1931:
1929:
1926:
1924:
1921:
1920:
1918:
1914:
1913:
1911:
1906:
1900:
1895:Example
1892:
1884:
1879:
1878:
1877:
1874:
1872:
1869:
1865:
1862:
1860:
1857:
1855:
1852:
1850:
1847:
1846:
1845:
1842:
1840:
1837:
1835:
1832:
1830:
1827:
1823:
1820:
1818:
1815:
1814:
1813:
1810:
1806:
1803:
1801:
1798:
1796:
1793:
1791:
1788:
1787:
1786:
1783:
1781:
1778:
1774:
1771:
1769:
1766:
1764:
1761:
1760:
1759:
1756:
1752:
1749:
1747:
1744:
1742:
1739:
1737:
1734:
1732:
1729:
1727:
1724:
1723:
1722:
1719:
1717:
1714:
1712:
1709:
1707:
1704:
1700:
1697:
1695:
1692:
1690:
1687:
1685:
1682:
1681:
1680:
1677:
1675:
1672:
1670:
1667:
1665:
1662:
1658:
1655:
1653:
1652:by definition
1650:
1649:
1648:
1645:
1641:
1638:
1637:
1636:
1633:
1631:
1628:
1626:
1623:
1621:
1618:
1616:
1613:
1612:
1609:
1606:
1604:
1600:
1595:
1589:
1585:
1575:
1572:
1570:
1567:
1565:
1562:
1560:
1557:
1555:
1552:
1550:
1547:
1545:
1542:
1540:
1539:KripkeâPlatek
1537:
1535:
1532:
1528:
1525:
1523:
1520:
1519:
1518:
1515:
1514:
1512:
1508:
1500:
1497:
1496:
1495:
1492:
1490:
1487:
1483:
1480:
1479:
1478:
1475:
1473:
1470:
1468:
1465:
1463:
1460:
1458:
1455:
1452:
1448:
1444:
1441:
1437:
1434:
1432:
1429:
1427:
1424:
1423:
1422:
1418:
1415:
1414:
1412:
1410:
1406:
1402:
1394:
1391:
1389:
1386:
1384:
1383:constructible
1381:
1380:
1379:
1376:
1374:
1371:
1369:
1366:
1364:
1361:
1359:
1356:
1354:
1351:
1349:
1346:
1344:
1341:
1339:
1336:
1334:
1331:
1329:
1326:
1324:
1321:
1319:
1316:
1315:
1313:
1311:
1306:
1298:
1295:
1293:
1290:
1288:
1285:
1283:
1280:
1278:
1275:
1273:
1270:
1269:
1267:
1263:
1260:
1258:
1255:
1254:
1253:
1250:
1248:
1245:
1243:
1240:
1238:
1235:
1233:
1229:
1225:
1223:
1220:
1216:
1213:
1212:
1211:
1208:
1207:
1204:
1201:
1199:
1195:
1185:
1182:
1180:
1177:
1175:
1172:
1170:
1167:
1165:
1162:
1160:
1157:
1153:
1150:
1149:
1148:
1145:
1141:
1136:
1135:
1134:
1131:
1130:
1128:
1126:
1122:
1114:
1111:
1109:
1106:
1104:
1101:
1100:
1099:
1096:
1094:
1091:
1089:
1086:
1084:
1081:
1079:
1076:
1074:
1071:
1069:
1066:
1065:
1063:
1061:
1060:Propositional
1057:
1051:
1048:
1046:
1043:
1041:
1038:
1036:
1033:
1031:
1028:
1026:
1023:
1019:
1016:
1015:
1014:
1011:
1009:
1006:
1004:
1001:
999:
996:
994:
991:
989:
988:Logical truth
986:
984:
981:
980:
978:
976:
972:
969:
967:
963:
957:
954:
952:
949:
947:
944:
942:
939:
937:
934:
932:
928:
924:
920:
918:
915:
913:
910:
908:
904:
901:
900:
898:
896:
890:
885:
879:
876:
874:
871:
869:
866:
864:
861:
859:
856:
854:
851:
849:
846:
844:
841:
839:
836:
834:
831:
829:
826:
824:
821:
817:
814:
813:
812:
809:
808:
806:
802:
798:
791:
786:
784:
779:
777:
772:
771:
768:
754:
747:
741:
737:
730:
724:
720:
719:
714:
709:
705:
699:
695:
694:
689:
685:
681:
677:
675:0-387-15299-7
671:
667:
666:
660:
656:
650:
646:
642:
638:
634:
628:
625:. MIT Press.
624:
619:
615:
609:
605:
604:
598:
597:
589:
586:
584:
581:
579:
576:
573:
569:
566:
564:
561:
559:
556:
555:
549:
547:
541:
539:
535:
530:
526:
521:
519:
515:
511:
505:
495:
493:
490:
486:
481:
476:
474:
470:
466:
462:
458:
454:
450:
446:
442:
438:
434:
430:
425:
423:
419:
416:
412:
407:
405:
401:
397:
393:
389:
383:
373:
371:
367:
363:
359:
355:
351:
347:
343:
339:
335:
334:
329:
325:
321:
315:
305:
303:
299:
294:
292:
288:
284:
280:
276:
275:semidecidable
272:
268:
267:recursive set
264:
260:
254:
250:
240:
238:
227:
225:
221:
216:
214:
210:
206:
201:
199:
195:
191:
181:
179:
178:Turing degree
175:
171:
167:
163:
158:
156:
152:
148:
143:
141:
137:
136:long division
133:
129:
125:
121:
117:
113:
109:
105:
101:
97:
93:
89:
85:
81:
77:
73:
69:
65:
61:
57:
53:
45:
41:
37:
32:
26:
22:
2505:
2350:
2303:Ultraproduct
2150:Model theory
2115:Independence
2051:Formal proof
2043:Proof theory
2026:
1999:
1956:real numbers
1928:second-order
1839:Substitution
1716:Metalanguage
1657:conservative
1630:Axiom schema
1574:Constructive
1544:MorseâKelley
1510:Set theories
1489:Aleph number
1482:inaccessible
1388:Grothendieck
1272:intersection
1159:Higher-order
1147:Second-order
1093:Truth tables
1050:Venn diagram
833:Formal proof
740:
721:. Springer.
717:
713:Manna, Zohar
696:. Springer.
692:
668:. Springer.
664:
644:
622:
606:. Springer.
602:
542:
537:
533:
528:
524:
522:
509:
507:
477:
472:
468:
464:
456:
452:
448:
444:
440:
439:) such that
436:
432:
428:
426:
421:
417:
408:
403:
399:
395:
391:
385:
353:
349:
345:
341:
337:
331:
327:
317:
295:
290:
282:
278:
274:
270:
262:
258:
256:
243:Decidability
233:
217:
202:
197:
194:infinite set
189:
187:
173:
161:
159:
147:decidability
144:
139:
131:
127:
123:
119:
115:
111:
107:
99:
95:
91:
87:
83:
79:
59:
49:
43:
39:
35:
2413:Type theory
2361:undecidable
2293:Truth value
2180:equivalence
1859:non-logical
1472:Enumeration
1462:Isomorphism
1409:cardinality
1393:Von Neumann
1358:Ultrafilter
1323:Uncountable
1257:equivalence
1174:Quantifiers
1164:Fixed-point
1133:First-order
1013:Consistency
998:Proposition
975:Traditional
946:Lindström's
936:Compactness
878:Type theory
823:Cardinality
485:NP-complete
402:divided by
291:undecidable
174:undecidable
155:undecidable
2528:Categories
2224:elementary
1917:arithmetic
1785:Quantifier
1763:functional
1635:Expression
1353:Transitive
1297:identities
1282:complement
1215:hereditary
1198:Set theory
641:Sipser, M.
594:References
492:complement
398:, what is
184:Definition
2495:Supertask
2398:Recursion
2356:decidable
2190:saturated
2168:of models
2091:deductive
2086:axiomatic
2006:Hilbert's
1993:Euclidean
1974:canonical
1897:axiomatic
1829:Signature
1758:Predicate
1647:Extension
1569:Ackermann
1494:Operation
1373:Universal
1363:Recursive
1338:Singleton
1333:Inhabited
1318:Countable
1308:Types of
1292:power set
1262:partition
1179:Predicate
1125:Predicate
1040:Syllogism
1030:Soundness
1003:Inference
993:Tautology
895:paradoxes
259:decidable
162:decidable
140:decidable
104:algorithm
72:algorithm
2480:Logicism
2473:timeline
2449:Concrete
2308:Validity
2278:T-schema
2271:Kripke's
2266:Tarski's
2261:semantic
2251:Strength
2200:submodel
2195:spectrum
2163:function
2011:Tarski's
2000:Elements
1987:geometry
1943:Robinson
1864:variable
1849:function
1822:spectrum
1812:Sentence
1768:variable
1711:Language
1664:Relation
1625:Automata
1615:Alphabet
1599:language
1453:-jection
1431:codomain
1417:Function
1378:Universe
1348:Infinite
1252:Relation
1035:Validity
1025:Argument
923:theorem,
753:Archived
643:(2020).
552:See also
525:equal to
333:complete
283:provable
279:solvable
230:Examples
209:alphabet
2422:Related
2219:Diagram
2117: (
2096:Hilbert
2081:Systems
2076:Theorem
1954:of the
1899:systems
1679:Formula
1674:Grammar
1590: (
1534:General
1247:Forcing
1232:Element
1152:Monadic
927:paradox
868:Theorem
804:General
205:strings
118:, does
86:, does
2185:finite
1948:Skolem
1901:
1876:Theory
1844:Symbol
1834:String
1817:atomic
1694:ground
1689:closed
1684:atomic
1640:ground
1603:syntax
1499:binary
1426:domain
1343:Finite
1108:finite
966:Logics
925:
873:Theory
725:
700:
672:
651:
629:
610:
2175:Model
1923:Peano
1780:Proof
1620:Arity
1549:Naive
1436:image
1368:Fuzzy
1328:Empty
1277:union
1222:Class
863:Model
853:Lemma
811:Axiom
756:(PDF)
749:(PDF)
281:, or
76:prime
62:is a
2298:Type
2101:list
1905:list
1882:list
1871:Term
1805:rank
1699:open
1593:list
1405:Maps
1310:sets
1169:Free
1139:list
889:list
816:list
723:ISBN
698:ISBN
670:ISBN
649:ISBN
627:ISBN
608:ISBN
510:best
447:) =
406:?".
394:and
296:The
251:and
114:and
98:and
82:and
58:, a
54:and
1985:of
1967:of
1915:of
1447:Sur
1421:Map
1228:Ur-
1210:Set
527:or
340:if
261:or
198:yes
50:In
42:or
40:yes
2530::
2371:NP
1995::
1989::
1919::
1596:),
1451:Bi
1443:In
751:.
686:;
548:.
520:.
409:A
370:NP
304:.
277:,
273:,
200:.
188:A
157:.
142:.
44:no
34:A
2451:/
2366:P
2121:)
1907:)
1903:(
1800:â
1795:!
1790:â
1751:=
1746:â
1741:â
1736:â§
1731:âš
1726:ÂŹ
1449:/
1445:/
1419:/
1230:)
1226:(
1113:â
1103:3
891:)
789:e
782:t
775:v
731:.
706:.
678:.
657:.
635:.
616:.
574:.
538:N
534:N
473:x
471:(
469:f
465:x
457:y
455:,
453:x
449:y
445:x
443:(
441:f
437:y
435:,
433:x
429:f
422:f
418:f
404:y
400:x
396:y
392:x
354:P
350:S
346:S
342:P
338:S
328:P
132:y
128:x
124:y
120:x
116:y
112:x
100:y
96:x
92:y
88:x
84:y
80:x
27:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
