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