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