Knowledge

Kruskal's tree theorem

Source đź“ť

1799: 25: 1786: 826:, but by adding a "gap condition" to the definition of the order on trees above, he found a natural variation of the theorem unprovable in this system. Much later, the Robertson–Seymour theorem would give another theorem unprovable by Π 2589: 1514: 1633: 790:, some special cases and variants of the theorem can be expressed in subsystems of second-order arithmetic much weaker than the subsystems where they can be proved. This was first observed by 1558: 2372: 2055: 2018: 1453: 1416: 3093:
Smith, Rick L. (1985), "The consistency strengths of some finite forms of the Higman and Kruskal theorems", in Harrington, L. A.; Morley, M.; Scedrov, A.; et al. (eds.),
2331: 2284: 2238: 2086: 1858: 1620: 1242: 194: 1945: 1343: 991: 759: 364: 1977: 1375: 2163: 614: 578: 1585: 1017: 719: 2399: 2202: 2116: 1202: 1157: 1120: 1091: 1050: 892: 652: 517: 488: 439: 1303: 951: 1790:
To differentiate the two functions, "TREE" (with all caps) is the big TREE function, and "tree" (with all letters in lowercase) is the weak tree function.
2495: 43: 3084:(1985), "Nonprovability of certain combinatorial properties of finite trees", in Harrington, L. A.; Morley, M.; Scedrov, A.; et al. (eds.), 2937: 4154: 212:
The version given here is that proven by Nash-Williams; Kruskal's formulation is somewhat stronger. All trees we consider are finite.
4199: 4137: 3667: 3123: 3503: 1458: 3984: 1781:{\displaystyle \mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{8}(7)}(7)}(7)}(7)}(7).} 803: 147: 798:
field of reverse mathematics. In the case where the trees above are taken to be unlabeled (that is, in the case where
4120: 3979: 3397: 61: 3974: 3217: 3212: 3207: 3202: 3197: 3192: 3187: 3182: 3610: 2999: 2813: 674:
is well-quasi-ordered under the inf-embeddable order defined above. (That is to say, given any infinite sequence
127: 1519: 3692: 2337: 4204: 4011: 3931: 3432: 3312: 3081: 2424: 158: 3796: 3725: 3605: 3317: 3307: 3247: 2419: 2414: 1164: 787: 154: 91: 4189: 3699: 3687: 3650: 3625: 3600: 3554: 3523: 3262: 3116: 162: 2023: 1986: 1421: 1384: 3996: 3630: 3620: 3496: 3407: 2088:
explodes to a value that is so big that many other "large" combinatorial constants, such as Friedman's
2841: 2291: 2244: 2212: 2060: 1832: 1594: 1216: 168: 161:, a result that has also proved important in reverse mathematics and leads to the even-faster-growing 3969: 3392: 1910: 1308: 956: 724: 329: 4209: 3901: 3528: 3470: 2875:
Internal finite tree embeddings. Reflections on the foundations of mathematics (Stanford, CA, 1998)
1950: 1348: 39: 4149: 4132: 2632: 2123: 846: 779: 143: 4061: 3677: 3465: 3360: 3109: 783: 583: 547: 4194: 4039: 3874: 3865: 3734: 3615: 3569: 3533: 3489: 3427: 3417: 3355: 2790: 2785: 279: 1563: 996: 698: 4127: 4086: 4076: 4066: 3811: 3774: 3764: 3744: 3729: 3074: 3031: 3011: 2972: 2926: 2882: 2462:) is defined as the length of the longest possible sequence that can be constructed with a 2377: 1802:
A sequence of rooted trees labelled from a set of 3 labels (blue < red < green). The
850: 813:
result with a provably impredicative proof. This case of the theorem is still provable by Π
2980: 2178: 2092: 1178: 1133: 1096: 1067: 1026: 868: 628: 493: 464: 415: 8: 4054: 3965: 3911: 3870: 3860: 3749: 3682: 3645: 3302: 1282: 930: 667: 135: 87: 83: 3015: 1818:
By incorporating labels, Friedman defined a far faster-growing function. For a positive
1053: 4166: 4093: 3946: 3855: 3845: 3786: 3704: 3640: 3350: 3252: 3242: 3035: 2960: 2402: 2167: 1588: 1168: 115: 4006: 3097:, Studies in Logic and the Foundations of Mathematics, North-Holland, pp. 119–136 111: 4103: 4081: 3941: 3926: 3906: 3709: 3267: 3088:, Studies in Logic and the Foundations of Mathematics, North-Holland, pp. 87–117 3066: 3039: 2917: 854: 2877:, Lect. Notes Log., vol. 15, Urbana, IL: Assoc. Symbol. Logic, pp. 60–91, 3916: 3769: 3452: 3272: 3222: 3062: 3019: 2952: 2912: 842: 4098: 3881: 3759: 3754: 3739: 3655: 3564: 3549: 3412: 3070: 3027: 2968: 2922: 2878: 2584:{\displaystyle n(1)=3,n(2)=11,\,{\textrm {and}}\,n(3)>2\uparrow ^{7197}158386} 810: 791: 4016: 4001: 3991: 3850: 3828: 3806: 3442: 3333: 3232: 3047: 2933: 1810:
vertices, and no tree is inf-embeddable within any later tree in the sequence.
119: 3023: 4183: 4115: 4071: 4049: 3921: 3791: 3779: 3584: 3402: 3177: 3157: 3132: 2893: 771: 367: 3936: 3818: 3801: 3719: 3559: 3512: 3437: 2889: 1127: 1061: 4142: 3835: 3714: 3579: 3447: 3387: 2171: 220: 75: 4110: 4044: 3885: 3237: 2964: 107: 4161: 4034: 3840: 3343: 3338: 3172: 2287:. Graham's number, for example, is much smaller than the lower bound 2956: 3956: 3823: 3574: 3277: 1798: 200:
application of the theorem gives the existence of the fast-growing
197: 2938:"Well-quasi-ordering, the tree theorem, and Vazsonyi's conjecture" 3167: 1819: 103: 3101: 1814:
is defined to be the longest possible length of such a sequence.
802:
has size one), Friedman found that the result was unprovable in
3481: 3422: 3227: 3162: 2981:"Wqo and bqo theory in subsystems of second order arithmetic" 1159:
in Peano arithmetic grows phenomenally fast as a function of
3095:
Harvey Friedman's Research on the Foundations of Mathematics
3086:
Harvey Friedman's Research on the Foundations of Mathematics
2894:"What's so special about Kruskal's theorem and the ordinal Γ 2756: 778:, Kruskal's tree theorem can be expressed and proven using 1093:
is true, but Peano arithmetic cannot prove the statement "
3152: 1509:{\displaystyle {\text{tree}}(3)\geq 844,424,930,131,960} 3048:"Proof-theoretic investigations on Kruskal's theorem" 2498: 2380: 2340: 2294: 2247: 2215: 2181: 2126: 2095: 2063: 2026: 1989: 1953: 1913: 1835: 1636: 1597: 1566: 1522: 1461: 1424: 1387: 1351: 1311: 1285: 1219: 1181: 1136: 1099: 1070: 1029: 999: 959: 933: 920:
is a finite sequence of unlabeled rooted trees where
871: 845:
confirms the strength of Kruskal's theorem, with the
727: 701: 631: 586: 550: 496: 467: 418: 332: 171: 2631:), taking two arguments, is a particular version of 1052:are true as a consequence of Kruskal's theorem and 34:
may be too technical for most readers to understand
2583: 2393: 2366: 2325: 2278: 2232: 2196: 2157: 2110: 2080: 2049: 2012: 1971: 1939: 1852: 1780: 1614: 1579: 1552: 1508: 1447: 1410: 1369: 1337: 1297: 1236: 1196: 1151: 1114: 1085: 1044: 1011: 985: 945: 886: 753: 713: 646: 608: 572: 511: 482: 433: 358: 188: 153:In 2004, the result was generalized from trees to 2945:Transactions of the American Mathematical Society 90:set of labels is itself well-quasi-ordered under 4181: 3045: 2762: 2466:-letter alphabet such that no block of letters x 3002:(1963), "On well-quasi-ordering finite trees", 2849:Ohio State University Department of Mathematics 670:, then the set of rooted trees with labels in 134:). It has since become a prominent example in 3497: 3117: 3046:Rathjen, Michael; Weiermann, Andreas (1993), 2998: 2951:(2), American Mathematical Society: 210–225, 2442:Friedman originally denoted this function by 1204:holds similarly grows extremely quickly with 540:are any two distinct immediate successors of 131: 1622:(where the argument specifies the number of 794:in the early 1980s, an early success of the 2898:? A survey of some results in proof theory" 138:as a statement that cannot be proved in ATR 4155:Positive cone of a partially ordered group 3504: 3490: 3124: 3110: 1553:{\displaystyle {\text{tree}}(4)\gg g_{64}} 300:are rooted trees with vertices labeled in 2916: 2594: 2549: 2541: 1806:th tree in the sequence contains at most 1244:, the weak tree function, as the largest 1126:". Moreover, the length of the shortest 62:Learn how and when to remove this message 46:, without removing the technical details. 4138:Positive cone of an ordered vector space 2872: 2839: 2811: 2783: 2367:{\displaystyle g_{3\uparrow ^{187196}3}} 1797: 3080: 2978: 2932: 2888: 2170:, are extremely small by comparison. A 1890:of rooted trees labelled from a set of 123: 4182: 2840:Friedman, Harvey M. (8 October 1998), 1270:of unlabeled rooted trees, where each 3485: 3105: 3092: 2607:) taking one argument, is defined as 2595: 2479:is a subsequence of any later block x 860: 853:(sometimes confused with the smaller 809:, thus giving the first example of a 44:make it understandable to non-experts 658:Kruskal's tree theorem then states: 243:if the unique path from the root to 18: 2812:Friedman, Harvey M. (1 June 2000), 2768: 2449: 16:Well-quasi-ordering of finite trees 13: 3665:Properties & Types ( 2784:Friedman, Harvey (28 March 2006), 2436: 2050:{\displaystyle {\text{TREE}}(2)=3} 2013:{\displaystyle {\text{TREE}}(1)=1} 1712: 1709: 1706: 1703: 1696: 1693: 1690: 1687: 1680: 1677: 1674: 1671: 1664: 1661: 1658: 1655: 1648: 1645: 1642: 1639: 1627: 1448:{\displaystyle {\text{tree}}(2)=5} 1411:{\displaystyle {\text{tree}}(1)=2} 765: 148:arithmetical transfinite recursion 14: 4221: 4121:Positive cone of an ordered field 3398:Indefinite and fictitious numbers 3131: 4200:Theorems in discrete mathematics 3975:Ordered topological vector space 3511: 3055:Annals of Pure and Applied Logic 2814:"Enormous Integers In Real Life" 2326:{\displaystyle A^{A(187196)}(1)} 2279:{\displaystyle A^{A(187196)}(1)} 2233:{\displaystyle {\text{TREE}}(3)} 2081:{\displaystyle {\text{TREE}}(3)} 1853:{\displaystyle {\text{TREE}}(n)} 1793: 1615:{\displaystyle {\text{TREE}}(3)} 1237:{\displaystyle {\text{tree}}(n)} 189:{\displaystyle {\text{TREE}}(3)} 23: 2833: 2450: 1940:{\displaystyle T_{i}\leq T_{j}} 1868:so that we have the following: 1338:{\displaystyle T_{i}\leq T_{j}} 1248:so that we have the following: 986:{\displaystyle T_{i}\leq T_{j}} 754:{\displaystyle T_{i}\leq T_{j}} 359:{\displaystyle T_{1}\leq T_{2}} 126:); a short proof was given by 2805: 2777: 2747: 2738: 2729: 2720: 2711: 2569: 2559: 2553: 2529: 2523: 2508: 2502: 2437: 2350: 2320: 2314: 2309: 2303: 2273: 2267: 2262: 2256: 2227: 2221: 2191: 2185: 2152: 2146: 2141: 2135: 2105: 2099: 2075: 2069: 2038: 2032: 2001: 1995: 1847: 1841: 1772: 1766: 1761: 1755: 1750: 1744: 1739: 1733: 1728: 1722: 1609: 1603: 1534: 1528: 1473: 1467: 1436: 1430: 1399: 1393: 1231: 1225: 1191: 1185: 1146: 1140: 1109: 1103: 1080: 1074: 1039: 1033: 881: 875: 641: 635: 603: 590: 567: 554: 506: 500: 477: 471: 428: 422: 263:if additionally the path from 183: 177: 82:states that the set of finite 1: 3932:Series-parallel partial order 3313:Conway chained arrow notation 2699: 3611:Cantor's isomorphism theorem 3067:10.1016/0168-0072(93)90192-G 2918:10.1016/0168-0072(91)90022-E 2873:Friedman, Harvey M. (2002), 2763:Rathjen & Weiermann 1993 2735:Simpson 1985, Definition 4.1 1972:{\displaystyle i<j\leq m} 1370:{\displaystyle i<j\leq m} 1165:primitive recursive function 849:of the theorem equaling the 207: 7: 3651:Szpilrajn extension theorem 3626:Hausdorff maximal principle 3601:Boolean prime ideal theorem 2408: 2158:{\displaystyle n^{n(5)}(5)} 1516:(about 844 trillion), 691:of rooted trees labeled in 10: 4226: 3997:Topological vector lattice 3408:Largest known prime number 3000:Nash-Williams, C. St.J. A. 2851:, pp. 5, 48 (Thm.6.8) 2786:"273:Sigma01/optimal/size" 2744:Simpson 1985, Theorem 5.14 271:contains no other vertex. 97: 4027: 3955: 3894: 3664: 3593: 3542: 3519: 3461: 3393:Extended real number line 3373: 3326: 3308:Knuth's up-arrow notation 3295: 3286: 3139: 3024:10.1017/S0305004100003844 2979:Marcone, Alberto (2001), 2753:Marcone 2001, p. 8–9 2726:Friedman 2002, p. 60 2717:Simpson 1985, Theorem 1.8 2425:Robertson–Seymour theorem 2334:, which is approximately 1983:The TREE sequence begins 1171:, for example. The least 159:Robertson–Seymour theorem 128:Crispin Nash-Williams 3606:Cantor–Bernstein theorem 3318:Steinhaus–Moser notation 2430: 2420:Kanamori–McAloon theorem 2415:Paris–Harrington theorem 788:Paris–Harrington theorem 609:{\displaystyle F(w_{2})} 573:{\displaystyle F(w_{1})} 4150:Partially ordered group 3970:Specialization preorder 2842:"Long Finite Sequences" 2774:Smith 1985, p. 120 847:proof-theoretic ordinal 780:second-order arithmetic 144:second-order arithmetic 3636:Kruskal's tree theorem 3631:Knaster–Tarski theorem 3621:Dushnik–Miller theorem 3361:Fast-growing hierarchy 3004:Proc. Camb. Phil. Soc. 2585: 2395: 2368: 2327: 2280: 2234: 2198: 2159: 2112: 2082: 2051: 2014: 1973: 1947:does not hold for any 1941: 1854: 1815: 1782: 1616: 1581: 1580:{\displaystyle g_{64}} 1554: 1510: 1449: 1412: 1371: 1345:does not hold for any 1339: 1299: 1238: 1198: 1163:, far faster than any 1153: 1116: 1087: 1046: 1013: 1012:{\displaystyle i<j} 987: 947: 888: 763: 755: 715: 714:{\displaystyle i<j} 648: 610: 574: 513: 484: 435: 412:precedes the label of 360: 190: 146:theory with a form of 80:Kruskal's tree theorem 3418:Long and short scales 3356:Grzegorczyk hierarchy 2905:Ann. Pure Appl. Logic 2821:Ohio State University 2791:Ohio State University 2586: 2396: 2394:{\displaystyle g_{x}} 2369: 2328: 2281: 2235: 2209:weak lower bound for 2199: 2160: 2113: 2083: 2052: 2015: 1974: 1942: 1855: 1801: 1783: 1617: 1582: 1555: 1511: 1450: 1413: 1372: 1340: 1300: 1239: 1199: 1154: 1117: 1088: 1047: 1014: 988: 948: 889: 756: 716: 660: 649: 611: 575: 544:, then the path from 514: 485: 436: 373:from the vertices of 361: 280:partially ordered set 223:, and given vertices 191: 4205:Trees (graph theory) 4128:Ordered vector space 2633:Ackermann's function 2496: 2378: 2338: 2292: 2245: 2213: 2197:{\displaystyle n(4)} 2179: 2124: 2111:{\displaystyle n(4)} 2093: 2061: 2024: 1987: 1951: 1911: 1907:vertices, such that 1872:There is a sequence 1833: 1634: 1595: 1564: 1520: 1459: 1422: 1385: 1349: 1309: 1305:vertices, such that 1283: 1252:There is a sequence 1217: 1197:{\displaystyle P(n)} 1179: 1152:{\displaystyle P(n)} 1134: 1115:{\displaystyle P(n)} 1097: 1086:{\displaystyle P(n)} 1068: 1045:{\displaystyle P(n)} 1027: 997: 957: 931: 887:{\displaystyle P(n)} 869: 851:small Veblen ordinal 725: 699: 647:{\displaystyle F(v)} 629: 584: 548: 512:{\displaystyle F(v)} 494: 483:{\displaystyle F(w)} 465: 448:is any successor of 434:{\displaystyle F(v)} 416: 330: 169: 3966:Alexandrov topology 3912:Lexicographic order 3871:Well-quasi-ordering 3433:Orders of magnitude 3303:Scientific notation 3082:Simpson, Stephen G. 3016:1963PCPS...59..833N 2988:Reverse Mathematics 2793:Department of Maths 1894:labels, where each 1298:{\displaystyle i+n} 1023:All the statements 946:{\displaystyle i+n} 784:Goodstein's theorem 382:to the vertices of 257:immediate successor 136:reverse mathematics 4190:Mathematical logic 3947:Transitive closure 3907:Converse/Transpose 3616:Dilworth's theorem 3351:Ackermann function 2581: 2391: 2364: 2323: 2276: 2230: 2194: 2155: 2108: 2078: 2047: 2010: 1969: 1937: 1860:to be the largest 1850: 1816: 1778: 1612: 1577: 1550: 1506: 1445: 1408: 1367: 1335: 1295: 1234: 1194: 1169:Ackermann function 1149: 1112: 1083: 1042: 1009: 983: 943: 894:is the statement: 884: 861:Weak tree function 751: 711: 668:well-quasi-ordered 644: 606: 570: 509: 490:is a successor of 480: 431: 356: 186: 120:Joseph Kruskal 88:well-quasi-ordered 4175: 4174: 4133:Partially ordered 3942:Symmetric closure 3927:Reflexive closure 3670: 3479: 3478: 3369: 3368: 2546: 2403:Graham's function 2219: 2205:, and, hence, an 2067: 2057:, then suddenly, 2030: 1993: 1839: 1630:) is larger than 1601: 1526: 1465: 1428: 1391: 1381:It is known that 1223: 855:Ackermann ordinal 395:For all vertices 175: 72: 71: 64: 4217: 3917:Linear extension 3666: 3646:Mirsky's theorem 3506: 3499: 3492: 3483: 3482: 3293: 3292: 3223:Eddington number 3168:Hundred thousand 3126: 3119: 3112: 3103: 3102: 3098: 3089: 3077: 3052: 3042: 2995: 2985: 2975: 2942: 2929: 2920: 2902: 2890:Gallier, Jean H. 2885: 2860: 2859: 2858: 2856: 2846: 2837: 2831: 2830: 2829: 2827: 2818: 2809: 2803: 2802: 2801: 2799: 2781: 2775: 2772: 2766: 2760: 2754: 2751: 2745: 2742: 2736: 2733: 2727: 2724: 2718: 2715: 2599: 2590: 2588: 2587: 2582: 2577: 2576: 2548: 2547: 2544: 2454: 2441: 2400: 2398: 2397: 2392: 2390: 2389: 2373: 2371: 2370: 2365: 2363: 2362: 2358: 2357: 2332: 2330: 2329: 2324: 2313: 2312: 2285: 2283: 2282: 2277: 2266: 2265: 2239: 2237: 2236: 2231: 2220: 2217: 2203: 2201: 2200: 2195: 2164: 2162: 2161: 2156: 2145: 2144: 2117: 2115: 2114: 2109: 2087: 2085: 2084: 2079: 2068: 2065: 2056: 2054: 2053: 2048: 2031: 2028: 2019: 2017: 2016: 2011: 1994: 1991: 1978: 1976: 1975: 1970: 1946: 1944: 1943: 1938: 1936: 1935: 1923: 1922: 1906: 1901: 1893: 1889: 1865: 1859: 1857: 1856: 1851: 1840: 1837: 1826: 1813: 1809: 1805: 1787: 1785: 1784: 1779: 1765: 1764: 1754: 1753: 1743: 1742: 1732: 1731: 1721: 1720: 1715: 1699: 1683: 1667: 1651: 1621: 1619: 1618: 1613: 1602: 1599: 1586: 1584: 1583: 1578: 1576: 1575: 1559: 1557: 1556: 1551: 1549: 1548: 1527: 1524: 1515: 1513: 1512: 1507: 1466: 1463: 1454: 1452: 1451: 1446: 1429: 1426: 1417: 1415: 1414: 1409: 1392: 1389: 1376: 1374: 1373: 1368: 1344: 1342: 1341: 1336: 1334: 1333: 1321: 1320: 1304: 1302: 1301: 1296: 1277: 1269: 1247: 1243: 1241: 1240: 1235: 1224: 1221: 1208: 1203: 1201: 1200: 1195: 1174: 1162: 1158: 1156: 1155: 1150: 1125: 1122:is true for all 1121: 1119: 1118: 1113: 1092: 1090: 1089: 1084: 1062:Peano arithmetic 1059: 1051: 1049: 1048: 1043: 1018: 1016: 1015: 1010: 992: 990: 989: 984: 982: 981: 969: 968: 952: 950: 949: 944: 926: 919: 901: 893: 891: 890: 885: 843:Ordinal analysis 834: 833: 821: 820: 801: 797: 782:. However, like 777: 760: 758: 757: 752: 750: 749: 737: 736: 720: 718: 717: 712: 695:, there is some 694: 690: 673: 665: 653: 651: 650: 645: 624: 615: 613: 612: 607: 602: 601: 579: 577: 576: 571: 566: 565: 543: 539: 530: 518: 516: 515: 510: 489: 487: 486: 481: 460: 451: 447: 440: 438: 437: 432: 411: 407: 398: 390: 381: 372: 365: 363: 362: 357: 355: 354: 342: 341: 325: 312: 303: 299: 290: 277: 270: 266: 262: 254: 250: 246: 242: 234: 230: 226: 218: 195: 193: 192: 187: 176: 173: 67: 60: 56: 53: 47: 27: 26: 19: 4225: 4224: 4220: 4219: 4218: 4216: 4215: 4214: 4210:Wellfoundedness 4180: 4179: 4176: 4171: 4167:Young's lattice 4023: 3951: 3890: 3740:Heyting algebra 3688:Boolean algebra 3660: 3641:Laver's theorem 3589: 3555:Boolean algebra 3550:Binary relation 3538: 3515: 3510: 3480: 3475: 3457: 3413:List of numbers 3381: 3379: 3377: 3375: 3365: 3322: 3288: 3282: 3253:Graham's number 3243:Skewes's number 3145: 3143: 3141: 3135: 3130: 3050: 2983: 2957:10.2307/1993287 2940: 2900: 2897: 2864: 2863: 2854: 2852: 2844: 2838: 2834: 2825: 2823: 2816: 2810: 2806: 2797: 2795: 2782: 2778: 2773: 2769: 2761: 2757: 2752: 2748: 2743: 2739: 2734: 2730: 2725: 2721: 2716: 2712: 2702: 2572: 2568: 2543: 2542: 2497: 2494: 2493: 2491: 2484: 2478: 2471: 2433: 2411: 2385: 2381: 2379: 2376: 2375: 2353: 2349: 2345: 2341: 2339: 2336: 2335: 2299: 2295: 2293: 2290: 2289: 2252: 2248: 2246: 2243: 2242: 2216: 2214: 2211: 2210: 2180: 2177: 2176: 2168:Graham's number 2131: 2127: 2125: 2122: 2121: 2094: 2091: 2090: 2064: 2062: 2059: 2058: 2027: 2025: 2022: 2021: 1990: 1988: 1985: 1984: 1952: 1949: 1948: 1931: 1927: 1918: 1914: 1912: 1909: 1908: 1904: 1900: 1896: 1891: 1888: 1879: 1873: 1866: 1863: 1836: 1834: 1831: 1830: 1827: 1824: 1811: 1807: 1803: 1796: 1716: 1702: 1701: 1700: 1686: 1685: 1684: 1670: 1669: 1668: 1654: 1653: 1652: 1638: 1637: 1635: 1632: 1631: 1598: 1596: 1593: 1592: 1589:Graham's number 1571: 1567: 1565: 1562: 1561: 1544: 1540: 1523: 1521: 1518: 1517: 1462: 1460: 1457: 1456: 1425: 1423: 1420: 1419: 1388: 1386: 1383: 1382: 1350: 1347: 1346: 1329: 1325: 1316: 1312: 1310: 1307: 1306: 1284: 1281: 1280: 1276: 1272: 1268: 1259: 1253: 1245: 1220: 1218: 1215: 1214: 1206: 1180: 1177: 1176: 1172: 1160: 1135: 1132: 1131: 1123: 1098: 1095: 1094: 1069: 1066: 1065: 1064:can prove that 1057: 1028: 1025: 1024: 998: 995: 994: 977: 973: 964: 960: 958: 955: 954: 953:vertices, then 932: 929: 928: 925: 921: 918: 909: 903: 899: 870: 867: 866: 863: 838: 832: 829: 828: 827: 825: 819: 816: 815: 814: 807: 799: 795: 792:Harvey Friedman 775: 768: 766:Friedman's work 745: 741: 732: 728: 726: 723: 722: 700: 697: 696: 692: 688: 681: 675: 671: 663: 630: 627: 626: 623: 617: 597: 593: 585: 582: 581: 561: 557: 549: 546: 545: 541: 538: 532: 529: 523: 495: 492: 491: 466: 463: 462: 459: 453: 449: 445: 417: 414: 413: 409: 408:, the label of 406: 400: 396: 389: 383: 380: 374: 370: 366:if there is an 350: 346: 337: 333: 331: 328: 327: 324: 318: 311: 305: 301: 298: 292: 289: 283: 275: 268: 264: 260: 252: 248: 244: 240: 232: 228: 224: 216: 210: 172: 170: 167: 166: 165:, which dwarfs 141: 112:Andrew Vázsonyi 100: 68: 57: 51: 48: 40:help improve it 37: 28: 24: 17: 12: 11: 5: 4223: 4213: 4212: 4207: 4202: 4197: 4192: 4173: 4172: 4170: 4169: 4164: 4159: 4158: 4157: 4147: 4146: 4145: 4140: 4135: 4125: 4124: 4123: 4113: 4108: 4107: 4106: 4101: 4094:Order morphism 4091: 4090: 4089: 4079: 4074: 4069: 4064: 4059: 4058: 4057: 4047: 4042: 4037: 4031: 4029: 4025: 4024: 4022: 4021: 4020: 4019: 4014: 4012:Locally convex 4009: 4004: 3994: 3992:Order topology 3989: 3988: 3987: 3985:Order topology 3982: 3972: 3962: 3960: 3953: 3952: 3950: 3949: 3944: 3939: 3934: 3929: 3924: 3919: 3914: 3909: 3904: 3898: 3896: 3892: 3891: 3889: 3888: 3878: 3868: 3863: 3858: 3853: 3848: 3843: 3838: 3833: 3832: 3831: 3821: 3816: 3815: 3814: 3809: 3804: 3799: 3797:Chain-complete 3789: 3784: 3783: 3782: 3777: 3772: 3767: 3762: 3752: 3747: 3742: 3737: 3732: 3722: 3717: 3712: 3707: 3702: 3697: 3696: 3695: 3685: 3680: 3674: 3672: 3662: 3661: 3659: 3658: 3653: 3648: 3643: 3638: 3633: 3628: 3623: 3618: 3613: 3608: 3603: 3597: 3595: 3591: 3590: 3588: 3587: 3582: 3577: 3572: 3567: 3562: 3557: 3552: 3546: 3544: 3540: 3539: 3537: 3536: 3531: 3526: 3520: 3517: 3516: 3509: 3508: 3501: 3494: 3486: 3477: 3476: 3474: 3473: 3468: 3462: 3459: 3458: 3456: 3455: 3450: 3445: 3443:Power of three 3440: 3435: 3430: 3425: 3423:Number systems 3420: 3415: 3410: 3405: 3400: 3395: 3390: 3384: 3382: 3378:(alphabetical 3371: 3370: 3367: 3366: 3364: 3363: 3358: 3353: 3348: 3347: 3346: 3341: 3334:Hyperoperation 3330: 3328: 3324: 3323: 3321: 3320: 3315: 3310: 3305: 3299: 3297: 3290: 3284: 3283: 3281: 3280: 3275: 3270: 3265: 3260: 3255: 3250: 3248:Moser's number 3245: 3240: 3235: 3233:Shannon number 3230: 3225: 3220: 3215: 3210: 3205: 3200: 3195: 3190: 3185: 3180: 3175: 3170: 3165: 3160: 3155: 3149: 3147: 3137: 3136: 3129: 3128: 3121: 3114: 3106: 3100: 3099: 3090: 3078: 3043: 3010:(4): 833–835, 2996: 2976: 2934:Kruskal, J. B. 2930: 2911:(3): 199–260, 2895: 2886: 2862: 2861: 2832: 2804: 2776: 2767: 2755: 2746: 2737: 2728: 2719: 2709: 2708: 2701: 2698: 2697: 2696: 2592: 2580: 2575: 2571: 2567: 2564: 2561: 2558: 2555: 2552: 2540: 2537: 2534: 2531: 2528: 2525: 2522: 2519: 2516: 2513: 2510: 2507: 2504: 2501: 2486: 2480: 2473: 2467: 2447: 2432: 2429: 2428: 2427: 2422: 2417: 2410: 2407: 2388: 2384: 2361: 2356: 2352: 2348: 2344: 2322: 2319: 2316: 2311: 2308: 2305: 2302: 2298: 2275: 2272: 2269: 2264: 2261: 2258: 2255: 2251: 2229: 2226: 2223: 2193: 2190: 2187: 2184: 2154: 2151: 2148: 2143: 2140: 2137: 2134: 2130: 2107: 2104: 2101: 2098: 2077: 2074: 2071: 2046: 2043: 2040: 2037: 2034: 2009: 2006: 2003: 2000: 1997: 1981: 1980: 1968: 1965: 1962: 1959: 1956: 1934: 1930: 1926: 1921: 1917: 1898: 1884: 1877: 1862: 1849: 1846: 1843: 1823: 1795: 1792: 1777: 1774: 1771: 1768: 1763: 1760: 1757: 1752: 1749: 1746: 1741: 1738: 1735: 1730: 1727: 1724: 1719: 1714: 1711: 1708: 1705: 1698: 1695: 1692: 1689: 1682: 1679: 1676: 1673: 1666: 1663: 1660: 1657: 1650: 1647: 1644: 1641: 1611: 1608: 1605: 1574: 1570: 1547: 1543: 1539: 1536: 1533: 1530: 1505: 1502: 1499: 1496: 1493: 1490: 1487: 1484: 1481: 1478: 1475: 1472: 1469: 1444: 1441: 1438: 1435: 1432: 1407: 1404: 1401: 1398: 1395: 1379: 1378: 1366: 1363: 1360: 1357: 1354: 1332: 1328: 1324: 1319: 1315: 1294: 1291: 1288: 1274: 1264: 1257: 1233: 1230: 1227: 1193: 1190: 1187: 1184: 1148: 1145: 1142: 1139: 1111: 1108: 1105: 1102: 1082: 1079: 1076: 1073: 1041: 1038: 1035: 1032: 1021: 1020: 1008: 1005: 1002: 980: 976: 972: 967: 963: 942: 939: 936: 923: 914: 907: 898:There is some 883: 880: 877: 874: 862: 859: 836: 830: 823: 817: 805: 767: 764: 748: 744: 740: 735: 731: 710: 707: 704: 686: 679: 656: 655: 643: 640: 637: 634: 621: 605: 600: 596: 592: 589: 569: 564: 560: 556: 553: 536: 527: 520: 508: 505: 502: 499: 479: 476: 473: 470: 457: 442: 430: 427: 424: 421: 404: 387: 378: 353: 349: 345: 340: 336: 322: 315:inf-embeddable 309: 304:, we say that 296: 287: 209: 206: 185: 182: 179: 139: 99: 96: 70: 69: 31: 29: 22: 15: 9: 6: 4: 3: 2: 4222: 4211: 4208: 4206: 4203: 4201: 4198: 4196: 4193: 4191: 4188: 4187: 4185: 4178: 4168: 4165: 4163: 4160: 4156: 4153: 4152: 4151: 4148: 4144: 4141: 4139: 4136: 4134: 4131: 4130: 4129: 4126: 4122: 4119: 4118: 4117: 4116:Ordered field 4114: 4112: 4109: 4105: 4102: 4100: 4097: 4096: 4095: 4092: 4088: 4085: 4084: 4083: 4080: 4078: 4075: 4073: 4072:Hasse diagram 4070: 4068: 4065: 4063: 4060: 4056: 4053: 4052: 4051: 4050:Comparability 4048: 4046: 4043: 4041: 4038: 4036: 4033: 4032: 4030: 4026: 4018: 4015: 4013: 4010: 4008: 4005: 4003: 4000: 3999: 3998: 3995: 3993: 3990: 3986: 3983: 3981: 3978: 3977: 3976: 3973: 3971: 3967: 3964: 3963: 3961: 3958: 3954: 3948: 3945: 3943: 3940: 3938: 3935: 3933: 3930: 3928: 3925: 3923: 3922:Product order 3920: 3918: 3915: 3913: 3910: 3908: 3905: 3903: 3900: 3899: 3897: 3895:Constructions 3893: 3887: 3883: 3879: 3876: 3872: 3869: 3867: 3864: 3862: 3859: 3857: 3854: 3852: 3849: 3847: 3844: 3842: 3839: 3837: 3834: 3830: 3827: 3826: 3825: 3822: 3820: 3817: 3813: 3810: 3808: 3805: 3803: 3800: 3798: 3795: 3794: 3793: 3792:Partial order 3790: 3788: 3785: 3781: 3780:Join and meet 3778: 3776: 3773: 3771: 3768: 3766: 3763: 3761: 3758: 3757: 3756: 3753: 3751: 3748: 3746: 3743: 3741: 3738: 3736: 3733: 3731: 3727: 3723: 3721: 3718: 3716: 3713: 3711: 3708: 3706: 3703: 3701: 3698: 3694: 3691: 3690: 3689: 3686: 3684: 3681: 3679: 3678:Antisymmetric 3676: 3675: 3673: 3669: 3663: 3657: 3654: 3652: 3649: 3647: 3644: 3642: 3639: 3637: 3634: 3632: 3629: 3627: 3624: 3622: 3619: 3617: 3614: 3612: 3609: 3607: 3604: 3602: 3599: 3598: 3596: 3592: 3586: 3585:Weak ordering 3583: 3581: 3578: 3576: 3573: 3571: 3570:Partial order 3568: 3566: 3563: 3561: 3558: 3556: 3553: 3551: 3548: 3547: 3545: 3541: 3535: 3532: 3530: 3527: 3525: 3522: 3521: 3518: 3514: 3507: 3502: 3500: 3495: 3493: 3488: 3487: 3484: 3472: 3469: 3467: 3464: 3463: 3460: 3454: 3451: 3449: 3446: 3444: 3441: 3439: 3436: 3434: 3431: 3429: 3426: 3424: 3421: 3419: 3416: 3414: 3411: 3409: 3406: 3404: 3403:Infinitesimal 3401: 3399: 3396: 3394: 3391: 3389: 3386: 3385: 3383: 3372: 3362: 3359: 3357: 3354: 3352: 3349: 3345: 3342: 3340: 3337: 3336: 3335: 3332: 3331: 3329: 3325: 3319: 3316: 3314: 3311: 3309: 3306: 3304: 3301: 3300: 3298: 3294: 3291: 3285: 3279: 3276: 3274: 3273:Rayo's number 3271: 3269: 3266: 3264: 3261: 3259: 3256: 3254: 3251: 3249: 3246: 3244: 3241: 3239: 3236: 3234: 3231: 3229: 3226: 3224: 3221: 3219: 3216: 3214: 3211: 3209: 3206: 3204: 3201: 3199: 3196: 3194: 3191: 3189: 3186: 3184: 3181: 3179: 3176: 3174: 3171: 3169: 3166: 3164: 3161: 3159: 3156: 3154: 3151: 3150: 3148: 3138: 3134: 3133:Large numbers 3127: 3122: 3120: 3115: 3113: 3108: 3107: 3104: 3096: 3091: 3087: 3083: 3079: 3076: 3072: 3068: 3064: 3060: 3056: 3049: 3044: 3041: 3037: 3033: 3029: 3025: 3021: 3017: 3013: 3009: 3005: 3001: 2997: 2993: 2989: 2982: 2977: 2974: 2970: 2966: 2962: 2958: 2954: 2950: 2946: 2939: 2935: 2931: 2928: 2924: 2919: 2914: 2910: 2906: 2899: 2891: 2887: 2884: 2880: 2876: 2871: 2870: 2869: 2868: 2850: 2843: 2836: 2822: 2815: 2808: 2794: 2792: 2787: 2780: 2771: 2764: 2759: 2750: 2741: 2732: 2723: 2714: 2710: 2707: 2706: 2694: 2690: 2686: 2682: 2678: 2674: 2670: 2666: 2662: 2658: 2654: 2650: 2646: 2642: 2638: 2634: 2630: 2626: 2622: 2618: 2614: 2610: 2606: 2602: 2598: 2597: 2593: 2578: 2573: 2565: 2562: 2556: 2550: 2538: 2535: 2532: 2526: 2520: 2517: 2514: 2511: 2505: 2499: 2490: 2483: 2477: 2470: 2465: 2461: 2457: 2453: 2452: 2448: 2445: 2440: 2439: 2435: 2434: 2426: 2423: 2421: 2418: 2416: 2413: 2412: 2406: 2404: 2386: 2382: 2359: 2354: 2346: 2342: 2333: 2317: 2306: 2300: 2296: 2286: 2270: 2259: 2253: 2249: 2224: 2208: 2204: 2188: 2182: 2173: 2169: 2165: 2149: 2138: 2132: 2128: 2118: 2102: 2096: 2072: 2044: 2041: 2035: 2007: 2004: 1998: 1966: 1963: 1960: 1957: 1954: 1932: 1928: 1924: 1919: 1915: 1902: 1887: 1883: 1876: 1871: 1870: 1869: 1867: 1844: 1828: 1821: 1800: 1794:TREE function 1791: 1788: 1775: 1769: 1758: 1747: 1736: 1725: 1717: 1629: 1625: 1606: 1590: 1572: 1568: 1545: 1541: 1537: 1531: 1503: 1500: 1497: 1494: 1491: 1488: 1485: 1482: 1479: 1476: 1470: 1442: 1439: 1433: 1405: 1402: 1396: 1364: 1361: 1358: 1355: 1352: 1330: 1326: 1322: 1317: 1313: 1292: 1289: 1286: 1278: 1267: 1263: 1256: 1251: 1250: 1249: 1228: 1211: 1209: 1188: 1182: 1170: 1166: 1143: 1137: 1129: 1106: 1100: 1077: 1071: 1063: 1055: 1054:KĹ‘nig's lemma 1036: 1030: 1006: 1003: 1000: 978: 974: 970: 965: 961: 940: 937: 934: 917: 913: 906: 902:such that if 897: 896: 895: 878: 872: 865:Suppose that 858: 856: 852: 848: 844: 840: 812: 808: 793: 789: 785: 781: 773: 762: 746: 742: 738: 733: 729: 708: 705: 702: 685: 678: 669: 659: 638: 632: 620: 598: 594: 587: 562: 558: 551: 535: 526: 521: 503: 497: 474: 468: 456: 443: 425: 419: 403: 394: 393: 392: 386: 377: 369: 368:injective map 351: 347: 343: 338: 334: 321: 316: 308: 295: 286: 281: 272: 258: 238: 222: 215:Given a tree 213: 205: 203: 202:TREE function 199: 180: 164: 163:SSCG function 160: 156: 151: 149: 145: 137: 133: 129: 125: 121: 117: 113: 109: 105: 95: 93: 89: 85: 81: 77: 66: 63: 55: 45: 41: 35: 32:This article 30: 21: 20: 4195:Order theory 4177: 3959:& Orders 3937:Star product 3866:Well-founded 3819:Prefix order 3775:Distributive 3765:Complemented 3735:Foundational 3700:Completeness 3656:Zorn's lemma 3635: 3560:Cyclic order 3543:Key concepts 3513:Order theory 3438:Power of two 3428:Number names 3257: 3163:Ten thousand 3094: 3085: 3061:(1): 49–88, 3058: 3054: 3007: 3003: 2991: 2987: 2948: 2944: 2936:(May 1960), 2908: 2904: 2874: 2867:Bibliography 2866: 2865: 2853:, retrieved 2848: 2835: 2824:, retrieved 2820: 2807: 2796:, retrieved 2789: 2779: 2770: 2758: 2749: 2740: 2731: 2722: 2713: 2704: 2703: 2692: 2688: 2684: 2680: 2676: 2672: 2668: 2664: 2660: 2656: 2652: 2648: 2644: 2640: 2636: 2635:defined as: 2628: 2624: 2620: 2616: 2612: 2608: 2604: 2600: 2596: 2488: 2481: 2475: 2468: 2463: 2459: 2455: 2451: 2443: 2438: 2288: 2241: 2206: 2175: 2120: 2089: 1982: 1903:has at most 1895: 1885: 1881: 1874: 1861: 1822: 1817: 1789: 1623: 1380: 1279:has at most 1271: 1265: 1261: 1254: 1212: 1205: 1022: 915: 911: 904: 864: 841: 796:then-nascent 769: 683: 676: 661: 657: 618: 533: 524: 454: 401: 384: 375: 319: 314: 306: 293: 284: 273: 256: 236: 214: 211: 201: 152: 101: 94:embedding. 92:homeomorphic 79: 73: 58: 49: 33: 4143:Riesz space 4104:Isomorphism 3980:Normal cone 3902:Composition 3836:Semilattice 3745:Homogeneous 3730:Equivalence 3580:Total order 3448:Power of 10 3388:Busy beaver 3193:Quintillion 3188:Quadrillion 2172:lower bound 1056:. For each 811:predicative 391:such that: 251:, and call 108:conjectured 76:mathematics 4184:Categories 4111:Order type 4045:Cofinality 3886:Well-order 3861:Transitive 3750:Idempotent 3683:Asymmetric 3453:Sagan Unit 3287:Expression 3238:Googolplex 3203:Septillion 3198:Sextillion 3144:numerical 2700:References 1175:for which 774:label set 326:and write 4162:Upper set 4099:Embedding 4035:Antichain 3856:Tolerance 3846:Symmetric 3841:Semiorder 3787:Reflexive 3705:Connected 3344:Pentation 3339:Tetration 3327:Operators 3296:Notations 3218:Decillion 3213:Nonillion 3208:Octillion 3140:Examples 3040:251095188 2994:: 303–330 2705:Citations 2655:+1, 1) = 2619:), where 2570:↑ 2351:↑ 2207:extremely 1964:≤ 1925:≤ 1538:≫ 1477:≥ 1362:≤ 1323:≤ 993:for some 971:≤ 772:countable 739:≤ 625:contains 344:≤ 247:contains 237:successor 208:Statement 52:June 2024 3957:Topology 3824:Preorder 3807:Eulerian 3770:Complete 3720:Directed 3710:Covering 3575:Preorder 3534:Category 3529:Glossary 3376:articles 3374:Related 3278:Infinity 3183:Trillion 3158:Thousand 2892:(1991), 2855:8 August 2826:8 August 2798:8 August 2409:See also 2374:, where 721:so that 278:to be a 198:finitary 4062:Duality 4040:Cofinal 4028:Related 4007:FrĂ©chet 3884:)  3760:Bounded 3755:Lattice 3728:)  3726:Partial 3594:Results 3565:Lattice 3471:History 3289:methods 3263:SSCG(3) 3258:TREE(3) 3178:Billion 3173:Million 3153:Hundred 3075:1212407 3032:0153601 3012:Bibcode 2973:0111704 2965:1993287 2927:1129778 2883:1943303 1880:, ..., 1829:, take 1820:integer 1812:TREE(3) 1591:), and 1560:(where 1260:, ..., 1213:Define 1167:or the 910:, ..., 786:or the 461:, then 231:, call 219:with a 157:as the 130: ( 122: ( 104:theorem 98:History 86:over a 38:Please 4087:Subnet 4067:Filter 4017:Normed 4002:Banach 3968:& 3875:Better 3812:Strict 3802:Graded 3693:topics 3524:Topics 3380:order) 3228:Googol 3073:  3038:  3030:  2971:  2963:  2925:  2881:  2675:+1) = 2663:, 1), 2579:158386 2485:,...,x 2472:,...,x 2355:187196 2307:187196 2260:187196 2166:, and 1626:; see 1624:labels 770:For a 155:graphs 116:proved 4077:Ideal 4055:Graph 3851:Total 3829:Total 3715:Dense 3466:Names 3268:BH(3) 3146:order 3051:(PDF) 3036:S2CID 2984:(PDF) 2961:JSTOR 2941:(PDF) 2901:(PDF) 2845:(PDF) 2817:(PDF) 2643:) = 2 2431:Notes 2240:, is 1628:below 1128:proof 519:; and 282:. If 274:Take 84:trees 3668:list 2857:2017 2828:2017 2800:2017 2691:+1, 2671:+1, 2639:(1, 2574:7197 2563:> 2218:TREE 2174:for 2066:TREE 2029:TREE 1992:TREE 1958:< 1838:TREE 1600:TREE 1525:tree 1464:tree 1427:tree 1390:tree 1356:< 1222:tree 1004:< 927:has 706:< 221:root 196:. A 174:TREE 132:1963 124:1960 114:and 106:was 102:The 4082:Net 3882:Pre 3063:doi 3020:doi 2953:doi 2913:doi 2695:)). 2545:and 2401:is 1587:is 1504:960 1498:131 1492:930 1486:424 1480:844 1130:of 857:). 835:-CA 822:-CA 804:ATR 689:, … 666:is 662:If 616:in 580:to 522:If 452:in 444:If 399:of 317:in 313:is 267:to 259:of 255:an 239:of 150:). 142:(a 118:by 110:by 74:In 42:to 4186:: 3142:in 3071:MR 3069:, 3059:60 3057:, 3053:, 3034:, 3028:MR 3026:, 3018:, 3008:59 3006:, 2992:21 2990:, 2986:, 2969:MR 2967:, 2959:, 2949:95 2947:, 2943:, 2923:MR 2921:, 2909:53 2907:, 2903:, 2879:MR 2847:, 2819:, 2788:, 2683:, 2647:, 2627:, 2615:, 2536:11 2492:. 2444:TR 2405:. 2119:, 2020:, 1573:64 1546:64 1455:, 1418:, 1210:. 1060:, 839:. 761:.) 682:, 531:, 291:, 235:a 227:, 204:. 78:, 3880:( 3877:) 3873:( 3724:( 3671:) 3505:e 3498:t 3491:v 3125:e 3118:t 3111:v 3065:: 3022:: 3014:: 2955:: 2915:: 2896:0 2765:. 2693:n 2689:k 2687:( 2685:A 2681:k 2679:( 2677:A 2673:n 2669:k 2667:( 2665:A 2661:k 2659:( 2657:A 2653:k 2651:( 2649:A 2645:n 2641:n 2637:A 2629:n 2625:k 2623:( 2621:A 2617:x 2613:x 2611:( 2609:A 2605:x 2603:( 2601:A 2591:. 2566:2 2560:) 2557:3 2554:( 2551:n 2539:, 2533:= 2530:) 2527:2 2524:( 2521:n 2518:, 2515:3 2512:= 2509:) 2506:1 2503:( 2500:n 2489:j 2487:2 2482:j 2476:i 2474:2 2469:i 2464:k 2460:k 2458:( 2456:n 2446:. 2387:x 2383:g 2360:3 2347:3 2343:g 2321:) 2318:1 2315:( 2310:) 2304:( 2301:A 2297:A 2274:) 2271:1 2268:( 2263:) 2257:( 2254:A 2250:A 2228:) 2225:3 2222:( 2192:) 2189:4 2186:( 2183:n 2153:) 2150:5 2147:( 2142:) 2139:5 2136:( 2133:n 2129:n 2106:) 2103:4 2100:( 2097:n 2076:) 2073:3 2070:( 2045:3 2042:= 2039:) 2036:2 2033:( 2008:1 2005:= 2002:) 1999:1 1996:( 1979:. 1967:m 1961:j 1955:i 1933:j 1929:T 1920:i 1916:T 1905:i 1899:i 1897:T 1892:n 1886:m 1882:T 1878:1 1875:T 1864:m 1848:) 1845:n 1842:( 1825:n 1808:n 1804:n 1776:. 1773:) 1770:7 1767:( 1762:) 1759:7 1756:( 1751:) 1748:7 1745:( 1740:) 1737:7 1734:( 1729:) 1726:7 1723:( 1718:8 1713:e 1710:e 1707:r 1704:t 1697:e 1694:e 1691:r 1688:t 1681:e 1678:e 1675:r 1672:t 1665:e 1662:e 1659:r 1656:t 1649:e 1646:e 1643:r 1640:t 1610:) 1607:3 1604:( 1569:g 1542:g 1535:) 1532:4 1529:( 1501:, 1495:, 1489:, 1483:, 1474:) 1471:3 1468:( 1443:5 1440:= 1437:) 1434:2 1431:( 1406:2 1403:= 1400:) 1397:1 1394:( 1377:. 1365:m 1359:j 1353:i 1331:j 1327:T 1318:i 1314:T 1293:n 1290:+ 1287:i 1275:i 1273:T 1266:m 1262:T 1258:1 1255:T 1246:m 1232:) 1229:n 1226:( 1207:n 1192:) 1189:n 1186:( 1183:P 1173:m 1161:n 1147:) 1144:n 1141:( 1138:P 1124:n 1110:) 1107:n 1104:( 1101:P 1081:) 1078:n 1075:( 1072:P 1058:n 1040:) 1037:n 1034:( 1031:P 1019:. 1007:j 1001:i 979:j 975:T 966:i 962:T 941:n 938:+ 935:i 924:i 922:T 916:m 912:T 908:1 905:T 900:m 882:) 879:n 876:( 873:P 837:0 831:1 824:0 818:1 806:0 800:X 776:X 747:j 743:T 734:i 730:T 709:j 703:i 693:X 687:2 684:T 680:1 677:T 672:X 664:X 654:. 642:) 639:v 636:( 633:F 622:2 619:T 604:) 599:2 595:w 591:( 588:F 568:) 563:1 559:w 555:( 552:F 542:v 537:2 534:w 528:1 525:w 507:) 504:v 501:( 498:F 478:) 475:w 472:( 469:F 458:1 455:T 450:v 446:w 441:; 429:) 426:v 423:( 420:F 410:v 405:1 402:T 397:v 388:2 385:T 379:1 376:T 371:F 352:2 348:T 339:1 335:T 323:2 320:T 310:1 307:T 302:X 297:2 294:T 288:1 285:T 276:X 269:w 265:v 261:v 253:w 249:v 245:w 241:v 233:w 229:w 225:v 217:T 184:) 181:3 178:( 140:0 65:) 59:( 54:) 50:( 36:.

Index

help improve it
make it understandable to non-experts
Learn how and when to remove this message
mathematics
trees
well-quasi-ordered
homeomorphic
theorem
conjectured
Andrew Vázsonyi
proved
Joseph Kruskal
1960
Crispin Nash-Williams
1963
reverse mathematics
second-order arithmetic
arithmetical transfinite recursion
graphs
Robertson–Seymour theorem
SSCG function
finitary
root
partially ordered set
injective map
well-quasi-ordered
countable
second-order arithmetic
Goodstein's theorem
Paris–Harrington theorem

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.

↑