5541:
2256:
The fixed-point operations that we defined so far iterate the inductive definitions of the predicates mentioned in the formula indefinitely, until a fixed point is reached. In implementations, it may be necessary to bound the number of iterations to limit the computation time. The resulting operators
1210:
This inflationary fixed-point agrees with the least-fixed point where the latter is defined. Although at first glance it seems as if inflationary fixed-point logic should be more expressive than least fixed-point logic since it supports a wider range of fixed-point arguments, in fact, every
1227:
While all the fixed-point operators introduced so far iterated only on the definition of a single predicate, many computer programs are more naturally thought of as iterating over several predicates simultaneously. By either increasing the
2239:
1232:
of the fixed-point operators or by nesting them, every simultaneous least, inflationary or partial fixed-point can in fact be expressed using the corresponding single-iteration constructions discussed above.
2671:
2086:
1995:
1134:
1089:
2135:
1706:
1205:
563:
2488:
2567:
1876:
1361:
114:
1274:
439:
3920:
1795:
3310:
3245:
3191:
3096:
3047:
2960:
2406:
2303:
493:
2523:
2444:
2038:
1915:
1593:
1564:
1535:
1506:
1477:
1448:
1419:
1390:
912:
316:
287:
258:
229:
180:
2698:
772:
4595:
2765:
2745:
870:
832:(that is, occurrences preceded by an even number of negations). This guarantees monotonicity of the fixed-point construction (That is, if the second order variable is
2811:
1743:
1638:
726:
637:
600:
2879:
1821:
2725:
973:
946:
799:
3125:
2989:
2912:
2844:
2361:
2332:
369:
1044:
1024:
336:
200:
693:
4678:
3819:
820:
Since the iterated predicates involved in calculating the partial fixed point are not in general monotone, the fixed-point may not always exist. FO(LFP,X),
2140:
4992:
5150:
3759:
3938:
5005:
4328:
4590:
5010:
5000:
4737:
3943:
3555:
4488:
3934:
2572:
5146:
3780:
3587:
Yuri
Gurevich and Saharon Shelah, Fixed-pointed extension of first order logic, Annals of Pure and Applied Logic 32 (1986) 265--280.
3471:
3362:
38:
are extensions of classical predicate logic that have been introduced to express recursion. Their development has been motivated by
5243:
4987:
3812:
4548:
4241:
3982:
5565:
5504:
5206:
4969:
4964:
4789:
4210:
3894:
3630:
5499:
5282:
5199:
4912:
4843:
4720:
3962:
39:
4570:
5424:
5250:
4936:
4169:
4575:
2046:
1955:
1094:
1049:
4907:
4646:
3904:
3805:
2257:
are also of interest from a theoretical point of view since they can also be used to characterise complexity classes.
2095:
1647:
994:
The expressivity of least-fixed point logic coincides exactly with the expressivity of the database querying language
5302:
5297:
1139:
5231:
4821:
4215:
4183:
3874:
3948:
498:
5521:
5470:
5367:
4865:
4826:
4303:
2449:
5362:
3977:
998:, showing that, on ordered structures, Datalog can express exactly those queries executable in polynomial time.
5575:
5570:
5292:
4831:
4683:
4666:
4389:
3869:
1952:) is defined as FO(TC,X) where the transitive closure operator is deterministic. This means that when we apply
1940:. This characterisation is a crucial part of Immerman's proof that NL is closed under complement (NL = co-NL).
1256:
using first-order connectives and predicates, second-order variables as well as a transitive closure operator
5194:
5171:
5132:
5018:
4959:
4605:
4525:
4369:
4313:
3926:
2528:
43:
5484:
5211:
5189:
5156:
5049:
4895:
4880:
4853:
4804:
4688:
4623:
4448:
4414:
4409:
4283:
4114:
4091:
3533:
3334:
1826:
1279:
99:
54:
1259:
5414:
5267:
5059:
4777:
4513:
4419:
4278:
4263:
4144:
4119:
5540:
1006:
Another way to ensure the monotonicity of the fixed-point construction is by only adding new tuples to
398:
5387:
5349:
5226:
5030:
4870:
4794:
4772:
4600:
4558:
4457:
4424:
4288:
4076:
3987:
3392:
Proceedings of the 6th ACM SIGACT-SIGPLAN Symposium on
Principles of Programming Languages - POPL '79
1748:
824:, is the set of formulas in FO(PFP,X) where the partial fixed point is taken only over such formulas
3538:
3256:
3198:
3132:
3056:
2997:
2920:
2366:
2263:
444:
5516:
5407:
5392:
5372:
5329:
5216:
5166:
5092:
5037:
4974:
4767:
4762:
4710:
4478:
4467:
4139:
4039:
3967:
3958:
3954:
3889:
3884:
2493:
2414:
5545:
5314:
5277:
5262:
5255:
5238:
5024:
4890:
4816:
4799:
4752:
4565:
4474:
4308:
4293:
4253:
4205:
4190:
4178:
4134:
4109:
3879:
3828:
3636:
3561:
3477:
3405:
1242:
93:
31:
5042:
4498:
2008:
1885:
1569:
1540:
1511:
1482:
1453:
1424:
1395:
1366:
875:
292:
263:
234:
205:
119:
2676:
743:
5480:
5287:
5097:
5087:
4979:
4860:
4695:
4671:
4452:
4436:
4341:
4318:
4164:
4129:
4024:
3859:
3786:
3776:
3755:
3675:
3626:
3551:
3467:
3368:
3358:
2750:
2730:
839:
89:
74:
2774:
1715:
1605:
698:
609:
572:
5494:
5489:
5382:
5339:
5161:
5122:
5117:
5102:
4928:
4885:
4782:
4580:
4530:
4104:
4066:
3747:
3667:
3618:
3543:
3528:
Vardi, Moshe Y. (1982). "The complexity of relational query languages (Extended
Abstract)".
3508:
3459:
3395:
3350:
2849:
2334:
is a (class of) functions from integers to integers, and for different classes of functions
1800:
1241:
Rather than allow induction over arbitrary predicates, transitive closure logic allows only
2703:
951:
924:
777:
5475:
5465:
5419:
5402:
5357:
5319:
5221:
5141:
4948:
4875:
4848:
4836:
4742:
4656:
4630:
4585:
4553:
4354:
4156:
4099:
4049:
4014:
3972:
3101:
3050:
2965:
2888:
2820:
2337:
2308:
2089:
1937:
804:
It has been proven that on ordered finite structures, a property is expressible in FO(PFP,
348:
5460:
5439:
5397:
5377:
5272:
5127:
4725:
4715:
4705:
4700:
4634:
4508:
4384:
4273:
4268:
4246:
3847:
3248:
2245:
1029:
1009:
988:
321:
185:
62:
3513:
3496:
3354:
644:
5559:
5434:
5112:
4619:
4404:
4394:
4364:
4349:
4019:
3481:
976:
3530:
Proceedings of the fourteenth annual ACM symposium on Theory of computing - STOC '82
5334:
5181:
5082:
5074:
4954:
4902:
4811:
4747:
4730:
4661:
4520:
4379:
4081:
3864:
3640:
3615:
Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC '83
3565:
3409:
3338:
5444:
5324:
4503:
4493:
4440:
4124:
4044:
4029:
3909:
3854:
3456:[1989] Proceedings. Fourth Annual Symposium on Logic in Computer Science
2962:
to be the FO-formulae with an iteration operator whose exponent is in the class
980:
2569:. We first need to define quantifier blocks (QB), a quantifier block is a list
4374:
4229:
4200:
4006:
3751:
2234:{\displaystyle \psi (u,v)=\phi (u,v)\wedge \forall x(x=v\vee \neg \phi (u,x))}
801:
s, so with a polynomial-space counter we can check if there is a loop or not.
58:
17:
3790:
3679:
3451:
3372:
5526:
5429:
4482:
4399:
4359:
4323:
4259:
4071:
4061:
4034:
3463:
3610:
3622:
3547:
3400:
3387:
5511:
5309:
4757:
4462:
4056:
5107:
3899:
995:
47:
65:
suggested fixed-point logic as an expressive database query language.
3797:
3770:
3655:
3452:"Fixpoint extensions of first-order logic and datalog-like languages"
3313:
809:
3671:
57:
in 1974, and it was introduced to computer scientists in 1979, when
4651:
3997:
3842:
1229:
3801:
2666:{\displaystyle (Q_{1}x_{1},\phi _{1})...(Q_{k}x_{k},\phi _{k})}
2244:
Over ordered structures, FO characterises the complexity class
1936:
Over ordered structures, FO characterises the complexity class
1026:
at every stage of iteration, without removing tuples for which
975:
iterations. The
Immerman-Vardi theorem, shown independently by
917:
Due to monotonicity, we only add vectors to the truth table of
3746:. Perspectives in Mathematical Logic (2 ed.). Springer.
53:
Least fixed-point logic was first studied systematically by
948:
possible vectors we will always find a fixed point before
3656:"Nondeterministic Space is Closed under Complementation"
3617:. New York, New York, USA: ACM Press. pp. 347â354.
1421:
are tuples of pairwise distinct first-order variables,
606:). Then, either there is a fixed point, or the list of
3259:
3201:
3135:
3104:
3059:
3000:
2968:
2923:
2891:
2852:
2823:
2777:
2753:
2733:
2706:
2679:
2575:
2531:
2496:
2452:
2417:
2369:
2340:
2311:
2266:
2143:
2098:
2049:
2011:
1958:
1888:
1829:
1803:
1751:
1718:
1650:
1608:
1572:
1543:
1514:
1485:
1456:
1427:
1398:
1369:
1282:
1262:
1142:
1097:
1052:
1032:
1012:
954:
927:
878:
842:
780:
746:
701:
647:
612:
575:
501:
447:
401:
351:
324:
295:
266:
237:
208:
188:
122:
102:
5453:
5348:
5180:
5073:
4925:
4618:
4541:
4435:
4339:
4228:
4155:
4090:
4005:
3996:
3918:
3835:
3343:
2846:time. One should pay attention that here there are
3497:"Relational queries computable in polynomial time"
3304:
3239:
3185:
3119:
3090:
3041:
2983:
2954:
2906:
2873:
2838:
2805:
2759:
2739:
2719:
2692:
2665:
2561:
2517:
2482:
2438:
2400:
2355:
2326:
2297:
2233:
2129:
2080:
2032:
1989:
1909:
1870:
1815:
1789:
1737:
1700:
1632:
1587:
1558:
1529:
1500:
1471:
1442:
1413:
1384:
1355:
1268:
1199:
1128:
1083:
1038:
1018:
967:
940:
906:
864:
793:
766:
720:
687:
631:
594:
557:
487:
433:
363:
330:
310:
281:
252:
223:
194:
174:
108:
2081:{\displaystyle \operatorname {DTC} (\phi _{u,v})}
1990:{\displaystyle \operatorname {DTC} (\phi _{u,v})}
1129:{\displaystyle \operatorname {PFP} (\psi _{P,x})}
1084:{\displaystyle \operatorname {IFP} (\phi _{P,x})}
2130:{\displaystyle \operatorname {TC} (\psi _{u,v})}
1701:{\displaystyle {\mathsf {TC}}(\phi _{u,v})(x,y)}
732:if there is a fixed point, else as false. Since
3394:. New York, New York, USA: ACM Press: 110â119.
2885:variables and each of those variable are used
1200:{\displaystyle \psi (P,x)=\phi (P,x)\vee P(x)}
695:is defined as the value of the fixed point of
3813:
3742:Ebbinghaus, Heinz-Dieter; Flum, Jörg (1999).
3339:"Elementary Induction on Abstract Structures"
8:
3611:"Languages which capture complexity classes"
3532:. New York, NY, USA: ACM. pp. 137â146.
2813:the iteration operator, which is defined as
2363:we will obtain different complexity classes
558:{\displaystyle P_{i}(x)=\varphi (P_{i-1},x)}
3458:. IEEE Comput. Soc. Press. pp. 71â79.
3386:Aho, Alfred V.; Ullman, Jeffrey D. (1979).
3316:. It is also another way to write FO(PFP).
2483:{\displaystyle (\forall x(P\Rightarrow Q))}
2260:We will define first-order with iteration,
4639:
4234:
4002:
3820:
3806:
3798:
3388:"Universality of data retrieval languages"
3251:. It is also another way to write FO(IFP).
2991:, and we obtain the following equalities:
828:that only contain positive occurrences of
602:substituted for the second-order variable
96:as well as a partial fixed point operator
3537:
3512:
3399:
3282:
3277:
3261:
3260:
3258:
3219:
3203:
3202:
3200:
3165:
3137:
3136:
3134:
3103:
3061:
3060:
3058:
3030:
3002:
3001:
2999:
2967:
2925:
2924:
2922:
2890:
2851:
2822:
2788:
2776:
2771:is a quantifiers block then we will call
2752:
2732:
2711:
2705:
2684:
2678:
2654:
2641:
2631:
2606:
2593:
2583:
2574:
2530:
2495:
2451:
2416:
2371:
2370:
2368:
2339:
2310:
2268:
2267:
2265:
2142:
2112:
2097:
2063:
2048:
2010:
1972:
1957:
1887:
1853:
1840:
1828:
1802:
1775:
1756:
1750:
1726:
1717:
1668:
1652:
1651:
1649:
1607:
1574:
1573:
1571:
1545:
1544:
1542:
1516:
1515:
1513:
1487:
1486:
1484:
1458:
1457:
1455:
1429:
1428:
1426:
1400:
1399:
1397:
1371:
1370:
1368:
1342:
1341:
1330:
1329:
1307:
1306:
1292:
1291:
1290:
1281:
1261:
1141:
1111:
1096:
1066:
1051:
1031:
1011:
959:
953:
932:
926:
883:
877:
847:
841:
785:
779:
756:
751:
745:
709:
700:
655:
646:
620:
611:
580:
574:
534:
506:
500:
452:
446:
419:
409:
400:
350:
323:
297:
296:
294:
268:
267:
265:
239:
238:
236:
210:
209:
207:
187:
161:
160:
132:
131:
130:
121:
101:
395:as variables. We can iteratively define
3326:
3265:
3262:
3207:
3204:
3141:
3138:
3065:
3062:
3006:
3003:
2929:
2926:
2700:s are quantifier-free FO-formulae and
2562:{\displaystyle (\exists x(P\wedge Q))}
2375:
2372:
2272:
2269:
1944:Deterministic transitive closure logic
1656:
1653:
90:first-order connectives and predicates
3604:
3602:
1252:) is the set of formulas formed from
1046:no longer holds. Formally, we define
84:) is the set of formulas formed from
7:
1871:{\displaystyle \phi (z_{i},z_{i+1})}
1356:{\displaystyle {\vec {s}}{\vec {t}}}
379:be a second-order variable of arity
260:a tuple of terms and the lengths of
109:{\displaystyle \operatorname {PFP} }
1882:is a formula written in FO(TC) and
1479:tuples of terms and the lengths of
1269:{\displaystyle \operatorname {TC} }
2881:quantifiers in the list, but only
2754:
2734:
2535:
2500:
2456:
2421:
2207:
2186:
1276:used to form formulas of the form
231:a tuple of first-order variables,
116:used to form formulas of the form
25:
3596:Ebbinghaus and Flum, pp. 179, 193
3450:Abiteboul, S.; Vianu, V. (1989).
1215:)-formula is equivalent to an FO(
5539:
434:{\displaystyle (P_{i})_{i\in N}}
2411:In this section we will write
1790:{\displaystyle z_{1}=x,z_{n}=y}
387:be an FO(PFP,X) function using
3305:{\displaystyle {\mathsf {FO}}}
3299:
3292:
3286:
3270:
3240:{\displaystyle {\mathsf {FO}}}
3234:
3229:
3223:
3212:
3186:{\displaystyle {\mathsf {FO}}}
3180:
3175:
3169:
3162:
3149:
3146:
3114:
3108:
3091:{\displaystyle {\mathsf {FO}}}
3085:
3082:
3076:
3070:
3042:{\displaystyle {\mathsf {FO}}}
3036:
3027:
3014:
3011:
2978:
2972:
2955:{\displaystyle {\mathsf {FO}}}
2949:
2946:
2940:
2934:
2901:
2895:
2868:
2862:
2833:
2827:
2798:
2792:
2785:
2778:
2660:
2624:
2612:
2576:
2556:
2553:
2541:
2532:
2509:
2497:
2477:
2474:
2468:
2462:
2453:
2430:
2418:
2401:{\displaystyle {\mathsf {FO}}}
2395:
2392:
2386:
2380:
2350:
2344:
2321:
2315:
2298:{\displaystyle {\mathsf {FO}}}
2292:
2289:
2283:
2277:
2228:
2225:
2213:
2192:
2180:
2168:
2159:
2147:
2124:
2105:
2075:
2056:
2027:
2015:
1984:
1965:
1904:
1892:
1865:
1833:
1732:
1719:
1695:
1683:
1680:
1661:
1598:TC is defined as follows: Let
1579:
1550:
1521:
1492:
1463:
1434:
1405:
1376:
1347:
1335:
1326:
1312:
1297:
1283:
1194:
1188:
1179:
1167:
1158:
1146:
1123:
1104:
1078:
1059:
1002:Inflationary fixed-point logic
901:
895:
859:
853:
715:
702:
682:
679:
673:
648:
626:
613:
552:
527:
518:
512:
488:{\displaystyle P_{0}(x)=false}
464:
458:
416:
402:
302:
273:
244:
215:
166:
157:
137:
123:
1:
5500:History of mathematical logic
3514:10.1016/s0019-9958(86)80029-8
3355:10.1016/s0049-237x(08)x7092-2
2518:{\displaystyle (\exists xP)Q}
2439:{\displaystyle (\forall xP)Q}
40:descriptive complexity theory
27:Concept in mathematical logic
5425:Primitive recursive function
808:) if and only if it lies in
202:is a second-order variable,
3578:Ebbinghaus and Flum, p. 242
3431:Ebbinghaus and Flum, p. 121
3422:Ebbinghaus and Flum, p. 121
2001:, there exists at most one
991:on all ordered structures.
921:, and since there are only
318:coincide with the arity of
5592:
4489:SchröderâBernstein theorem
4216:Monadic predicate calculus
3875:Foundations of mathematics
3098:is FO-uniform AC of depth
2033:{\displaystyle \phi (u,v)}
1910:{\displaystyle \phi (x,y)}
1602:be a positive integer and
1588:{\displaystyle {\vec {t}}}
1559:{\displaystyle {\vec {s}}}
1530:{\displaystyle {\vec {y}}}
1501:{\displaystyle {\vec {x}}}
1472:{\displaystyle {\vec {s}}}
1443:{\displaystyle {\vec {t}}}
1414:{\displaystyle {\vec {y}}}
1385:{\displaystyle {\vec {x}}}
1245:to be expressed directly.
907:{\displaystyle P_{i+1}(x)}
736:s are properties of arity
311:{\displaystyle {\vec {t}}}
282:{\displaystyle {\vec {x}}}
253:{\displaystyle {\vec {t}}}
224:{\displaystyle {\vec {x}}}
175:{\displaystyle {\vec {t}}}
42:and their relationship to
5535:
5522:Philosophy of mathematics
5471:Automated theorem proving
4642:
4596:Von NeumannâBernaysâGödel
4237:
3752:10.1007/978-3-662-03182-7
3660:SIAM Journal on Computing
2693:{\displaystyle \phi _{i}}
1917:means that the variables
767:{\displaystyle 2^{n^{k}}}
69:Partial fixed-point logic
2760:{\displaystyle \exists }
2740:{\displaystyle \forall }
1237:Transitive closure logic
865:{\displaystyle P_{i}(x)}
44:database query languages
5172:Self-verifying theories
4993:Tarski's axiomatization
3944:Tarski's undefinability
3939:incompleteness theorems
3769:Neil, Immerman (1999).
3654:Immerman, Neil (1988).
3609:Immerman, Neil (1983).
3501:Information and Control
3495:Immerman, Neil (1986).
3464:10.1109/lics.1989.39160
3335:Moschovakis, Yiannis N.
3049:is equal to FO-uniform
2806:{\displaystyle ^{t(n)}}
1997:, we know that for all
1738:{\displaystyle (z_{i})}
1708:is true if there exist
1633:{\displaystyle u,v,x,y}
822:least fixed-point logic
816:Least fixed-point logic
721:{\displaystyle (P_{i})}
632:{\displaystyle (P_{i})}
595:{\displaystyle P_{i-1}}
5566:Descriptive complexity
5546:Mathematics portal
5157:Proof of impossibility
4805:propositional variable
4115:Propositional calculus
3772:Descriptive complexity
3306:
3241:
3187:
3121:
3092:
3043:
2985:
2956:
2908:
2875:
2874:{\displaystyle k*t(n)}
2840:
2807:
2761:
2741:
2721:
2694:
2667:
2563:
2519:
2484:
2440:
2402:
2357:
2328:
2299:
2235:
2131:
2082:
2034:
1991:
1911:
1872:
1817:
1816:{\displaystyle i<n}
1791:
1739:
1702:
1634:
1589:
1560:
1531:
1502:
1473:
1444:
1415:
1386:
1357:
1270:
1223:Simultaneous induction
1201:
1130:
1085:
1040:
1020:
969:
942:
908:
866:
795:
768:
722:
689:
633:
596:
559:
489:
435:
365:
332:
312:
283:
254:
225:
196:
176:
110:
94:second-order variables
55:Yiannis N. Moschovakis
5415:Kolmogorov complexity
5368:Computably enumerable
5268:Model complete theory
5060:Principia Mathematica
4120:Propositional formula
3949:BanachâTarski paradox
3728:Immerman 1999, p. 161
3623:10.1145/800061.808765
3548:10.1145/800070.802186
3440:Immerman 1999, p. 161
3401:10.1145/567752.567763
3307:
3242:
3188:
3122:
3093:
3044:
2986:
2957:
2909:
2876:
2841:
2808:
2762:
2742:
2722:
2720:{\displaystyle Q_{i}}
2695:
2668:
2564:
2520:
2485:
2441:
2403:
2358:
2329:
2300:
2236:
2132:
2083:
2035:
1992:
1912:
1873:
1818:
1792:
1740:
1712:vectors of variables
1703:
1635:
1590:
1561:
1532:
1503:
1474:
1445:
1416:
1387:
1358:
1271:
1202:
1131:
1086:
1041:
1021:
970:
968:{\displaystyle n^{k}}
943:
941:{\displaystyle n^{k}}
909:
867:
796:
794:{\displaystyle P_{i}}
769:
723:
690:
634:
597:
560:
490:
436:
366:
333:
313:
284:
255:
226:
197:
177:
111:
5363:ChurchâTuring thesis
5350:Computability theory
4559:continuum hypothesis
4077:Square of opposition
3935:Gödel's completeness
3719:Immerman 1999, p. 58
3710:Immerman 1999, p. 84
3701:Immerman 1999, p. 82
3692:Immerman 1999, p. 63
3257:
3199:
3133:
3120:{\displaystyle t(n)}
3102:
3057:
2998:
2984:{\displaystyle t(n)}
2966:
2921:
2907:{\displaystyle t(n)}
2889:
2850:
2839:{\displaystyle t(n)}
2821:
2775:
2751:
2731:
2704:
2677:
2573:
2529:
2494:
2450:
2415:
2367:
2356:{\displaystyle t(n)}
2338:
2327:{\displaystyle t(n)}
2309:
2264:
2141:
2096:
2047:
2043:We can suppose that
2009:
1956:
1886:
1827:
1801:
1749:
1716:
1648:
1606:
1570:
1541:
1512:
1483:
1454:
1425:
1396:
1367:
1280:
1260:
1140:
1095:
1050:
1030:
1010:
983:, shows that FO(LFP,
952:
925:
876:
840:
778:
744:
740:, there are at most
699:
645:
610:
573:
499:
445:
399:
349:
322:
293:
264:
235:
206:
186:
120:
100:
75:relational signature
5517:Mathematical object
5408:P versus NP problem
5373:Computable function
5167:Reverse mathematics
5093:Logical consequence
4970:primitive recursive
4965:elementary function
4738:Free/bound variable
4591:TarskiâGrothendieck
4110:Logical connectives
4040:Logical equivalence
3890:Logical consequence
3744:Finite Model Theory
1243:transitive closures
364:{\displaystyle x,y}
46:, in particular to
5315:Transfer principle
5278:Semantics of logic
5263:Categorical theory
5239:Non-standard model
4753:Logical connective
3880:Information theory
3829:Mathematical logic
3302:
3237:
3183:
3117:
3088:
3039:
2981:
2952:
2917:We can now define
2904:
2871:
2836:
2803:
2757:
2737:
2717:
2690:
2663:
2559:
2515:
2480:
2436:
2398:
2353:
2324:
2295:
2231:
2127:
2078:
2030:
1987:
1907:
1868:
1813:
1787:
1735:
1698:
1630:
1585:
1556:
1527:
1498:
1469:
1440:
1411:
1382:
1353:
1266:
1197:
1126:
1081:
1036:
1016:
965:
938:
904:
862:
791:
764:
718:
685:
629:
592:
555:
485:
431:
361:
328:
308:
279:
250:
221:
192:
172:
106:
36:fixed-point logics
32:mathematical logic
5553:
5552:
5485:Abstract category
5288:Theories of truth
5098:Rule of inference
5088:Natural deduction
5069:
5068:
4614:
4613:
4319:Cartesian product
4224:
4223:
4130:Many-valued logic
4105:Boolean functions
3988:Russell's paradox
3963:diagonal argument
3860:First-order logic
3761:978-3-662-03184-1
1582:
1553:
1524:
1495:
1466:
1437:
1408:
1379:
1350:
1338:
1315:
1300:
1039:{\displaystyle P}
1019:{\displaystyle P}
331:{\displaystyle P}
305:
276:
247:
218:
195:{\displaystyle P}
169:
140:
16:(Redirected from
5583:
5544:
5543:
5495:History of logic
5490:Category of sets
5383:Decision problem
5162:Ordinal analysis
5103:Sequent calculus
5001:Boolean algebras
4941:
4940:
4915:
4886:logical/constant
4640:
4626:
4549:ZermeloâFraenkel
4300:Set operations:
4235:
4172:
4003:
3983:LöwenheimâSkolem
3870:Formal semantics
3822:
3815:
3808:
3799:
3794:
3765:
3729:
3726:
3720:
3717:
3711:
3708:
3702:
3699:
3693:
3690:
3684:
3683:
3651:
3645:
3644:
3606:
3597:
3594:
3588:
3585:
3579:
3576:
3570:
3569:
3541:
3525:
3519:
3518:
3516:
3492:
3486:
3485:
3447:
3441:
3438:
3432:
3429:
3423:
3420:
3414:
3413:
3403:
3383:
3377:
3376:
3331:
3311:
3309:
3308:
3303:
3298:
3297:
3296:
3295:
3269:
3268:
3246:
3244:
3243:
3238:
3233:
3232:
3211:
3210:
3192:
3190:
3189:
3184:
3179:
3178:
3145:
3144:
3126:
3124:
3123:
3118:
3097:
3095:
3094:
3089:
3069:
3068:
3048:
3046:
3045:
3040:
3035:
3034:
3010:
3009:
2990:
2988:
2987:
2982:
2961:
2959:
2958:
2953:
2933:
2932:
2913:
2911:
2910:
2905:
2884:
2880:
2878:
2877:
2872:
2845:
2843:
2842:
2837:
2816:
2812:
2810:
2809:
2804:
2802:
2801:
2770:
2766:
2764:
2763:
2758:
2746:
2744:
2743:
2738:
2726:
2724:
2723:
2718:
2716:
2715:
2699:
2697:
2696:
2691:
2689:
2688:
2672:
2670:
2669:
2664:
2659:
2658:
2646:
2645:
2636:
2635:
2611:
2610:
2598:
2597:
2588:
2587:
2568:
2566:
2565:
2560:
2524:
2522:
2521:
2516:
2489:
2487:
2486:
2481:
2445:
2443:
2442:
2437:
2407:
2405:
2404:
2399:
2379:
2378:
2362:
2360:
2359:
2354:
2333:
2331:
2330:
2325:
2304:
2302:
2301:
2296:
2276:
2275:
2240:
2238:
2237:
2232:
2136:
2134:
2133:
2128:
2123:
2122:
2087:
2085:
2084:
2079:
2074:
2073:
2039:
2037:
2036:
2031:
2004:
2000:
1996:
1994:
1993:
1988:
1983:
1982:
1932:
1928:
1925:are replaced by
1924:
1920:
1916:
1914:
1913:
1908:
1881:
1877:
1875:
1874:
1869:
1864:
1863:
1845:
1844:
1822:
1820:
1819:
1814:
1796:
1794:
1793:
1788:
1780:
1779:
1761:
1760:
1744:
1742:
1741:
1736:
1731:
1730:
1711:
1707:
1705:
1704:
1699:
1679:
1678:
1660:
1659:
1644:variables. Then
1643:
1639:
1637:
1636:
1631:
1601:
1594:
1592:
1591:
1586:
1584:
1583:
1575:
1565:
1563:
1562:
1557:
1555:
1554:
1546:
1536:
1534:
1533:
1528:
1526:
1525:
1517:
1507:
1505:
1504:
1499:
1497:
1496:
1488:
1478:
1476:
1475:
1470:
1468:
1467:
1459:
1449:
1447:
1446:
1441:
1439:
1438:
1430:
1420:
1418:
1417:
1412:
1410:
1409:
1401:
1391:
1389:
1388:
1383:
1381:
1380:
1372:
1362:
1360:
1359:
1354:
1352:
1351:
1343:
1340:
1339:
1331:
1319:
1318:
1317:
1316:
1308:
1302:
1301:
1293:
1275:
1273:
1272:
1267:
1206:
1204:
1203:
1198:
1135:
1133:
1132:
1127:
1122:
1121:
1090:
1088:
1087:
1082:
1077:
1076:
1045:
1043:
1042:
1037:
1025:
1023:
1022:
1017:
987:) characterises
974:
972:
971:
966:
964:
963:
947:
945:
944:
939:
937:
936:
920:
913:
911:
910:
905:
894:
893:
871:
869:
868:
863:
852:
851:
835:
831:
827:
800:
798:
797:
792:
790:
789:
773:
771:
770:
765:
763:
762:
761:
760:
739:
735:
731:
727:
725:
724:
719:
714:
713:
694:
692:
691:
688:{\displaystyle }
686:
666:
665:
638:
636:
635:
630:
625:
624:
605:
601:
599:
598:
593:
591:
590:
568:
564:
562:
561:
556:
545:
544:
511:
510:
494:
492:
491:
486:
457:
456:
440:
438:
437:
432:
430:
429:
414:
413:
394:
390:
386:
382:
378:
374:
370:
368:
367:
362:
344:
337:
335:
334:
329:
317:
315:
314:
309:
307:
306:
298:
288:
286:
285:
280:
278:
277:
269:
259:
257:
256:
251:
249:
248:
240:
230:
228:
227:
222:
220:
219:
211:
201:
199:
198:
193:
181:
179:
178:
173:
171:
170:
162:
150:
149:
142:
141:
133:
115:
113:
112:
107:
21:
5591:
5590:
5586:
5585:
5584:
5582:
5581:
5580:
5576:Predicate logic
5571:Database theory
5556:
5555:
5554:
5549:
5538:
5531:
5476:Category theory
5466:Algebraic logic
5449:
5420:Lambda calculus
5358:Church encoding
5344:
5320:Truth predicate
5176:
5142:Complete theory
5065:
4934:
4930:
4926:
4921:
4913:
4633: and
4629:
4624:
4610:
4586:New Foundations
4554:axiom of choice
4537:
4499:Gödel numbering
4439: and
4431:
4335:
4220:
4170:
4151:
4100:Boolean algebra
4086:
4050:Equiconsistency
4015:Classical logic
3992:
3973:Halting problem
3961: and
3937: and
3925: and
3924:
3919:Theorems (
3914:
3831:
3826:
3783:
3768:
3762:
3741:
3738:
3733:
3732:
3727:
3723:
3718:
3714:
3709:
3705:
3700:
3696:
3691:
3687:
3672:10.1137/0217058
3653:
3652:
3648:
3633:
3608:
3607:
3600:
3595:
3591:
3586:
3582:
3577:
3573:
3558:
3539:10.1.1.331.6045
3527:
3526:
3522:
3507:(1â3): 86â104.
3494:
3493:
3489:
3474:
3449:
3448:
3444:
3439:
3435:
3430:
3426:
3421:
3417:
3385:
3384:
3380:
3365:
3333:
3332:
3328:
3323:
3278:
3273:
3255:
3254:
3215:
3197:
3196:
3193:is equal to NC.
3161:
3131:
3130:
3100:
3099:
3055:
3054:
3026:
2996:
2995:
2964:
2963:
2919:
2918:
2887:
2886:
2882:
2848:
2847:
2819:
2818:
2814:
2784:
2773:
2772:
2768:
2749:
2748:
2729:
2728:
2707:
2702:
2701:
2680:
2675:
2674:
2650:
2637:
2627:
2602:
2589:
2579:
2571:
2570:
2527:
2526:
2492:
2491:
2448:
2447:
2413:
2412:
2365:
2364:
2336:
2335:
2307:
2306:
2262:
2261:
2254:
2139:
2138:
2108:
2094:
2093:
2090:syntactic sugar
2059:
2045:
2044:
2007:
2006:
2002:
1998:
1968:
1954:
1953:
1946:
1930:
1926:
1922:
1918:
1884:
1883:
1879:
1878:is true. Here,
1849:
1836:
1825:
1824:
1799:
1798:
1771:
1752:
1747:
1746:
1722:
1714:
1713:
1709:
1664:
1646:
1645:
1641:
1604:
1603:
1599:
1568:
1567:
1539:
1538:
1510:
1509:
1481:
1480:
1452:
1451:
1423:
1422:
1394:
1393:
1365:
1364:
1286:
1278:
1277:
1258:
1257:
1239:
1225:
1138:
1137:
1107:
1093:
1092:
1062:
1048:
1047:
1028:
1027:
1008:
1007:
1004:
955:
950:
949:
928:
923:
922:
918:
879:
874:
873:
872:always implies
843:
838:
837:
833:
829:
825:
818:
781:
776:
775:
774:values for the
752:
747:
742:
741:
737:
733:
729:
705:
697:
696:
651:
643:
642:
616:
608:
607:
603:
576:
571:
570:
566:
530:
502:
497:
496:
448:
443:
442:
415:
405:
397:
396:
392:
388:
384:
380:
376:
372:
347:
346:
345:be an integer,
342:
320:
319:
291:
290:
262:
261:
233:
232:
204:
203:
184:
183:
126:
118:
117:
98:
97:
71:
28:
23:
22:
15:
12:
11:
5:
5589:
5587:
5579:
5578:
5573:
5568:
5558:
5557:
5551:
5550:
5536:
5533:
5532:
5530:
5529:
5524:
5519:
5514:
5509:
5508:
5507:
5497:
5492:
5487:
5478:
5473:
5468:
5463:
5461:Abstract logic
5457:
5455:
5451:
5450:
5448:
5447:
5442:
5440:Turing machine
5437:
5432:
5427:
5422:
5417:
5412:
5411:
5410:
5405:
5400:
5395:
5390:
5380:
5378:Computable set
5375:
5370:
5365:
5360:
5354:
5352:
5346:
5345:
5343:
5342:
5337:
5332:
5327:
5322:
5317:
5312:
5307:
5306:
5305:
5300:
5295:
5285:
5280:
5275:
5273:Satisfiability
5270:
5265:
5260:
5259:
5258:
5248:
5247:
5246:
5236:
5235:
5234:
5229:
5224:
5219:
5214:
5204:
5203:
5202:
5197:
5190:Interpretation
5186:
5184:
5178:
5177:
5175:
5174:
5169:
5164:
5159:
5154:
5144:
5139:
5138:
5137:
5136:
5135:
5125:
5120:
5110:
5105:
5100:
5095:
5090:
5085:
5079:
5077:
5071:
5070:
5067:
5066:
5064:
5063:
5055:
5054:
5053:
5052:
5047:
5046:
5045:
5040:
5035:
5015:
5014:
5013:
5011:minimal axioms
5008:
4997:
4996:
4995:
4984:
4983:
4982:
4977:
4972:
4967:
4962:
4957:
4944:
4942:
4923:
4922:
4920:
4919:
4918:
4917:
4905:
4900:
4899:
4898:
4893:
4888:
4883:
4873:
4868:
4863:
4858:
4857:
4856:
4851:
4841:
4840:
4839:
4834:
4829:
4824:
4814:
4809:
4808:
4807:
4802:
4797:
4787:
4786:
4785:
4780:
4775:
4770:
4765:
4760:
4750:
4745:
4740:
4735:
4734:
4733:
4728:
4723:
4718:
4708:
4703:
4701:Formation rule
4698:
4693:
4692:
4691:
4686:
4676:
4675:
4674:
4664:
4659:
4654:
4649:
4643:
4637:
4620:Formal systems
4616:
4615:
4612:
4611:
4609:
4608:
4603:
4598:
4593:
4588:
4583:
4578:
4573:
4568:
4563:
4562:
4561:
4556:
4545:
4543:
4539:
4538:
4536:
4535:
4534:
4533:
4523:
4518:
4517:
4516:
4509:Large cardinal
4506:
4501:
4496:
4491:
4486:
4472:
4471:
4470:
4465:
4460:
4445:
4443:
4433:
4432:
4430:
4429:
4428:
4427:
4422:
4417:
4407:
4402:
4397:
4392:
4387:
4382:
4377:
4372:
4367:
4362:
4357:
4352:
4346:
4344:
4337:
4336:
4334:
4333:
4332:
4331:
4326:
4321:
4316:
4311:
4306:
4298:
4297:
4296:
4291:
4281:
4276:
4274:Extensionality
4271:
4269:Ordinal number
4266:
4256:
4251:
4250:
4249:
4238:
4232:
4226:
4225:
4222:
4221:
4219:
4218:
4213:
4208:
4203:
4198:
4193:
4188:
4187:
4186:
4176:
4175:
4174:
4161:
4159:
4153:
4152:
4150:
4149:
4148:
4147:
4142:
4137:
4127:
4122:
4117:
4112:
4107:
4102:
4096:
4094:
4088:
4087:
4085:
4084:
4079:
4074:
4069:
4064:
4059:
4054:
4053:
4052:
4042:
4037:
4032:
4027:
4022:
4017:
4011:
4009:
4000:
3994:
3993:
3991:
3990:
3985:
3980:
3975:
3970:
3965:
3953:Cantor's
3951:
3946:
3941:
3931:
3929:
3916:
3915:
3913:
3912:
3907:
3902:
3897:
3892:
3887:
3882:
3877:
3872:
3867:
3862:
3857:
3852:
3851:
3850:
3839:
3837:
3833:
3832:
3827:
3825:
3824:
3817:
3810:
3802:
3796:
3795:
3781:
3766:
3760:
3737:
3734:
3731:
3730:
3721:
3712:
3703:
3694:
3685:
3666:(5): 935â938.
3646:
3631:
3598:
3589:
3580:
3571:
3557:978-0897910705
3556:
3520:
3487:
3472:
3442:
3433:
3424:
3415:
3378:
3363:
3325:
3324:
3322:
3319:
3318:
3317:
3301:
3294:
3291:
3288:
3285:
3281:
3276:
3272:
3267:
3264:
3252:
3236:
3231:
3228:
3225:
3222:
3218:
3214:
3209:
3206:
3194:
3182:
3177:
3174:
3171:
3168:
3164:
3160:
3157:
3154:
3151:
3148:
3143:
3140:
3128:
3116:
3113:
3110:
3107:
3087:
3084:
3081:
3078:
3075:
3072:
3067:
3064:
3053:, and in fact
3038:
3033:
3029:
3025:
3022:
3019:
3016:
3013:
3008:
3005:
2980:
2977:
2974:
2971:
2951:
2948:
2945:
2942:
2939:
2936:
2931:
2928:
2903:
2900:
2897:
2894:
2870:
2867:
2864:
2861:
2858:
2855:
2835:
2832:
2829:
2826:
2800:
2797:
2794:
2791:
2787:
2783:
2780:
2756:
2736:
2714:
2710:
2687:
2683:
2662:
2657:
2653:
2649:
2644:
2640:
2634:
2630:
2626:
2623:
2620:
2617:
2614:
2609:
2605:
2601:
2596:
2592:
2586:
2582:
2578:
2558:
2555:
2552:
2549:
2546:
2543:
2540:
2537:
2534:
2514:
2511:
2508:
2505:
2502:
2499:
2479:
2476:
2473:
2470:
2467:
2464:
2461:
2458:
2455:
2435:
2432:
2429:
2426:
2423:
2420:
2397:
2394:
2391:
2388:
2385:
2382:
2377:
2374:
2352:
2349:
2346:
2343:
2323:
2320:
2317:
2314:
2294:
2291:
2288:
2285:
2282:
2279:
2274:
2271:
2253:
2250:
2230:
2227:
2224:
2221:
2218:
2215:
2212:
2209:
2206:
2203:
2200:
2197:
2194:
2191:
2188:
2185:
2182:
2179:
2176:
2173:
2170:
2167:
2164:
2161:
2158:
2155:
2152:
2149:
2146:
2126:
2121:
2118:
2115:
2111:
2107:
2104:
2101:
2077:
2072:
2069:
2066:
2062:
2058:
2055:
2052:
2029:
2026:
2023:
2020:
2017:
2014:
1986:
1981:
1978:
1975:
1971:
1967:
1964:
1961:
1945:
1942:
1906:
1903:
1900:
1897:
1894:
1891:
1867:
1862:
1859:
1856:
1852:
1848:
1843:
1839:
1835:
1832:
1812:
1809:
1806:
1797:, and for all
1786:
1783:
1778:
1774:
1770:
1767:
1764:
1759:
1755:
1734:
1729:
1725:
1721:
1697:
1694:
1691:
1688:
1685:
1682:
1677:
1674:
1671:
1667:
1663:
1658:
1655:
1640:be vectors of
1629:
1626:
1623:
1620:
1617:
1614:
1611:
1581:
1578:
1552:
1549:
1523:
1520:
1494:
1491:
1465:
1462:
1436:
1433:
1407:
1404:
1378:
1375:
1349:
1346:
1337:
1334:
1328:
1325:
1322:
1314:
1311:
1305:
1299:
1296:
1289:
1285:
1265:
1238:
1235:
1224:
1221:
1196:
1193:
1190:
1187:
1184:
1181:
1178:
1175:
1172:
1169:
1166:
1163:
1160:
1157:
1154:
1151:
1148:
1145:
1125:
1120:
1117:
1114:
1110:
1106:
1103:
1100:
1080:
1075:
1072:
1069:
1065:
1061:
1058:
1055:
1035:
1015:
1003:
1000:
962:
958:
935:
931:
903:
900:
897:
892:
889:
886:
882:
861:
858:
855:
850:
846:
817:
814:
788:
784:
759:
755:
750:
717:
712:
708:
704:
684:
681:
678:
675:
672:
669:
664:
661:
658:
654:
650:
628:
623:
619:
615:
589:
586:
583:
579:
554:
551:
548:
543:
540:
537:
533:
529:
526:
523:
520:
517:
514:
509:
505:
484:
481:
478:
475:
472:
469:
466:
463:
460:
455:
451:
428:
425:
422:
418:
412:
408:
404:
371:be vectors of
360:
357:
354:
327:
304:
301:
275:
272:
246:
243:
217:
214:
191:
168:
165:
159:
156:
153:
148:
145:
139:
136:
129:
125:
105:
70:
67:
63:Jeffrey Ullman
26:
24:
18:Fixpoint logic
14:
13:
10:
9:
6:
4:
3:
2:
5588:
5577:
5574:
5572:
5569:
5567:
5564:
5563:
5561:
5548:
5547:
5542:
5534:
5528:
5525:
5523:
5520:
5518:
5515:
5513:
5510:
5506:
5503:
5502:
5501:
5498:
5496:
5493:
5491:
5488:
5486:
5482:
5479:
5477:
5474:
5472:
5469:
5467:
5464:
5462:
5459:
5458:
5456:
5452:
5446:
5443:
5441:
5438:
5436:
5435:Recursive set
5433:
5431:
5428:
5426:
5423:
5421:
5418:
5416:
5413:
5409:
5406:
5404:
5401:
5399:
5396:
5394:
5391:
5389:
5386:
5385:
5384:
5381:
5379:
5376:
5374:
5371:
5369:
5366:
5364:
5361:
5359:
5356:
5355:
5353:
5351:
5347:
5341:
5338:
5336:
5333:
5331:
5328:
5326:
5323:
5321:
5318:
5316:
5313:
5311:
5308:
5304:
5301:
5299:
5296:
5294:
5291:
5290:
5289:
5286:
5284:
5281:
5279:
5276:
5274:
5271:
5269:
5266:
5264:
5261:
5257:
5254:
5253:
5252:
5249:
5245:
5244:of arithmetic
5242:
5241:
5240:
5237:
5233:
5230:
5228:
5225:
5223:
5220:
5218:
5215:
5213:
5210:
5209:
5208:
5205:
5201:
5198:
5196:
5193:
5192:
5191:
5188:
5187:
5185:
5183:
5179:
5173:
5170:
5168:
5165:
5163:
5160:
5158:
5155:
5152:
5151:from ZFC
5148:
5145:
5143:
5140:
5134:
5131:
5130:
5129:
5126:
5124:
5121:
5119:
5116:
5115:
5114:
5111:
5109:
5106:
5104:
5101:
5099:
5096:
5094:
5091:
5089:
5086:
5084:
5081:
5080:
5078:
5076:
5072:
5062:
5061:
5057:
5056:
5051:
5050:non-Euclidean
5048:
5044:
5041:
5039:
5036:
5034:
5033:
5029:
5028:
5026:
5023:
5022:
5020:
5016:
5012:
5009:
5007:
5004:
5003:
5002:
4998:
4994:
4991:
4990:
4989:
4985:
4981:
4978:
4976:
4973:
4971:
4968:
4966:
4963:
4961:
4958:
4956:
4953:
4952:
4950:
4946:
4945:
4943:
4938:
4932:
4927:Example
4924:
4916:
4911:
4910:
4909:
4906:
4904:
4901:
4897:
4894:
4892:
4889:
4887:
4884:
4882:
4879:
4878:
4877:
4874:
4872:
4869:
4867:
4864:
4862:
4859:
4855:
4852:
4850:
4847:
4846:
4845:
4842:
4838:
4835:
4833:
4830:
4828:
4825:
4823:
4820:
4819:
4818:
4815:
4813:
4810:
4806:
4803:
4801:
4798:
4796:
4793:
4792:
4791:
4788:
4784:
4781:
4779:
4776:
4774:
4771:
4769:
4766:
4764:
4761:
4759:
4756:
4755:
4754:
4751:
4749:
4746:
4744:
4741:
4739:
4736:
4732:
4729:
4727:
4724:
4722:
4719:
4717:
4714:
4713:
4712:
4709:
4707:
4704:
4702:
4699:
4697:
4694:
4690:
4687:
4685:
4684:by definition
4682:
4681:
4680:
4677:
4673:
4670:
4669:
4668:
4665:
4663:
4660:
4658:
4655:
4653:
4650:
4648:
4645:
4644:
4641:
4638:
4636:
4632:
4627:
4621:
4617:
4607:
4604:
4602:
4599:
4597:
4594:
4592:
4589:
4587:
4584:
4582:
4579:
4577:
4574:
4572:
4571:KripkeâPlatek
4569:
4567:
4564:
4560:
4557:
4555:
4552:
4551:
4550:
4547:
4546:
4544:
4540:
4532:
4529:
4528:
4527:
4524:
4522:
4519:
4515:
4512:
4511:
4510:
4507:
4505:
4502:
4500:
4497:
4495:
4492:
4490:
4487:
4484:
4480:
4476:
4473:
4469:
4466:
4464:
4461:
4459:
4456:
4455:
4454:
4450:
4447:
4446:
4444:
4442:
4438:
4434:
4426:
4423:
4421:
4418:
4416:
4415:constructible
4413:
4412:
4411:
4408:
4406:
4403:
4401:
4398:
4396:
4393:
4391:
4388:
4386:
4383:
4381:
4378:
4376:
4373:
4371:
4368:
4366:
4363:
4361:
4358:
4356:
4353:
4351:
4348:
4347:
4345:
4343:
4338:
4330:
4327:
4325:
4322:
4320:
4317:
4315:
4312:
4310:
4307:
4305:
4302:
4301:
4299:
4295:
4292:
4290:
4287:
4286:
4285:
4282:
4280:
4277:
4275:
4272:
4270:
4267:
4265:
4261:
4257:
4255:
4252:
4248:
4245:
4244:
4243:
4240:
4239:
4236:
4233:
4231:
4227:
4217:
4214:
4212:
4209:
4207:
4204:
4202:
4199:
4197:
4194:
4192:
4189:
4185:
4182:
4181:
4180:
4177:
4173:
4168:
4167:
4166:
4163:
4162:
4160:
4158:
4154:
4146:
4143:
4141:
4138:
4136:
4133:
4132:
4131:
4128:
4126:
4123:
4121:
4118:
4116:
4113:
4111:
4108:
4106:
4103:
4101:
4098:
4097:
4095:
4093:
4092:Propositional
4089:
4083:
4080:
4078:
4075:
4073:
4070:
4068:
4065:
4063:
4060:
4058:
4055:
4051:
4048:
4047:
4046:
4043:
4041:
4038:
4036:
4033:
4031:
4028:
4026:
4023:
4021:
4020:Logical truth
4018:
4016:
4013:
4012:
4010:
4008:
4004:
4001:
3999:
3995:
3989:
3986:
3984:
3981:
3979:
3976:
3974:
3971:
3969:
3966:
3964:
3960:
3956:
3952:
3950:
3947:
3945:
3942:
3940:
3936:
3933:
3932:
3930:
3928:
3922:
3917:
3911:
3908:
3906:
3903:
3901:
3898:
3896:
3893:
3891:
3888:
3886:
3883:
3881:
3878:
3876:
3873:
3871:
3868:
3866:
3863:
3861:
3858:
3856:
3853:
3849:
3846:
3845:
3844:
3841:
3840:
3838:
3834:
3830:
3823:
3818:
3816:
3811:
3809:
3804:
3803:
3800:
3792:
3788:
3784:
3782:0-387-98600-6
3778:
3774:
3773:
3767:
3763:
3757:
3753:
3749:
3745:
3740:
3739:
3735:
3725:
3722:
3716:
3713:
3707:
3704:
3698:
3695:
3689:
3686:
3681:
3677:
3673:
3669:
3665:
3661:
3657:
3650:
3647:
3642:
3638:
3634:
3628:
3624:
3620:
3616:
3612:
3605:
3603:
3599:
3593:
3590:
3584:
3581:
3575:
3572:
3567:
3563:
3559:
3553:
3549:
3545:
3540:
3535:
3531:
3524:
3521:
3515:
3510:
3506:
3502:
3498:
3491:
3488:
3483:
3479:
3475:
3473:0-8186-1954-6
3469:
3465:
3461:
3457:
3453:
3446:
3443:
3437:
3434:
3428:
3425:
3419:
3416:
3411:
3407:
3402:
3397:
3393:
3389:
3382:
3379:
3374:
3370:
3366:
3364:9780444105370
3360:
3356:
3352:
3348:
3344:
3340:
3336:
3330:
3327:
3320:
3315:
3289:
3283:
3279:
3274:
3253:
3250:
3226:
3220:
3216:
3195:
3172:
3166:
3158:
3155:
3152:
3129:
3111:
3105:
3079:
3073:
3052:
3031:
3023:
3020:
3017:
2994:
2993:
2992:
2975:
2969:
2943:
2937:
2915:
2898:
2892:
2865:
2859:
2856:
2853:
2830:
2824:
2795:
2789:
2781:
2727:s are either
2712:
2708:
2685:
2681:
2655:
2651:
2647:
2642:
2638:
2632:
2628:
2621:
2618:
2615:
2607:
2603:
2599:
2594:
2590:
2584:
2580:
2550:
2547:
2544:
2538:
2512:
2506:
2503:
2471:
2465:
2459:
2433:
2427:
2424:
2409:
2389:
2383:
2347:
2341:
2318:
2312:
2286:
2280:
2258:
2251:
2249:
2247:
2242:
2222:
2219:
2216:
2210:
2204:
2201:
2198:
2195:
2189:
2183:
2177:
2174:
2171:
2165:
2162:
2156:
2153:
2150:
2144:
2119:
2116:
2113:
2109:
2102:
2099:
2091:
2070:
2067:
2064:
2060:
2053:
2050:
2041:
2024:
2021:
2018:
2012:
1979:
1976:
1973:
1969:
1962:
1959:
1951:
1943:
1941:
1939:
1934:
1901:
1898:
1895:
1889:
1860:
1857:
1854:
1850:
1846:
1841:
1837:
1830:
1810:
1807:
1804:
1784:
1781:
1776:
1772:
1768:
1765:
1762:
1757:
1753:
1727:
1723:
1692:
1689:
1686:
1675:
1672:
1669:
1665:
1627:
1624:
1621:
1618:
1615:
1612:
1609:
1596:
1576:
1547:
1518:
1489:
1460:
1431:
1402:
1373:
1344:
1332:
1323:
1320:
1309:
1303:
1294:
1287:
1263:
1255:
1251:
1246:
1244:
1236:
1234:
1231:
1222:
1220:
1218:
1214:
1208:
1191:
1185:
1182:
1176:
1173:
1170:
1164:
1161:
1155:
1152:
1149:
1143:
1118:
1115:
1112:
1108:
1101:
1098:
1073:
1070:
1067:
1063:
1056:
1053:
1033:
1013:
1001:
999:
997:
992:
990:
986:
982:
978:
960:
956:
933:
929:
915:
898:
890:
887:
884:
880:
856:
848:
844:
823:
815:
813:
811:
807:
802:
786:
782:
757:
753:
748:
710:
706:
676:
670:
667:
662:
659:
656:
652:
640:
639:s is cyclic.
621:
617:
587:
584:
581:
577:
549:
546:
541:
538:
535:
531:
524:
521:
515:
507:
503:
482:
479:
476:
473:
470:
467:
461:
453:
449:
426:
423:
420:
410:
406:
358:
355:
352:
339:
325:
299:
270:
241:
212:
189:
163:
154:
151:
146:
143:
134:
127:
103:
95:
91:
87:
83:
79:
76:
68:
66:
64:
60:
56:
51:
49:
45:
41:
37:
33:
19:
5537:
5335:Ultraproduct
5182:Model theory
5147:Independence
5083:Formal proof
5075:Proof theory
5058:
5031:
4988:real numbers
4960:second-order
4871:Substitution
4748:Metalanguage
4689:conservative
4662:Axiom schema
4606:Constructive
4576:MorseâKelley
4542:Set theories
4521:Aleph number
4514:inaccessible
4420:Grothendieck
4304:intersection
4195:
4191:Higher-order
4179:Second-order
4125:Truth tables
4082:Venn diagram
3865:Formal proof
3775:. Springer.
3771:
3743:
3724:
3715:
3706:
3697:
3688:
3663:
3659:
3649:
3614:
3592:
3583:
3574:
3529:
3523:
3504:
3500:
3490:
3455:
3445:
3436:
3427:
3418:
3391:
3381:
3346:
3342:
3329:
3312:is equal to
3247:is equal to
2916:
2410:
2259:
2255:
2243:
2042:
1949:
1947:
1935:
1597:
1253:
1249:
1247:
1240:
1226:
1216:
1212:
1209:
1005:
993:
984:
916:
821:
819:
805:
803:
641:
340:
85:
81:
77:
72:
52:
35:
29:
5445:Type theory
5393:undecidable
5325:Truth value
5212:equivalence
4891:non-logical
4504:Enumeration
4494:Isomorphism
4441:cardinality
4425:Von Neumann
4390:Ultrafilter
4355:Uncountable
4289:equivalence
4206:Quantifiers
4196:Fixed-point
4165:First-order
4045:Consistency
4030:Proposition
4007:Traditional
3978:Lindström's
3968:Compactness
3910:Type theory
3855:Cardinality
1219:)-formula.
375:variables,
5560:Categories
5256:elementary
4949:arithmetic
4817:Quantifier
4795:functional
4667:Expression
4385:Transitive
4329:identities
4314:complement
4247:hereditary
4230:Set theory
3736:References
3632:0897910990
2673:where the
2252:Iterations
2005:such that
1745:such that
1595:coincide.
441:such that
383:, and let
59:Alfred Aho
5527:Supertask
5430:Recursion
5388:decidable
5222:saturated
5200:of models
5123:deductive
5118:axiomatic
5038:Hilbert's
5025:Euclidean
5006:canonical
4929:axiomatic
4861:Signature
4790:Predicate
4679:Extension
4601:Ackermann
4526:Operation
4405:Universal
4395:Recursive
4370:Singleton
4365:Inhabited
4350:Countable
4340:Types of
4324:power set
4294:partition
4211:Predicate
4157:Predicate
4072:Syllogism
4062:Soundness
4035:Inference
4025:Tautology
3927:paradoxes
3791:901297152
3680:0097-5397
3534:CiteSeerX
3482:206437693
3373:0049-237X
3156:
3021:
2857:∗
2755:∃
2735:∀
2682:ϕ
2652:ϕ
2604:ϕ
2548:∧
2536:∃
2501:∃
2469:⇒
2457:∀
2422:∀
2211:ϕ
2208:¬
2205:∨
2187:∀
2184:∧
2166:ϕ
2145:ψ
2110:ψ
2103:
2061:ϕ
2054:
2013:ϕ
1970:ϕ
1963:
1890:ϕ
1831:ϕ
1666:ϕ
1580:→
1551:→
1522:→
1493:→
1464:→
1435:→
1406:→
1377:→
1348:→
1336:→
1324:φ
1321:
1313:→
1298:→
1183:∨
1165:ϕ
1144:ψ
1109:ψ
1102:
1064:ϕ
1057:
671:φ
668:
585:−
565:(meaning
539:−
525:φ
424:∈
303:→
274:→
245:→
216:→
167:→
155:φ
152:
138:→
5512:Logicism
5505:timeline
5481:Concrete
5340:Validity
5310:T-schema
5303:Kripke's
5298:Tarski's
5293:semantic
5283:Strength
5232:submodel
5227:spectrum
5195:function
5043:Tarski's
5032:Elements
5019:geometry
4975:Robinson
4896:variable
4881:function
4854:spectrum
4844:Sentence
4800:variable
4743:Language
4696:Relation
4657:Automata
4647:Alphabet
4631:language
4485:-jection
4463:codomain
4449:Function
4410:Universe
4380:Infinite
4284:Relation
4067:Validity
4057:Argument
3955:theorem,
3337:(1974).
2817:written
2525:to mean
2446:to mean
1363:, where
977:Immerman
182:, where
5454:Related
5251:Diagram
5149: (
5128:Hilbert
5113:Systems
5108:Theorem
4986:of the
4931:systems
4711:Formula
4706:Grammar
4622: (
4566:General
4279:Forcing
4264:Element
4184:Monadic
3959:paradox
3900:Theorem
3836:General
3641:7503265
3566:7869248
3410:3242505
2914:times.
2305:; here
996:Datalog
836:, then
48:Datalog
5217:finite
4980:Skolem
4933:
4908:Theory
4876:Symbol
4866:String
4849:atomic
4726:ground
4721:closed
4716:atomic
4672:ground
4635:syntax
4531:binary
4458:domain
4375:Finite
4140:finite
3998:Logics
3957:
3905:Theory
3789:
3779:
3758:
3678:
3639:
3629:
3564:
3554:
3536:
3480:
3470:
3408:
3371:
3361:
3314:PSPACE
2137:where
1880:φ
1136:where
826:φ
810:PSPACE
567:φ
385:φ
88:using
73:For a
5207:Model
4955:Peano
4812:Proof
4652:Arity
4581:Naive
4468:image
4400:Fuzzy
4360:Empty
4309:union
4254:Class
3895:Model
3885:Lemma
3843:Axiom
3637:S2CID
3562:S2CID
3478:S2CID
3406:S2CID
3321:Notes
3249:PTIME
2767:. If
1230:arity
981:Vardi
569:with
80:, FO(
5330:Type
5133:list
4937:list
4914:list
4903:Term
4837:rank
4731:open
4625:list
4437:Maps
4342:sets
4201:Free
4171:list
3921:list
3848:list
3787:OCLC
3777:ISBN
3756:ISBN
3676:ISSN
3627:ISBN
3552:ISBN
3468:ISBN
3369:ISSN
3359:ISBN
2490:and
2092:for
1929:and
1921:and
1808:<
1566:and
1450:and
1392:and
1207:.
979:and
495:and
391:and
341:Let
289:and
61:and
5017:of
4999:of
4947:of
4479:Sur
4453:Map
4260:Ur-
4242:Set
3748:doi
3668:doi
3619:doi
3544:doi
3509:doi
3460:doi
3396:doi
3351:doi
3153:log
3018:log
2747:or
2248:.
2088:is
2051:DTC
1960:DTC
1948:FO(
1248:FO(
1211:FO(
1099:PFP
1091:as
1054:IFP
914:).
728:on
653:PFP
338:.
128:PFP
104:PFP
30:In
5562::
5403:NP
5027::
5021::
4951::
4628:),
4483:Bi
4475:In
3785:.
3754:.
3674:.
3664:17
3662:.
3658:.
3635:.
3625:.
3613:.
3601:^
3560:.
3550:.
3542:.
3505:68
3503:.
3499:.
3476:.
3466:.
3454:.
3404:.
3390:.
3367:.
3357:.
3349:.
3347:77
3345:.
3341:.
3051:AC
2408:.
2241:.
2100:TC
2040:.
1938:NL
1933:.
1823:,
1537:,
1508:,
1288:TC
1264:TC
812:.
92:,
50:.
34:,
5483:/
5398:P
5153:)
4939:)
4935:(
4832:â
4827:!
4822:â
4783:=
4778:â
4773:â
4768:â§
4763:âš
4758:ÂŹ
4481:/
4477:/
4451:/
4262:)
4258:(
4145:â
4135:3
3923:)
3821:e
3814:t
3807:v
3793:.
3764:.
3750::
3682:.
3670::
3643:.
3621::
3568:.
3546::
3517:.
3511::
3484:.
3462::
3412:.
3398::
3375:.
3353::
3300:]
3293:)
3290:1
3287:(
3284:O
3280:n
3275:2
3271:[
3266:O
3263:F
3235:]
3230:)
3227:1
3224:(
3221:O
3217:n
3213:[
3208:O
3205:F
3181:]
3176:)
3173:1
3170:(
3167:O
3163:)
3159:n
3150:(
3147:[
3142:O
3139:F
3127:.
3115:)
3112:n
3109:(
3106:t
3086:]
3083:)
3080:n
3077:(
3074:t
3071:[
3066:O
3063:F
3037:]
3032:i
3028:)
3024:n
3015:(
3012:[
3007:O
3004:F
2979:)
2976:n
2973:(
2970:t
2950:]
2947:)
2944:n
2941:(
2938:t
2935:[
2930:O
2927:F
2902:)
2899:n
2896:(
2893:t
2883:k
2869:)
2866:n
2863:(
2860:t
2854:k
2834:)
2831:n
2828:(
2825:t
2815:Q
2799:)
2796:n
2793:(
2790:t
2786:]
2782:Q
2779:[
2769:Q
2713:i
2709:Q
2686:i
2661:)
2656:k
2648:,
2643:k
2639:x
2633:k
2629:Q
2625:(
2622:.
2619:.
2616:.
2613:)
2608:1
2600:,
2595:1
2591:x
2585:1
2581:Q
2577:(
2557:)
2554:)
2551:Q
2545:P
2542:(
2539:x
2533:(
2513:Q
2510:)
2507:P
2504:x
2498:(
2478:)
2475:)
2472:Q
2466:P
2463:(
2460:x
2454:(
2434:Q
2431:)
2428:P
2425:x
2419:(
2396:]
2393:)
2390:n
2387:(
2384:t
2381:[
2376:O
2373:F
2351:)
2348:n
2345:(
2342:t
2322:)
2319:n
2316:(
2313:t
2293:]
2290:)
2287:n
2284:(
2281:t
2278:[
2273:O
2270:F
2246:L
2229:)
2226:)
2223:x
2220:,
2217:u
2214:(
2202:v
2199:=
2196:x
2193:(
2190:x
2181:)
2178:v
2175:,
2172:u
2169:(
2163:=
2160:)
2157:v
2154:,
2151:u
2148:(
2125:)
2120:v
2117:,
2114:u
2106:(
2076:)
2071:v
2068:,
2065:u
2057:(
2028:)
2025:v
2022:,
2019:u
2016:(
2003:v
1999:u
1985:)
1980:v
1977:,
1974:u
1966:(
1950:X
1931:y
1927:x
1923:v
1919:u
1905:)
1902:y
1899:,
1896:x
1893:(
1866:)
1861:1
1858:+
1855:i
1851:z
1847:,
1842:i
1838:z
1834:(
1811:n
1805:i
1785:y
1782:=
1777:n
1773:z
1769:,
1766:x
1763:=
1758:1
1754:z
1733:)
1728:i
1724:z
1720:(
1710:n
1696:)
1693:y
1690:,
1687:x
1684:(
1681:)
1676:v
1673:,
1670:u
1662:(
1657:C
1654:T
1642:k
1628:y
1625:,
1622:x
1619:,
1616:v
1613:,
1610:u
1600:k
1577:t
1548:s
1519:y
1490:x
1461:s
1432:t
1403:y
1374:x
1345:t
1333:s
1327:]
1310:y
1304:,
1295:x
1284:[
1254:X
1250:X
1217:X
1213:X
1195:)
1192:x
1189:(
1186:P
1180:)
1177:x
1174:,
1171:P
1168:(
1162:=
1159:)
1156:x
1153:,
1150:P
1147:(
1124:)
1119:x
1116:,
1113:P
1105:(
1079:)
1074:x
1071:,
1068:P
1060:(
1034:P
1014:P
989:P
985:X
961:k
957:n
934:k
930:n
919:P
902:)
899:x
896:(
891:1
888:+
885:i
881:P
860:)
857:x
854:(
849:i
845:P
834:P
830:P
806:X
787:i
783:P
758:k
754:n
749:2
738:k
734:P
730:y
716:)
711:i
707:P
703:(
683:]
680:)
677:y
674:(
663:x
660:,
657:P
649:[
627:)
622:i
618:P
614:(
604:P
588:1
582:i
578:P
553:)
550:x
547:,
542:1
536:i
532:P
528:(
522:=
519:)
516:x
513:(
508:i
504:P
483:e
480:s
477:l
474:a
471:f
468:=
465:)
462:x
459:(
454:0
450:P
427:N
421:i
417:)
411:i
407:P
403:(
393:P
389:x
381:k
377:P
373:k
359:y
356:,
353:x
343:k
326:P
300:t
271:x
242:t
213:x
190:P
164:t
158:]
147:P
144:,
135:x
124:[
86:X
82:X
78:X
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.