1077:. The empty sequence is the unique minimal element, and each element has a finite and well-ordered set of predecessors (the set of all of its prefixes). An order-theoretic tree may be represented by an isomorphic tree of sequences if and only if each of its elements has finite height (that is, a finite set of predecessors).
1878:
948:, and an outgoing edge from each nonempty sequence that connects it to the shorter sequence formed by removing its last element. This graph is a tree in the graph-theoretic sense. The root of the tree is the empty sequence.
1568:
882:
759:
415:
272:
1614:
908:
in which every vertex except for a special root vertex has exactly one outgoing edge, and in which the path formed by following these edges from any vertex eventually leads to the root vertex. If
1736:
1415:
201:
151:
344:
1189:
1130:
1353:
1672:
1035:
461:
1455:
1435:
1373:
1321:
1275:
1255:
1235:
1162:
1103:
1075:
1055:
1009:
989:
946:
926:
799:
779:
682:
658:
605:
553:
533:
513:
493:
435:
312:
292:
171:
121:
84:
60:
1728:
1698:
1301:
1215:
579:
1460:
1616:(the subset for which the length of the first sequence is equal to or 1 more than the length of the second sequence). In this way we may identify
971:
set of predecessors. Every tree in descriptive set theory is also an order-theoretic tree, using a partial ordering in which two sequences
804:
27:
This article is about mathematical trees described by prefixes of finite sequences. For trees described by partially ordered sets, see
687:
349:
206:
1873:{\displaystyle p=\{{\vec {x}}\in X^{\omega }|(\exists {\vec {y}}\in Y^{\omega })\langle {\vec {x}},{\vec {y}}\rangle \in \}}
1573:
1570:). Elements in this subspace are identified in the natural way with a subset of the product of two spaces of sequences,
1934:
1927:
928:
is a tree in the descriptive set theory sense, then it corresponds to a graph with one vertex for each sequence in
1951:
1378:
1919:
1956:
17:
176:
126:
87:
317:
1167:
1108:
1332:
35:
1898:
1619:
960:
1014:
1961:
1911:
8:
440:
625:
1440:
1420:
1358:
1306:
1260:
1240:
1220:
1147:
1088:
1060:
1040:
994:
974:
931:
911:
784:
764:
667:
643:
590:
538:
518:
498:
478:
420:
297:
277:
156:
106:
69:
45:
1707:
1677:
1280:
1194:
558:
1930:
1923:
1327:
956:
28:
1133:
964:
63:
1141:
905:
1563:{\displaystyle \langle x_{0},y_{1},x_{2},y_{3}\ldots ,x_{2m},y_{2m+1}\rangle }
1945:
968:
952:
897:
1355:
are considered. In this case, by convention, we consider only the subset
901:
613:
1894:
1890:
629:
632:
with an infinite number of sequences must necessarily be illfounded.
1257:
consist of the set of finite prefixes of the infinite sequences in
877:{\displaystyle \langle x_{0},x_{1},\ldots ,x_{n-1},x\rangle \in T}
754:{\displaystyle \langle x_{0},x_{1},\ldots ,x_{n-1}\rangle \in T}
90:
of a sequence in the collection also belongs to the collection.
103:
The collection of all finite sequences of elements of a set
410:{\displaystyle \langle x_{0},x_{1},\ldots ,x_{m-1}\rangle }
267:{\displaystyle \langle x_{0},x_{1},\ldots ,x_{n-1}\rangle }
1417:, containing only sequences whose even elements come from
884:. A tree that does not have any terminal nodes is called
1739:
1710:
1680:
1622:
1609:{\displaystyle X^{<\omega }\times Y^{<\omega }}
1576:
1463:
1443:
1423:
1381:
1361:
1335:
1309:
1283:
1263:
1243:
1223:
1197:
1170:
1150:
1111:
1091:
1063:
1043:
1017:
997:
977:
934:
914:
807:
787:
767:
690:
670:
646:
593:
561:
541:
521:
501:
481:
463:
shows that the empty sequence belongs to every tree.
443:
423:
352:
320:
300:
280:
209:
179:
159:
129:
109:
72:
48:
1700:for over the product space. We may then form the
891:
1872:
1722:
1692:
1666:
1608:
1562:
1449:
1429:
1409:
1367:
1347:
1315:
1295:
1269:
1249:
1229:
1209:
1183:
1156:
1124:
1097:
1069:
1049:
1029:
1003:
983:
940:
920:
876:
793:
773:
753:
676:
652:
599:
573:
547:
527:
507:
487:
455:
429:
409:
338:
306:
286:
266:
195:
165:
153:. With this notation, a tree is a nonempty subset
145:
115:
78:
54:
1943:
664:if it is not a prefix of a longer sequence in
1867:
1852:
1822:
1755:
1557:
1464:
865:
808:
742:
691:
404:
353:
261:
210:
955:, a different notion of a tree is used: an
515:, each of whose finite prefixes belongs to
1410:{\displaystyle (X\times Y)^{<\omega }}
640:A finite sequence that belongs to a tree
1144:. In this topology, every closed subset
1910:
495:is an infinite sequence of elements of
14:
1944:
610:A tree that has no branches is called
466:
1323:forms a closed set in this topology.
618:; a tree with at least one branch is
1085:The set of infinite sequences over
761:is terminal if there is no element
24:
1791:
535:. The set of all branches through
25:
1973:
635:
1916:Classical Descriptive Set Theory
892:Relation to other types of trees
196:{\displaystyle X^{<\omega }}
146:{\displaystyle X^{<\omega }}
1864:
1858:
1846:
1831:
1819:
1800:
1788:
1784:
1764:
1749:
1743:
1717:
1711:
1687:
1681:
1661:
1645:
1639:
1623:
1395:
1382:
1290:
1284:
1204:
1198:
568:
562:
346:, then the shortened sequence
93:
13:
1:
1920:Graduate Texts in Mathematics
1904:
967:in which each element has a
339:{\displaystyle 0\leq m<n}
7:
1884:
1437:and odd elements come from
1184:{\displaystyle X^{\omega }}
1125:{\displaystyle X^{\omega }}
1080:
10:
1978:
437:. In particular, choosing
26:
1893:, a type of tree used in
1348:{\displaystyle X\times Y}
274:is a sequence of length
98:
1897:as part of a notion of
1667:{\displaystyle \times }
1277:. Conversely, the body
1952:Descriptive set theory
1874:
1724:
1694:
1668:
1610:
1564:
1451:
1431:
1411:
1375:of the product space,
1369:
1349:
1317:
1297:
1271:
1251:
1231:
1211:
1185:
1158:
1126:
1099:
1071:
1057:is a proper prefix of
1051:
1031:
1030:{\displaystyle T<U}
1005:
985:
942:
922:
878:
795:
775:
755:
678:
654:
601:
575:
549:
529:
509:
489:
457:
431:
411:
340:
308:
288:
268:
197:
167:
147:
117:
80:
56:
36:descriptive set theory
1912:Kechris, Alexander S.
1875:
1725:
1695:
1669:
1611:
1565:
1452:
1432:
1412:
1370:
1350:
1318:
1298:
1272:
1252:
1232:
1217:for some pruned tree
1212:
1186:
1159:
1127:
1100:
1072:
1052:
1032:
1006:
986:
961:partially ordered set
943:
923:
879:
796:
776:
756:
679:
655:
602:
576:
550:
530:
510:
490:
458:
432:
412:
341:
309:
289:
269:
198:
168:
148:
118:
81:
57:
1737:
1708:
1678:
1620:
1574:
1461:
1441:
1421:
1379:
1359:
1333:
1326:Frequently trees on
1307:
1281:
1261:
1241:
1221:
1195:
1168:
1148:
1109:
1089:
1061:
1041:
1015:
995:
975:
957:order-theoretic tree
932:
912:
805:
785:
765:
688:
668:
644:
591:
559:
539:
519:
499:
479:
441:
421:
350:
318:
298:
278:
207:
177:
157:
127:
107:
70:
46:
1132:) may be given the
467:Branches and bodies
456:{\displaystyle m=0}
62:is a collection of
1957:Trees (set theory)
1870:
1720:
1690:
1664:
1606:
1560:
1447:
1427:
1407:
1365:
1345:
1328:Cartesian products
1313:
1293:
1267:
1247:
1227:
1207:
1181:
1154:
1122:
1095:
1067:
1047:
1027:
1001:
981:
938:
918:
874:
791:
771:
751:
674:
650:
597:
571:
545:
525:
505:
485:
453:
427:
407:
336:
304:
284:
264:
193:
163:
143:
113:
76:
52:
1849:
1834:
1803:
1767:
1450:{\displaystyle Y}
1430:{\displaystyle X}
1368:{\displaystyle T}
1316:{\displaystyle T}
1270:{\displaystyle C}
1250:{\displaystyle T}
1230:{\displaystyle T}
1157:{\displaystyle C}
1098:{\displaystyle X}
1070:{\displaystyle U}
1050:{\displaystyle T}
1004:{\displaystyle U}
984:{\displaystyle T}
941:{\displaystyle T}
921:{\displaystyle T}
794:{\displaystyle X}
774:{\displaystyle x}
677:{\displaystyle T}
653:{\displaystyle T}
600:{\displaystyle T}
548:{\displaystyle T}
528:{\displaystyle T}
508:{\displaystyle X}
488:{\displaystyle T}
430:{\displaystyle T}
307:{\displaystyle T}
287:{\displaystyle n}
166:{\displaystyle T}
116:{\displaystyle X}
79:{\displaystyle X}
55:{\displaystyle X}
29:Tree (set theory)
16:(Redirected from
1969:
1938:
1879:
1877:
1876:
1871:
1851:
1850:
1842:
1836:
1835:
1827:
1818:
1817:
1805:
1804:
1796:
1787:
1782:
1781:
1769:
1768:
1760:
1729:
1727:
1726:
1723:{\displaystyle }
1721:
1699:
1697:
1696:
1693:{\displaystyle }
1691:
1673:
1671:
1670:
1665:
1660:
1659:
1638:
1637:
1615:
1613:
1612:
1607:
1605:
1604:
1589:
1588:
1569:
1567:
1566:
1561:
1556:
1555:
1534:
1533:
1515:
1514:
1502:
1501:
1489:
1488:
1476:
1475:
1456:
1454:
1453:
1448:
1436:
1434:
1433:
1428:
1416:
1414:
1413:
1408:
1406:
1405:
1374:
1372:
1371:
1366:
1354:
1352:
1351:
1346:
1322:
1320:
1319:
1314:
1302:
1300:
1299:
1296:{\displaystyle }
1294:
1276:
1274:
1273:
1268:
1256:
1254:
1253:
1248:
1236:
1234:
1233:
1228:
1216:
1214:
1213:
1210:{\displaystyle }
1208:
1190:
1188:
1187:
1182:
1180:
1179:
1163:
1161:
1160:
1155:
1134:product topology
1131:
1129:
1128:
1123:
1121:
1120:
1104:
1102:
1101:
1096:
1076:
1074:
1073:
1068:
1056:
1054:
1053:
1048:
1036:
1034:
1033:
1028:
1010:
1008:
1007:
1002:
990:
988:
987:
982:
947:
945:
944:
939:
927:
925:
924:
919:
883:
881:
880:
875:
858:
857:
833:
832:
820:
819:
800:
798:
797:
792:
780:
778:
777:
772:
760:
758:
757:
752:
741:
740:
716:
715:
703:
702:
684:. Equivalently,
683:
681:
680:
675:
659:
657:
656:
651:
606:
604:
603:
598:
580:
578:
577:
574:{\displaystyle }
572:
554:
552:
551:
546:
534:
532:
531:
526:
514:
512:
511:
506:
494:
492:
491:
486:
462:
460:
459:
454:
436:
434:
433:
428:
417:also belongs to
416:
414:
413:
408:
403:
402:
378:
377:
365:
364:
345:
343:
342:
337:
313:
311:
310:
305:
293:
291:
290:
285:
273:
271:
270:
265:
260:
259:
235:
234:
222:
221:
202:
200:
199:
194:
192:
191:
172:
170:
169:
164:
152:
150:
149:
144:
142:
141:
122:
120:
119:
114:
86:such that every
85:
83:
82:
77:
64:finite sequences
61:
59:
58:
53:
21:
1977:
1976:
1972:
1971:
1970:
1968:
1967:
1966:
1942:
1941:
1922:156. Springer.
1907:
1887:
1841:
1840:
1826:
1825:
1813:
1809:
1795:
1794:
1783:
1777:
1773:
1759:
1758:
1738:
1735:
1734:
1709:
1706:
1705:
1679:
1676:
1675:
1652:
1648:
1630:
1626:
1621:
1618:
1617:
1597:
1593:
1581:
1577:
1575:
1572:
1571:
1542:
1538:
1526:
1522:
1510:
1506:
1497:
1493:
1484:
1480:
1471:
1467:
1462:
1459:
1458:
1442:
1439:
1438:
1422:
1419:
1418:
1398:
1394:
1380:
1377:
1376:
1360:
1357:
1356:
1334:
1331:
1330:
1308:
1305:
1304:
1282:
1279:
1278:
1262:
1259:
1258:
1242:
1239:
1238:
1222:
1219:
1218:
1196:
1193:
1192:
1191:is of the form
1175:
1171:
1169:
1166:
1165:
1149:
1146:
1145:
1116:
1112:
1110:
1107:
1106:
1090:
1087:
1086:
1083:
1062:
1059:
1058:
1042:
1039:
1038:
1037:if and only if
1016:
1013:
1012:
1011:are ordered by
996:
993:
992:
976:
973:
972:
965:minimal element
933:
930:
929:
913:
910:
909:
894:
847:
843:
828:
824:
815:
811:
806:
803:
802:
801:such that that
786:
783:
782:
766:
763:
762:
730:
726:
711:
707:
698:
694:
689:
686:
685:
669:
666:
665:
645:
642:
641:
638:
592:
589:
588:
581:and called the
560:
557:
556:
540:
537:
536:
520:
517:
516:
500:
497:
496:
480:
477:
476:
475:through a tree
469:
442:
439:
438:
422:
419:
418:
392:
388:
373:
369:
360:
356:
351:
348:
347:
319:
316:
315:
299:
296:
295:
279:
276:
275:
249:
245:
230:
226:
217:
213:
208:
205:
204:
203:, such that if
184:
180:
178:
175:
174:
158:
155:
154:
134:
130:
128:
125:
124:
108:
105:
104:
101:
96:
71:
68:
67:
66:of elements of
47:
44:
43:
32:
23:
22:
15:
12:
11:
5:
1975:
1965:
1964:
1959:
1954:
1940:
1939:
1906:
1903:
1902:
1901:
1886:
1883:
1882:
1881:
1869:
1866:
1863:
1860:
1857:
1854:
1848:
1845:
1839:
1833:
1830:
1824:
1821:
1816:
1812:
1808:
1802:
1799:
1793:
1790:
1786:
1780:
1776:
1772:
1766:
1763:
1757:
1754:
1751:
1748:
1745:
1742:
1719:
1716:
1713:
1689:
1686:
1683:
1663:
1658:
1655:
1651:
1647:
1644:
1641:
1636:
1633:
1629:
1625:
1603:
1600:
1596:
1592:
1587:
1584:
1580:
1559:
1554:
1551:
1548:
1545:
1541:
1537:
1532:
1529:
1525:
1521:
1518:
1513:
1509:
1505:
1500:
1496:
1492:
1487:
1483:
1479:
1474:
1470:
1466:
1446:
1426:
1404:
1401:
1397:
1393:
1390:
1387:
1384:
1364:
1344:
1341:
1338:
1312:
1303:of every tree
1292:
1289:
1286:
1266:
1246:
1237:. Namely, let
1226:
1206:
1203:
1200:
1178:
1174:
1153:
1142:discrete space
1119:
1115:
1094:
1082:
1079:
1066:
1046:
1026:
1023:
1020:
1000:
980:
937:
917:
906:directed graph
893:
890:
873:
870:
867:
864:
861:
856:
853:
850:
846:
842:
839:
836:
831:
827:
823:
818:
814:
810:
790:
770:
750:
747:
744:
739:
736:
733:
729:
725:
722:
719:
714:
710:
706:
701:
697:
693:
673:
649:
637:
636:Terminal nodes
634:
628:, a tree on a
596:
570:
567:
564:
544:
524:
504:
484:
468:
465:
452:
449:
446:
426:
406:
401:
398:
395:
391:
387:
384:
381:
376:
372:
368:
363:
359:
355:
335:
332:
329:
326:
323:
303:
283:
263:
258:
255:
252:
248:
244:
241:
238:
233:
229:
225:
220:
216:
212:
190:
187:
183:
162:
140:
137:
133:
112:
100:
97:
95:
92:
75:
51:
9:
6:
4:
3:
2:
1974:
1963:
1960:
1958:
1955:
1953:
1950:
1949:
1947:
1936:
1935:3-540-94374-9
1932:
1929:
1928:0-387-94374-9
1925:
1921:
1917:
1913:
1909:
1908:
1900:
1896:
1892:
1889:
1888:
1861:
1855:
1843:
1837:
1828:
1814:
1810:
1806:
1797:
1778:
1774:
1770:
1761:
1752:
1746:
1740:
1733:
1732:
1731:
1714:
1703:
1684:
1656:
1653:
1649:
1642:
1634:
1631:
1627:
1601:
1598:
1594:
1590:
1585:
1582:
1578:
1552:
1549:
1546:
1543:
1539:
1535:
1530:
1527:
1523:
1519:
1516:
1511:
1507:
1503:
1498:
1494:
1490:
1485:
1481:
1477:
1472:
1468:
1444:
1424:
1402:
1399:
1391:
1388:
1385:
1362:
1342:
1339:
1336:
1329:
1324:
1310:
1287:
1264:
1244:
1224:
1201:
1176:
1172:
1151:
1143:
1139:
1135:
1117:
1113:
1092:
1078:
1064:
1044:
1024:
1021:
1018:
998:
978:
970:
966:
962:
958:
954:
949:
935:
915:
907:
903:
899:
889:
887:
871:
868:
862:
859:
854:
851:
848:
844:
840:
837:
834:
829:
825:
821:
816:
812:
788:
768:
748:
745:
737:
734:
731:
727:
723:
720:
717:
712:
708:
704:
699:
695:
671:
663:
662:terminal node
647:
633:
631:
627:
626:Kőnig's lemma
623:
622:
617:
616:
615:
608:
594:
586:
585:
565:
542:
522:
502:
482:
474:
464:
450:
447:
444:
424:
399:
396:
393:
389:
385:
382:
379:
374:
370:
366:
361:
357:
333:
330:
327:
324:
321:
301:
281:
256:
253:
250:
246:
242:
239:
236:
231:
227:
223:
218:
214:
188:
185:
181:
160:
138:
135:
131:
110:
91:
89:
73:
65:
49:
41:
37:
30:
19:
1915:
1701:
1325:
1137:
1105:(denoted as
1084:
969:well-ordered
953:order theory
950:
898:graph theory
895:
885:
661:
660:is called a
639:
620:
619:
612:
611:
609:
587:of the tree
583:
582:
472:
470:
102:
39:
33:
1962:Determinacy
1136:, treating
902:rooted tree
614:wellfounded
555:is denoted
123:is denoted
94:Definitions
18:Pruned tree
1946:Categories
1905:References
1895:set theory
1891:Laver tree
1702:projection
630:finite set
621:illfounded
1856:∈
1853:⟩
1847:→
1832:→
1823:⟨
1815:ω
1807:∈
1801:→
1792:∃
1779:ω
1771:∈
1765:→
1657:ω
1643:×
1635:ω
1602:ω
1591:×
1586:ω
1558:⟩
1517:…
1465:⟨
1403:ω
1389:×
1340:×
1177:ω
1118:ω
963:with one
869:∈
866:⟩
852:−
838:…
809:⟨
746:∈
743:⟩
735:−
721:…
692:⟨
405:⟩
397:−
383:…
354:⟨
325:≤
314:, and if
262:⟩
254:−
240:…
211:⟨
189:ω
139:ω
42:on a set
1914:(1995).
1885:See also
1081:Topology
1899:forcing
1457:(e.g.,
1933:
1926:
886:pruned
624:. By
473:branch
88:prefix
1674:with
1140:as a
959:is a
904:is a
99:Trees
1931:ISBN
1924:ISBN
1654:<
1632:<
1599:<
1583:<
1400:<
1022:<
991:and
900:, a
584:body
331:<
186:<
136:<
40:tree
38:, a
1704:of
1164:of
951:In
896:In
781:of
294:in
173:of
34:In
1948::
1918:.
1730:,
888:.
607:.
471:A
1937:.
1880:.
1868:}
1865:]
1862:T
1859:[
1844:y
1838:,
1829:x
1820:)
1811:Y
1798:y
1789:(
1785:|
1775:X
1762:x
1756:{
1753:=
1750:]
1747:T
1744:[
1741:p
1718:]
1715:T
1712:[
1688:]
1685:T
1682:[
1662:]
1650:Y
1646:[
1640:]
1628:X
1624:[
1595:Y
1579:X
1553:1
1550:+
1547:m
1544:2
1540:y
1536:,
1531:m
1528:2
1524:x
1520:,
1512:3
1508:y
1504:,
1499:2
1495:x
1491:,
1486:1
1482:y
1478:,
1473:0
1469:x
1445:Y
1425:X
1396:)
1392:Y
1386:X
1383:(
1363:T
1343:Y
1337:X
1311:T
1291:]
1288:T
1285:[
1265:C
1245:T
1225:T
1205:]
1202:T
1199:[
1173:X
1152:C
1138:X
1114:X
1093:X
1065:U
1045:T
1025:U
1019:T
999:U
979:T
936:T
916:T
872:T
863:x
860:,
855:1
849:n
845:x
841:,
835:,
830:1
826:x
822:,
817:0
813:x
789:X
769:x
749:T
738:1
732:n
728:x
724:,
718:,
713:1
709:x
705:,
700:0
696:x
672:T
648:T
595:T
569:]
566:T
563:[
543:T
523:T
503:X
483:T
451:0
448:=
445:m
425:T
400:1
394:m
390:x
386:,
380:,
375:1
371:x
367:,
362:0
358:x
334:n
328:m
322:0
302:T
282:n
257:1
251:n
247:x
243:,
237:,
232:1
228:x
224:,
219:0
215:x
182:X
161:T
132:X
111:X
74:X
50:X
31:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.