89:
2007:. Although the axiom of choice is, in general, stronger than the principle of dependent choice, this restriction of dependent choice is equivalent to a restriction of the axiom of choice. In particular, when the branching at each node is done on a finite subset of an arbitrary set not assumed to be countable, the form of Kőnig's lemma that says "Every infinite finitely branching tree has an infinite path" is equivalent to the principle that every countable set of finite sets has a choice function, that is to say, the axiom of countable choice for finite sets. This form of the axiom of choice (and hence of Kőnig's lemma) is not provable in ZF set theory.
32:
1903:. At each step of the induction, a vertex with a particular property must be selected. Although it is proved that at least one appropriate vertex exists, if there is more than one suitable vertex there may be no canonical choice. In fact, the full strength of the axiom of dependent choice is not needed; as described below, the
344:, consider the infinitely many vertices that can be reached by simple paths that extend the current path, and for each of these vertices construct a simple path to it that extends the current path. There are infinitely many of these extended paths, each of which connects from
239:
that meets the conditions of the lemma, can be performed step by step, maintaining at each step a finite path that can be extended to reach infinitely many vertices (not necessarily all along the same path as each other). To begin this process, start with any single vertex
1838:
of the fan theorem can be taken to be the length of the longest sequence whose basic open set is in the finite subcover. This topological proof can be used in classical mathematics to show that the following form of Kőnig's lemma holds: for any natural number
498:
Repeating this process for extending the path produces an infinite sequence of finite simple paths, each extending the previous path in the sequence by one more edge. The union of all of these paths is the ray whose existence was promised by the lemma.
2180:
591:
the tree whose nodes are all finite sequences of natural numbers, where the parent of a node is obtained by removing the last element from a sequence. Each finite sequence can be identified with a partial function from
1531:. Here a binary tree is one in which every term of every sequence in the tree is 0 or 1, which is to say the tree is computably bounded via the constant function 2. The full form of Kőnig's lemma is not provable in WKL
115:
who published it in 1927. It gives a sufficient condition for an infinite graph to have an infinitely long path. The computability aspects of this theorem have been thoroughly investigated by researchers in
2192:
507:
The computability aspects of Kőnig's lemma have been thoroughly investigated. For this purpose it is convenient to state Kőnig's lemma in the form that any infinite finitely branching subtree of
1910:
If the graph is countable, the vertices are well-ordered and one can canonically choose the smallest suitable vertex. In this case, Kőnig's lemma is provable in second-order arithmetic with
1889:
1834:. Each sequence in the bar represents a basic open set of this space, and these basic open sets cover the space by assumption. By compactness, this cover has a finite subcover. The
172:. This means that every two vertices can be connected by a finite path, each vertex is adjacent to only finitely many other vertices, and the graph has infinitely many vertices. Then
1119:
980:
948:
916:
834:
762:
1622:
1399:
1208:
1051:
1013:
884:
730:
677:
643:
589:
535:
1832:
211:
or an infinite simple path. If it is locally finite, it meets the conditions of the lemma and has a ray, and if it is not locally finite then it has an infinite-degree vertex.
1151:
2337:
1087:
267:. This vertex can be thought of as a path of length zero, consisting of one vertex and no edges. By the assumptions of the lemma, each of the infinitely many vertices of
1766:
1734:
1678:
1646:
1493:
1428:
1276:
1256:
610:
555:
493:
433:
460:
396:
369:
342:
312:
265:
1345:
88:
2005:
1979:
1959:
1939:
1786:
1714:
1513:
1473:
1365:
1316:
1296:
1236:
1175:
854:
802:
782:
700:
285:
237:
190:
158:
1555:
to establish that there exists an adjacent vertex from which infinitely many other vertices can be reached, and because of the reliance on a weak form of the
1688:
if every sequence is either in the bar or not in the bar (this assumption is required because the theorem is ordinarily considered in situations where the
612:
to itself, and each infinite path can be identified with a total function. This allows for an analysis using the techniques of computability theory.
1559:. Facts about the computational aspects of the lemma suggest that no proof can be given that would be considered constructive by the main schools of
20:
2533:
2283:
2023:
of any inverse system of non-empty finite sets is non-empty. This may be seen as a generalization of Kőnig's lemma and can be proved with
645:
in which each sequence has only finitely many immediate extensions (that is, the tree has finite degree when viewed as a graph) is called
53:
1899:
Kőnig's lemma may be considered to be a choice principle; the first proof above illustrates the relationship between the lemma and the
2459:
2430:
2362:
2237:
2218:
1519:
A weak form of Kőnig's lemma which states that every infinite binary tree has an infinite branch is used to define the subsystem WKL
75:
495:. This extension preserves the property that infinitely many vertices can be reached by simple paths that extend the current path.
1915:
2508:
169:
165:
2513:
1368:
2117:
2028:
1567:
1548:
200:(a path with no repeated vertices) that starts at one vertex and continues from it through infinitely many vertices.
46:
40:
1911:
1846:
1689:
679:
has an infinite path, but Kőnig's lemma shows that any finitely branching infinite subtree must have such a path.
1904:
1900:
57:
2528:
2523:
2518:
1560:
125:
402:
that at least one of these neighbors is used as the next step on infinitely many of these extended paths. Let
1092:
953:
921:
889:
807:
735:
1524:
1585:
1374:
1183:
1026:
988:
859:
705:
652:
618:
564:
510:
2024:
1016:
2491:
has completely formalized and automatically checked the proof of a version of Kőnig's lemma in the file
208:
1798:
2452:
Recursively
Enumerable Sets and Degrees: A study of computable functions and computably generated sets
2266:(1976), "Some cases of König's lemma", in Marek, V. Wiktor; Srebrny, Marian; Zarach, Andrzej (eds.),
1552:
1154:
1124:
1020:
399:
2043:, for the possible existence of counterexamples when generalizing the lemma to higher cardinalities.
2244:
1528:
1438:
204:
197:
2310:
2171:, Mathematical Surveys and Monographs, vol. 59, Providence, RI: American Mathematical Society
1921:
Kőnig's lemma is essentially the restriction of the axiom of dependent choice to entire relations
1060:
2152:
193:
117:
2346:
2340:
1452:. This means that any function computable from the path is dominated by a computable function.
2482:
2455:
2426:
2409:
2379:
2358:
2279:
2233:
2214:
2176:
1442:
112:
2414:
Theorie der
Endlichen und Unendlichen Graphen: Kombinatorische Topologie der Streckenkomplexe
1739:
1719:
1651:
1631:
1478:
1261:
1241:
595:
540:
465:
405:
2398:
2350:
2271:
2144:
2016:
1791:
This can be proven in a classical setting by considering the bar as an open covering of the
121:
2469:
2440:
2372:
2293:
2256:
2228:
438:
374:
347:
320:
290:
243:
2465:
2447:
2436:
2368:
2289:
2252:
2224:
1556:
1431:
1321:
161:
1984:
1408:
2206:
2040:
1964:
1944:
1924:
1771:
1699:
1575:
1498:
1458:
1350:
1301:
1281:
1221:
1160:
839:
787:
767:
685:
558:
270:
222:
175:
143:
2354:
2502:
2164:
2156:
2020:
1792:
1054:
2383:
2488:
129:
108:
1180:
A finer analysis has been conducted for computably bounded trees. A subtree of
2263:
2135:
Franchella, Miriam (1997), "On the origins of Dénes König's infinity lemma",
2046:
2402:
2270:, Lecture Notes in Mathematics, vol. 537, Springer, pp. 273–284,
435:
be such a neighbor, and extend the current path by one edge, the edge from
2492:
2027:, viewing the finite sets as compact discrete spaces, and then using the
398:
has only finitely many neighbors. Therefore, it follows by a form of the
2275:
2268:
Set Theory and
Hierarchy Theory a Memorial Tribute to Andrzej Mostowski
2148:
104:
1788:. Brouwer's fan theorem says that any detachable bar is uniform.
1278:
such that for every sequence in the tree and every natural number
87:
1371:
apply to infinite, computably bounded, computable subtrees of
25:
2483:
Stanford
Encyclopedia of Philosophy: Constructive Mathematics
985:
There exist non-finitely branching computable subtrees of
203:
A useful special case of the lemma is that every infinite
2249:
Theory of
Recursive Functions and Effective Computability
2181:"Über eine Schlussweise aus dem Endlichen ins Unendliche"
1768:
has an initial segment in the bar of length no more than
1367:
gives a bound for how "wide" the tree is. The following
1547:
The proof given above is not generally considered to be
1543:
Relationship to constructive mathematics and compactness
1430:, the canonical Turing complete set that can decide the
317:
Next, as long as the current path ends at some vertex
2313:
1987:
1967:
1947:
1927:
1849:
1801:
1774:
1742:
1722:
1702:
1654:
1634:
1588:
1501:
1481:
1461:
1411:
1377:
1353:
1324:
1304:
1284:
1264:
1244:
1224:
1186:
1163:
1127:
1095:
1063:
1029:
991:
956:
924:
892:
862:
842:
810:
790:
770:
738:
708:
688:
655:
621:
598:
567:
557:
denotes the set of natural numbers (thought of as an
543:
513:
468:
441:
408:
377:
350:
323:
293:
273:
246:
225:
178:
146:
784:
through which there is an infinite path. Even when
2384:"Sur les correspondances multivoques des ensembles"
982:ensures that this greedy process cannot get stuck.
2331:
1999:
1973:
1953:
1933:
1883:
1826:
1780:
1760:
1728:
1708:
1672:
1640:
1616:
1507:
1487:
1467:
1422:
1393:
1359:
1339:
1310:
1290:
1270:
1250:
1230:
1202:
1169:
1145:
1113:
1081:
1045:
1007:
974:
942:
910:
886:has an infinite path, the path is computable from
878:
848:
828:
796:
776:
756:
724:
694:
671:
637:
604:
583:
549:
529:
487:
454:
427:
390:
363:
336:
306:
279:
259:
231:
184:
152:
1535:, but is equivalent to the stronger subsystem ACA
918:, step by step, greedily choosing a successor in
287:can be reached by a simple path that starts from
2454:, Perspectives in Mathematical Logic, Springer,
2425:, Perspectives in Mathematical Logic, Springer,
1495:the tree has a path that does not compute
1884:{\displaystyle \{0,\ldots ,k\}^{<\omega }}
1053:with a path must have a path computable from
8:
1869:
1850:
1815:
1802:
1755:
1743:
1667:
1655:
1602:
1589:
1023:path. However, every computable subtree of
124:. This theorem also has important roles in
2096:
1527:. This subsystem has an important role in
836:may not be computable. Whenever a subtree
2069:
1574:) is, from a classical point of view, the
2323:
2318:
2312:
2122:On the Domains of Definition of Functions
1986:
1966:
1946:
1926:
1872:
1848:
1818:
1800:
1773:
1741:
1721:
1701:
1653:
1633:
1605:
1587:
1500:
1480:
1460:
1410:
1405:Any such tree has a path computable from
1382:
1376:
1352:
1323:
1303:
1283:
1263:
1243:
1223:
1191:
1185:
1162:
1137:
1132:
1126:
1094:
1073:
1068:
1062:
1034:
1028:
996:
990:
955:
923:
891:
867:
861:
841:
809:
789:
769:
737:
713:
707:
687:
660:
654:
626:
620:
597:
572:
566:
542:
518:
512:
473:
467:
446:
440:
413:
407:
382:
376:
355:
349:
328:
322:
298:
292:
272:
251:
245:
224:
177:
145:
76:Learn how and when to remove this message
39:This article includes a list of general
2058:
1571:
1153:(for the meaning of this notation, see
1114:{\displaystyle \operatorname {Ext} (T)}
1089:complete set. This is because the set
975:{\displaystyle \operatorname {Ext} (T)}
943:{\displaystyle \operatorname {Ext} (T)}
911:{\displaystyle \operatorname {Ext} (T)}
829:{\displaystyle \operatorname {Ext} (T)}
757:{\displaystyle \operatorname {Ext} (T)}
2080:
1578:of a form of Kőnig's lemma. A subset
1318:th element of the sequence is at most
219:The construction of a ray, in a graph
2423:Subsystems of Second Order Arithmetic
2137:Archive for History of Exact Sciences
2092:
2065:
1895:Relationship with the axiom of choice
1617:{\displaystyle \{0,1\}^{<\omega }}
1394:{\displaystyle \omega ^{<\omega }}
1203:{\displaystyle \omega ^{<\omega }}
1046:{\displaystyle \omega ^{<\omega }}
1008:{\displaystyle \omega ^{<\omega }}
879:{\displaystyle \omega ^{<\omega }}
725:{\displaystyle \omega ^{<\omega }}
672:{\displaystyle \omega ^{<\omega }}
638:{\displaystyle \omega ^{<\omega }}
584:{\displaystyle \omega ^{<\omega }}
530:{\displaystyle \omega ^{<\omega }}
207:contains either a vertex of infinite
16:Mathematical result on infinite trees
7:
2100:
2169:Consequences of the Axiom of Choice
1843:, any infinite subtree of the tree
111:due to the Hungarian mathematician
2416:(in German), Leipzig: Akad. Verlag
2339:classes in computability theory",
2315:
2127:van Heijenoort, Jean, ed. (1967),
1218:if there is a computable function
1129:
1065:
45:it lacks sufficient corresponding
14:
2031:characterization of compactness.
1827:{\displaystyle \{0,1\}^{\omega }}
1551:, because at each step it uses a
1448:Any such tree has a path that is
1437:Any such tree has a path that is
950:at each step. The restriction to
649:. Not every infinite subtree of
2342:Handbook of Computability Theory
30:
21:König's theorem (disambiguation)
1146:{\displaystyle \Sigma _{1}^{1}}
2191:(2–3): 121–130, archived from
1334:
1328:
1108:
1102:
969:
963:
937:
931:
905:
899:
823:
817:
751:
745:
1:
2355:10.1016/S0049-237X(99)80018-4
1961:there are only finitely many
1455:For any noncomputable subset
537:has an infinite path. Here
371:to one of its neighbors, but
2534:Constructivism (mathematics)
2421:Simpson, Stephen G. (1999),
2332:{\displaystyle \Pi _{1}^{0}}
2029:finite intersection property
1692:is not assumed). A bar is
1680:has some initial segment in
1082:{\displaystyle \Pi _{1}^{1}}
764:denotes the set of nodes of
2550:
1912:arithmetical comprehension
1716:so that any function from
1690:law of the excluded middle
18:
2307:Cenzer, Douglas (1999), "
2097:Howard & Rubin (1998)
1905:axiom of countable choice
1901:axiom of dependent choice
2232:; reprint, Dover, 2002,
2185:Acta Sci. Math. (Szeged)
1696:if there is some number
1561:constructive mathematics
1441:. This is known as the
126:constructive mathematics
92:Kőnig's 1927 publication
2391:Fundamenta Mathematicae
2099:, pp. 20, 243; compare
1761:{\displaystyle \{0,1\}}
1729:{\displaystyle \omega }
1673:{\displaystyle \{0,1\}}
1641:{\displaystyle \omega }
1525:second-order arithmetic
1488:{\displaystyle \omega }
1271:{\displaystyle \omega }
1251:{\displaystyle \omega }
605:{\displaystyle \omega }
550:{\displaystyle \omega }
488:{\displaystyle v_{i+1}}
428:{\displaystyle v_{i+1}}
60:more precise citations.
2509:Lemmas in graph theory
2403:10.4064/fm-8-1-114-134
2333:
2001:
1975:
1955:
1935:
1914:, and, a fortiori, in
1891:has an infinite path.
1885:
1828:
1782:
1762:
1730:
1710:
1674:
1642:
1618:
1553:proof by contradiction
1509:
1489:
1469:
1424:
1395:
1361:
1341:
1312:
1292:
1272:
1252:
1232:
1204:
1171:
1147:
1115:
1083:
1047:
1009:
976:
944:
912:
880:
850:
830:
804:is computable the set
798:
778:
758:
726:
696:
673:
639:
606:
585:
551:
531:
489:
456:
429:
392:
365:
338:
308:
281:
261:
233:
186:
154:
136:Statement of the lemma
101:Kőnig's infinity lemma
93:
2345:, Elsevier, pp.
2334:
2002:
1976:
1956:
1936:
1886:
1829:
1783:
1763:
1731:
1711:
1675:
1643:
1628:if any function from
1619:
1510:
1490:
1470:
1425:
1396:
1362:
1342:
1313:
1293:
1273:
1253:
1233:
1205:
1172:
1148:
1116:
1084:
1048:
1010:
977:
945:
913:
881:
851:
831:
799:
779:
759:
727:
697:
674:
640:
607:
586:
552:
532:
503:Computability aspects
490:
457:
455:{\displaystyle v_{i}}
430:
393:
391:{\displaystyle v_{i}}
366:
364:{\displaystyle v_{i}}
339:
337:{\displaystyle v_{i}}
309:
307:{\displaystyle v_{1}}
282:
262:
260:{\displaystyle v_{1}}
234:
187:
155:
91:
2514:Computability theory
2311:
2143:(51(1)3:2-3): 3–27,
1985:
1965:
1945:
1925:
1847:
1799:
1772:
1740:
1720:
1700:
1652:
1632:
1586:
1568:L. E. J. Brouwer
1499:
1479:
1459:
1409:
1375:
1351:
1340:{\displaystyle f(n)}
1322:
1302:
1282:
1262:
1242:
1222:
1184:
1161:
1155:analytical hierarchy
1125:
1093:
1061:
1027:
1019:path, and indeed no
989:
954:
922:
890:
860:
840:
808:
788:
768:
736:
706:
686:
653:
619:
596:
565:
541:
511:
466:
439:
406:
400:pigeonhole principle
375:
348:
321:
291:
271:
244:
223:
176:
144:
122:computability theory
19:For other uses, see
2328:
2245:Rogers, Hartley Jr.
2129:From Frege to Gödel
2103:, Exercise IX.2.18.
2025:Tychonoff's theorem
2000:{\displaystyle xRz}
1941:such that for each
1566:The fan theorem of
1529:reverse mathematics
1216:recursively bounded
1142:
1078:
2329:
2314:
2276:10.1007/BFb0096907
2149:10.1007/BF00376449
1997:
1971:
1951:
1931:
1918:(without choice).
1881:
1824:
1795:topological space
1778:
1758:
1726:
1706:
1670:
1638:
1614:
1505:
1485:
1465:
1423:{\displaystyle 0'}
1420:
1391:
1357:
1337:
1308:
1288:
1268:
1248:
1228:
1212:computably bounded
1200:
1167:
1143:
1128:
1111:
1079:
1064:
1043:
1005:
972:
940:
908:
876:
846:
826:
794:
774:
754:
722:
692:
669:
647:finitely branching
635:
602:
581:
547:
527:
485:
452:
425:
388:
361:
334:
304:
277:
257:
229:
182:
150:
118:mathematical logic
94:
2285:978-3-540-07856-2
2118:Brouwer, L. E. J.
2070:Franchella (1997)
1974:{\displaystyle z}
1954:{\displaystyle x}
1934:{\displaystyle R}
1781:{\displaystyle N}
1709:{\displaystyle N}
1508:{\displaystyle X}
1468:{\displaystyle X}
1443:low basis theorem
1360:{\displaystyle f}
1311:{\displaystyle n}
1291:{\displaystyle n}
1231:{\displaystyle f}
1170:{\displaystyle T}
1021:hyperarithmetical
849:{\displaystyle T}
797:{\displaystyle T}
777:{\displaystyle T}
695:{\displaystyle T}
280:{\displaystyle G}
232:{\displaystyle G}
185:{\displaystyle G}
153:{\displaystyle G}
86:
85:
78:
2541:
2472:
2448:Soare, Robert I.
2443:
2417:
2405:
2388:
2375:
2338:
2336:
2335:
2330:
2327:
2322:
2296:
2259:
2231:
2211:Basic Set Theory
2202:
2201:
2200:
2172:
2159:
2131:
2124:
2104:
2090:
2084:
2083:, p. 418ff.
2078:
2072:
2068:as explained in
2063:
2017:category of sets
2006:
2004:
2003:
1998:
1980:
1978:
1977:
1972:
1960:
1958:
1957:
1952:
1940:
1938:
1937:
1932:
1890:
1888:
1887:
1882:
1880:
1879:
1833:
1831:
1830:
1825:
1823:
1822:
1787:
1785:
1784:
1779:
1767:
1765:
1764:
1759:
1735:
1733:
1732:
1727:
1715:
1713:
1712:
1707:
1679:
1677:
1676:
1671:
1647:
1645:
1644:
1639:
1623:
1621:
1620:
1615:
1613:
1612:
1514:
1512:
1511:
1506:
1494:
1492:
1491:
1486:
1474:
1472:
1471:
1466:
1450:hyperimmune free
1429:
1427:
1426:
1421:
1419:
1400:
1398:
1397:
1392:
1390:
1389:
1366:
1364:
1363:
1358:
1346:
1344:
1343:
1338:
1317:
1315:
1314:
1309:
1297:
1295:
1294:
1289:
1277:
1275:
1274:
1269:
1257:
1255:
1254:
1249:
1237:
1235:
1234:
1229:
1209:
1207:
1206:
1201:
1199:
1198:
1176:
1174:
1173:
1168:
1152:
1150:
1149:
1144:
1141:
1136:
1120:
1118:
1117:
1112:
1088:
1086:
1085:
1080:
1077:
1072:
1057:, the canonical
1052:
1050:
1049:
1044:
1042:
1041:
1014:
1012:
1011:
1006:
1004:
1003:
981:
979:
978:
973:
949:
947:
946:
941:
917:
915:
914:
909:
885:
883:
882:
877:
875:
874:
855:
853:
852:
847:
835:
833:
832:
827:
803:
801:
800:
795:
783:
781:
780:
775:
763:
761:
760:
755:
731:
729:
728:
723:
721:
720:
701:
699:
698:
693:
682:For any subtree
678:
676:
675:
670:
668:
667:
644:
642:
641:
636:
634:
633:
611:
609:
608:
603:
590:
588:
587:
582:
580:
579:
556:
554:
553:
548:
536:
534:
533:
528:
526:
525:
494:
492:
491:
486:
484:
483:
461:
459:
458:
453:
451:
450:
434:
432:
431:
426:
424:
423:
397:
395:
394:
389:
387:
386:
370:
368:
367:
362:
360:
359:
343:
341:
340:
335:
333:
332:
313:
311:
310:
305:
303:
302:
286:
284:
283:
278:
266:
264:
263:
258:
256:
255:
238:
236:
235:
230:
191:
189:
188:
183:
159:
157:
156:
151:
120:, especially in
81:
74:
70:
67:
61:
56:this article by
47:inline citations
34:
33:
26:
2549:
2548:
2544:
2543:
2542:
2540:
2539:
2538:
2529:Infinite graphs
2524:Axiom of choice
2519:Wellfoundedness
2499:
2498:
2479:
2462:
2446:
2433:
2420:
2408:
2386:
2378:
2365:
2309:
2308:
2306:
2303:
2301:Further reading
2286:
2262:
2251:, McGraw-Hill,
2243:
2221:
2205:
2198:
2196:
2175:
2162:
2134:
2126:
2125:. published in
2116:
2113:
2108:
2107:
2095:, p. 273;
2091:
2087:
2079:
2075:
2064:
2060:
2055:
2037:
2013:
1983:
1982:
1963:
1962:
1943:
1942:
1923:
1922:
1897:
1868:
1845:
1844:
1814:
1797:
1796:
1770:
1769:
1738:
1737:
1718:
1717:
1698:
1697:
1650:
1649:
1630:
1629:
1601:
1584:
1583:
1557:axiom of choice
1545:
1538:
1534:
1522:
1497:
1496:
1477:
1476:
1457:
1456:
1432:halting problem
1412:
1407:
1406:
1378:
1373:
1372:
1349:
1348:
1320:
1319:
1300:
1299:
1280:
1279:
1260:
1259:
1240:
1239:
1220:
1219:
1187:
1182:
1181:
1177:is computable.
1159:
1158:
1123:
1122:
1091:
1090:
1059:
1058:
1030:
1025:
1024:
992:
987:
986:
952:
951:
920:
919:
888:
887:
863:
858:
857:
838:
837:
806:
805:
786:
785:
766:
765:
734:
733:
709:
704:
703:
684:
683:
656:
651:
650:
622:
617:
616:
594:
593:
568:
563:
562:
539:
538:
514:
509:
508:
505:
469:
464:
463:
442:
437:
436:
409:
404:
403:
378:
373:
372:
351:
346:
345:
324:
319:
318:
294:
289:
288:
269:
268:
247:
242:
241:
221:
220:
217:
174:
173:
142:
141:
138:
82:
71:
65:
62:
52:Please help to
51:
35:
31:
24:
17:
12:
11:
5:
2547:
2545:
2537:
2536:
2531:
2526:
2521:
2516:
2511:
2501:
2500:
2497:
2496:
2485:
2478:
2477:External links
2475:
2474:
2473:
2460:
2444:
2431:
2418:
2406:
2397:(8): 114–134,
2376:
2363:
2326:
2321:
2317:
2302:
2299:
2298:
2297:
2284:
2260:
2241:
2219:
2203:
2173:
2163:Howard, Paul;
2160:
2132:
2112:
2109:
2106:
2105:
2085:
2073:
2057:
2056:
2054:
2051:
2050:
2049:
2044:
2041:Aronszajn tree
2036:
2033:
2012:
2011:Generalization
2009:
1996:
1993:
1990:
1970:
1950:
1930:
1896:
1893:
1878:
1875:
1871:
1867:
1864:
1861:
1858:
1855:
1852:
1821:
1817:
1813:
1810:
1807:
1804:
1777:
1757:
1754:
1751:
1748:
1745:
1725:
1705:
1669:
1666:
1663:
1660:
1657:
1637:
1611:
1608:
1604:
1600:
1597:
1594:
1591:
1576:contrapositive
1544:
1541:
1536:
1532:
1520:
1517:
1516:
1504:
1484:
1464:
1453:
1446:
1435:
1418:
1415:
1388:
1385:
1381:
1369:basis theorems
1356:
1336:
1333:
1330:
1327:
1307:
1287:
1267:
1247:
1227:
1197:
1194:
1190:
1166:
1140:
1135:
1131:
1110:
1107:
1104:
1101:
1098:
1076:
1071:
1067:
1040:
1037:
1033:
1002:
999:
995:
971:
968:
965:
962:
959:
939:
936:
933:
930:
927:
907:
904:
901:
898:
895:
873:
870:
866:
845:
825:
822:
819:
816:
813:
793:
773:
753:
750:
747:
744:
741:
719:
716:
712:
691:
666:
663:
659:
632:
629:
625:
601:
578:
575:
571:
559:ordinal number
546:
524:
521:
517:
504:
501:
482:
479:
476:
472:
449:
445:
422:
419:
416:
412:
385:
381:
358:
354:
331:
327:
301:
297:
276:
254:
250:
228:
216:
213:
181:
170:infinite graph
166:locally finite
149:
137:
134:
84:
83:
38:
36:
29:
15:
13:
10:
9:
6:
4:
3:
2:
2546:
2535:
2532:
2530:
2527:
2525:
2522:
2520:
2517:
2515:
2512:
2510:
2507:
2506:
2504:
2494:
2490:
2489:Mizar project
2486:
2484:
2481:
2480:
2476:
2471:
2467:
2463:
2461:3-540-15299-7
2457:
2453:
2449:
2445:
2442:
2438:
2434:
2432:3-540-64882-8
2428:
2424:
2419:
2415:
2411:
2407:
2404:
2400:
2396:
2393:(in French),
2392:
2385:
2381:
2377:
2374:
2370:
2366:
2364:0-444-89882-4
2360:
2356:
2352:
2348:
2344:
2343:
2324:
2319:
2305:
2304:
2300:
2295:
2291:
2287:
2281:
2277:
2273:
2269:
2265:
2261:
2258:
2254:
2250:
2246:
2242:
2239:
2238:0-486-42079-5
2235:
2230:
2226:
2222:
2220:3-540-08417-7
2216:
2212:
2208:
2204:
2195:on 2014-12-23
2194:
2190:
2187:(in German),
2186:
2182:
2178:
2174:
2170:
2166:
2161:
2158:
2154:
2150:
2146:
2142:
2138:
2133:
2130:
2123:
2119:
2115:
2114:
2110:
2102:
2098:
2094:
2089:
2086:
2082:
2081:Rogers (1967)
2077:
2074:
2071:
2067:
2062:
2059:
2052:
2048:
2045:
2042:
2039:
2038:
2034:
2032:
2030:
2026:
2022:
2021:inverse limit
2018:
2010:
2008:
1994:
1991:
1988:
1968:
1948:
1928:
1919:
1917:
1916:ZF set theory
1913:
1908:
1906:
1902:
1894:
1892:
1876:
1873:
1865:
1862:
1859:
1856:
1853:
1842:
1837:
1819:
1811:
1808:
1805:
1794:
1789:
1775:
1752:
1749:
1746:
1723:
1703:
1695:
1691:
1687:
1683:
1664:
1661:
1658:
1635:
1627:
1609:
1606:
1598:
1595:
1592:
1581:
1577:
1573:
1569:
1564:
1562:
1558:
1554:
1550:
1542:
1540:
1530:
1526:
1502:
1482:
1462:
1454:
1451:
1447:
1444:
1440:
1436:
1433:
1416:
1413:
1404:
1403:
1402:
1386:
1383:
1379:
1370:
1354:
1331:
1325:
1305:
1285:
1265:
1245:
1225:
1217:
1213:
1195:
1192:
1188:
1178:
1164:
1156:
1138:
1133:
1105:
1099:
1096:
1074:
1069:
1056:
1038:
1035:
1031:
1022:
1018:
1015:that have no
1000:
997:
993:
983:
966:
960:
957:
934:
928:
925:
902:
896:
893:
871:
868:
864:
843:
820:
814:
811:
791:
771:
748:
742:
739:
732:the notation
717:
714:
710:
689:
680:
664:
661:
657:
648:
630:
627:
623:
615:A subtree of
613:
599:
576:
573:
569:
560:
544:
522:
519:
515:
502:
500:
496:
480:
477:
474:
470:
447:
443:
420:
417:
414:
410:
401:
383:
379:
356:
352:
329:
325:
315:
299:
295:
274:
252:
248:
226:
214:
212:
210:
206:
201:
199:
195:
179:
171:
167:
163:
147:
135:
133:
131:
127:
123:
119:
114:
110:
106:
102:
98:
97:Kőnig's lemma
90:
80:
77:
69:
66:February 2021
59:
55:
49:
48:
42:
37:
28:
27:
22:
2451:
2422:
2413:
2394:
2390:
2341:
2267:
2248:
2213:, Springer,
2210:
2207:Lévy, Azriel
2197:, retrieved
2193:the original
2188:
2184:
2168:
2140:
2136:
2128:
2121:
2093:Truss (1976)
2088:
2076:
2066:Kőnig (1927)
2061:
2014:
1920:
1909:
1898:
1840:
1835:
1790:
1693:
1685:
1684:. A bar is
1681:
1625:
1624:is called a
1579:
1565:
1549:constructive
1546:
1518:
1449:
1215:
1211:
1179:
1017:arithmetical
984:
681:
646:
614:
506:
497:
316:
218:
215:Construction
202:
139:
130:proof theory
109:graph theory
100:
96:
95:
72:
63:
44:
2165:Rubin, Jean
2101:Lévy (1979)
1648:to the set
198:simple path
192:contains a
113:Dénes Kőnig
58:introducing
2503:Categories
2199:2014-12-23
2111:References
1981:such that
1907:suffices.
1686:detachable
1210:is called
1121:is always
1055:Kleene's O
41:references
2410:Kőnig, D.
2380:Kőnig, D.
2316:Π
2264:Truss, J.
2177:Kőnig, D.
2157:117198918
2047:PA degree
1877:ω
1860:…
1820:ω
1724:ω
1636:ω
1610:ω
1483:ω
1387:ω
1380:ω
1266:ω
1246:ω
1196:ω
1189:ω
1130:Σ
1100:
1066:Π
1039:ω
1032:ω
1001:ω
994:ω
961:
929:
897:
872:ω
865:ω
815:
743:
718:ω
711:ω
665:ω
658:ω
631:ω
624:ω
600:ω
577:ω
570:ω
545:ω
523:ω
516:ω
162:connected
2450:(1987),
2412:(1936),
2382:(1926),
2247:(1967),
2209:(1979),
2179:(1927),
2167:(1998),
2120:(1927),
2035:See also
1417:′
1347:. Thus
2493:TREES_2
2470:0882921
2441:1723993
2373:1720779
2294:0429557
2257:0224462
2229:0533962
2015:In the
1793:compact
1694:uniform
1570: (
1157:) when
105:theorem
54:improve
2468:
2458:
2439:
2429:
2371:
2361:
2292:
2282:
2255:
2236:
2227:
2217:
2155:
2019:, the
1298:, the
561:) and
209:degree
43:, but
2387:(PDF)
2347:37–85
2153:S2CID
2053:Notes
1238:from
160:be a
103:is a
2487:The
2456:ISBN
2427:ISBN
2359:ISBN
2280:ISBN
2234:ISBN
2215:ISBN
1874:<
1607:<
1572:1927
1384:<
1193:<
1036:<
998:<
869:<
715:<
662:<
628:<
574:<
520:<
205:tree
196:: a
140:Let
128:and
2399:doi
2351:doi
2272:doi
2145:doi
1736:to
1626:bar
1582:of
1523:of
1475:of
1439:low
1258:to
1214:or
1097:Ext
958:Ext
926:Ext
894:Ext
856:of
812:Ext
740:Ext
702:of
462:to
194:ray
107:in
99:or
2505::
2466:MR
2464:,
2437:MR
2435:,
2389:,
2369:MR
2367:,
2357:,
2349:,
2290:MR
2288:,
2278:,
2253:MR
2225:MR
2223:,
2183:,
2151:,
2141:51
2139:,
1563:.
1539:.
1401:.
314:.
168:,
164:,
132:.
2495:.
2401::
2395:8
2353::
2325:0
2320:1
2274::
2240:.
2189:3
2147::
1995:z
1992:R
1989:x
1969:z
1949:x
1929:R
1870:}
1866:k
1863:,
1857:,
1854:0
1851:{
1841:k
1836:N
1816:}
1812:1
1809:,
1806:0
1803:{
1776:N
1756:}
1753:1
1750:,
1747:0
1744:{
1704:N
1682:S
1668:}
1665:1
1662:,
1659:0
1656:{
1603:}
1599:1
1596:,
1593:0
1590:{
1580:S
1537:0
1533:0
1521:0
1515:.
1503:X
1463:X
1445:.
1434:.
1414:0
1355:f
1335:)
1332:n
1329:(
1326:f
1306:n
1286:n
1226:f
1165:T
1139:1
1134:1
1109:)
1106:T
1103:(
1075:1
1070:1
970:)
967:T
964:(
938:)
935:T
932:(
906:)
903:T
900:(
844:T
824:)
821:T
818:(
792:T
772:T
752:)
749:T
746:(
690:T
481:1
478:+
475:i
471:v
448:i
444:v
421:1
418:+
415:i
411:v
384:i
380:v
357:i
353:v
330:i
326:v
300:1
296:v
275:G
253:1
249:v
227:G
180:G
148:G
79:)
73:(
68:)
64:(
50:.
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
