Tree (set theory)

A branch (highlighted green) of a set-theoretic tree. Here dots represent elements, arrows represent the order relation, and ellipses and dashed arrows represent (possibly infinite) un-pictured elements and relationships.

In set theory, a tree is a partially ordered set (T, <) such that for each tT, the set {sT : s < t} is well-ordered by the relation <. Frequently trees are assumed to have only one root (i.e. minimal element), as the typical questions investigated in this field are easily reduced to questions about single-rooted trees.

Definition

Small finite examples: The three partially ordered sets on the left are trees (in blue); one branch of one of the trees is highlighted (in green). The partially ordered set on the right (in red) is not a tree because x1 < x3 and x2 < x3, but x1 is not comparable to x2 (dashed orange line).

A tree is a partially ordered set (poset) (T, <) such that for each tT, the set {sT : s < t} is well-ordered by the relation <. In particular, each well-ordered set (T, <) is a tree. For each tT, the order type of {sT : s < t} is called the height of t, denoted ht(tT). The height of T itself is the least ordinal greater than the height of each element of T. A root of a tree T is an element of height 0. Frequently trees are assumed to have only one root. Trees in set theory are often defined to grow downward making the root the greatest node.[citation needed]

Trees with a single root may be viewed as rooted trees in the sense of graph theory in one of two ways: either as a tree (graph theory) or as a trivially perfect graph. In the first case, the graph is the undirected Hasse diagram of the partially ordered set, and in the second case, the graph is simply the underlying (undirected) graph of the partially ordered set. However, if T is a tree of height > ω, then the Hasse diagram definition does not work. For example, the partially ordered set does not have a Hasse Diagram, as there is no predecessor to ω. Hence a height of at most ω is required in this case.

A branch of a tree is a maximal chain in the tree (that is, any two elements of the branch are comparable, and any element of the tree not in the branch is incomparable with at least one element of the branch). The length of a branch is the ordinal that is order isomorphic to the branch. For each ordinal α, the α-th level of T is the set of all elements of T of height α. A tree is a κ-tree, for an ordinal number κ, if and only if it has height κ and every level has cardinality less than the cardinality of κ. The width of a tree is the supremum of the cardinalities of its levels.

Any single-rooted tree of height forms a meet-semilattice, where meet (common ancestor) is given by maximal element of intersection of ancestors, which exists as the set of ancestors is non-empty and finite well-ordered, hence has a maximal element. Without a single root, the intersection of parents can be empty (two elements need not have common ancestors), for example where the elements are not comparable; while if there are an infinite number of ancestors there need not be a maximal element – for example, where are not comparable.

A subtree of a tree is a tree where and is downward closed under , i.e., if and then .[citation needed]

Set-theoretic properties

There are some fairly simply stated yet hard problems in infinite tree theory. Examples of this are the Kurepa conjecture and the Suslin conjecture. Both of these problems are known to be independent of Zermelo–Fraenkel set theory. By Kőnig's lemma, every ω-tree has an infinite branch. On the other hand, it is a theorem of ZFC that there are uncountable trees with no uncountable branches and no uncountable levels; such trees are known as Aronszajn trees. Given a cardinal number κ, a κ-Suslin tree is a tree of height κ which has no chains or antichains of size κ. In particular, if κ is singular then there exists a κ-Aronszajn tree and a κ-Suslin tree. In fact, for any infinite cardinal κ, every κ-Suslin tree is a κ-Aronszajn tree (the converse does not hold).

The Suslin conjecture was originally stated as a question about certain total orderings but it is equivalent to the statement: Every tree of height ω1 has an antichain of cardinality ω1 or a branch of length ω1.

If (T,<) is a tree, then the reflexive closure ≤ of < is a prefix order on T. The converse does not hold: for example, the usual order ≤ on the set Z of integers is a total and hence a prefix order, but (Z,<) is not a set-theoretic tree since e.g. the set {nZ: n < 0} has no least element.

Examples of infinite trees

Set-theoretic tree of height and width . Each node corresponds to a junction point of a red and a green line. Due to space restrictions, only branches with a prefix (0,0,0,...) or (1,1,1,...) are shown in full length.
  • Let be an ordinal number, and let be a set. Let be set of all functions where . Define if the domain of is a proper subset of the domain of and the two functions agree on the domain of . Then is a set-theoretic tree. Its root is the unique function on the empty set, and its height is . The union of all functions along a branch yields a function from to , that is, a generalized sequence of members of . If is a limit ordinal, none of the branches has a maximal element ("leaf"). The picture shows an example for and .
  • Each tree data structure in computer science is a set-theoretic tree: for two nodes , define if is a proper descendant of . The notions of root, node height, and branch length coincide, while the notions of tree height differ by one.
  • Infinite trees considered in automata theory (see e.g. tree (automata theory)) are also set-theoretic trees, with a tree height of up to .
  • A graph-theoretic tree can be turned into a set-theoretic one by choosing a root node and defining if and lies on the (unique) undirected path from to .

See also

References

  • Jech, Thomas (2002). Set Theory. Springer-Verlag. ISBN 3-540-44085-2.
  • Kunen, Kenneth (1980). Set Theory: An Introduction to Independence Proofs. North-Holland. ISBN 0-444-85401-0. Chapter 2, Section 5.
  • Monk, J. Donald (1976). Mathematical Logic. New York: Springer-Verlag. p. 517. ISBN 0-387-90170-1.
  • Hajnal, András; Hamburger, Peter (1999). Set Theory. Cambridge: Cambridge University Press. ISBN 9780521596671.
  • Kechris, Alexander S. (1995). Classical Descriptive Set Theory. Graduate Texts in Mathematics 156. Springer. ISBN 0-387-94374-9. ISBN 3-540-94374-9.

Read other articles:

Saint-Philibert Saint-Philibert (Frankreich) Staat Frankreich Region Bourgogne-Franche-Comté Département (Nr.) Côte-d’Or (21) Arrondissement Beaune Kanton Nuits-Saint-Georges Gemeindeverband Gevrey-Chambertin et de Nuits-Saint-Georges Koordinaten 47° 12′ N, 5° 1′ O47.2063888888895.0119444444444Koordinaten: 47° 12′ N, 5° 1′ O Höhe 213–235 m Fläche 4,72 km² Einwohner 519 (1. Januar 2020) Bevölkerungsdichte 110 Einw./k...

 

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Cet article ne cite pas suffisamment ses sources (septembre 2021). Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références » En pratique : Quelles sources sont attendues ? ...

 

vdeSeleção Jamaicana – Copa Ouro da CONCACAF de 20091 Ricketts • 3 Stewart • 5 Goodison • 10 Fuller • 11 Shelton • 13 Kerr • 15 Gardner • 17 Austin • 19 Addlery • 21 Miller • Treinador: Whitmore

حوامة تندر: هي مركبة قتالية ثقيلة إيرانية الصنع، والتي تُعتبَر إحدى المشاريع العسكرية لوزارة الدفاع الإيرانية وتتميز حوامة تندر بالقدرة على اجتياز المناطق الوعرة وقد تم تزويدها بأنظمة ألكترونية وقتالية لتعزيز قدرات القوات الإيرانية في العمليات الحربية البحرية، وكذلك تم

 

Pour les articles homonymes, voir Canada (homonymie). Canada Drapeau du Canada Armoiries du Canada Devise en latin : A mari usque ad mare (« D'un océan à l'autre ») Hymne Ô Canada Fête nationale 1er juillet · Événement commémoré Naissance de la Confédération canadienne (1867) Administration Forme de l'État Monarchie constitutionnelle parlementaire fédérale Roi Charles III Gouverneure générale Mary Simon Premier ministre Justin Trudeau Vice-première ...

 

العلاقات البليزية النيجيرية بليز نيجيريا   بليز   نيجيريا تعديل مصدري - تعديل   العلاقات البليزية النيجيرية هي العلاقات الثنائية التي تجمع بين بليز ونيجيريا.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية للدولتين: وجه المقارنة بليز ...

Filipino cable television channel Television channel Cinema OneLaging KasamaCountryPhilippinesBroadcast areaPhilippinesWorldwideHeadquartersABS-CBN Broadcasting Center, Diliman, Quezon CityProgrammingLanguage(s)Filipino EnglishPicture format16:9 480i (SDTV)OwnershipOwnerCreative Programs Inc.Sister channelsUnder ABS-CBN A2ZANCCine Mo!Jeepney TVKapamilya ChannelKnowledge ChannelMetro ChannelMyx Myx (America)PIE ChannelTeleRadyo SerbisyoTFCHistoryLaunchedJune 12, 1994; 29 years ago...

 

American singer-songwriter (born 2000) Payton SmithBackground informationBorn (2000-01-26) January 26, 2000 (age 23)Houma, Louisiana, USGenresCountry, rock, country rock, AmericanaOccupation(s)Singer, songwriterInstrument(s)Vocals, guitar, banjo, mandolinLabelsBig Machine Label Group (2018–present)Websitepaytonsmith.comMusical artist Payton Smith (born January 26, 2000) is an American singer-songwriter. Early life The eldest of four boys, Payton Smith was born in Beaumont, Texas and ra...

 

Elon Phoenix 2023–24 Elon Phoenix men's basketball team UniversityElon UniversityHead coachBilly Taylor (2nd season)ConferenceColonial Athletic AssociationLocationElon, North CarolinaArenaSchar Center (Capacity: 5,100)NicknamePhoenixColorsMaroon and gold[1]   NCAA tournament appearances1997*at Division II levelConference tournament championsSAC: 1997Conference division season championsSoCon North: 2006, 2013 The Elon Phoenix men's basketball team is the bask...

Season of television series Beyblade Burst RiseKey VisualCountry of originJapanNo. of episodes52 (Japanese version)26 (English version)ReleaseOriginal networkYouTube (CoroCoro, Takara Tomy)Original releaseApril 5, 2019 (2019-04-05) –March 27, 2020 (2020-03-27)Season chronology← PreviousBurst Turbo Next →Burst Surge List of episodes Beyblade Burst Rise,[1] known in Japan as Beyblade Burst GT (Gachi) (ベイブレードバーストGT(ガチ), Beiburēdo B...

 

Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber: The Royal Family of Broadway – berita · surat kabar · buku · cendekiawan · JSTOR The Royal Family of BroadwaySutradara George Cukor Cyril Gardner ProduserDitulis olehBerdasarkanTeater:Edna FerberGeorge S...

 

Kabab restaurant chain in Dhaka, Bangladesh Star KababRestaurant informationEstablished1965 [1]Owner(s)Mir Aktar Uddin, Halima Khatun, Monira Begum [2]Previous owner(s)Mir Momtaz Uddin [3]Food typeKabab restaurantStreet addressThatari BazarCityDhakaCountryBangladeshOther locationsThatari Bazar, Wari, Kawran Bazar, Gulistan, Farmgate, Bango Bazar, Dhanmondi-2, Shatmoshjid Road, Dhanmondi, Banani, New Elephant road, Johnson Road.[4] Star Kabab is a kebab restaura...

Philosophical view This article is about the metaphysical perspective in philosophy. For the psychological attitude, see optimism. For the concept in ethics, see Ideal (ethics). For other uses, see Idealism (disambiguation). Detail of Plato in The School of Athens, by Raphael Idealism in philosophy, also known as philosophical idealism or metaphysical idealism, is the set of metaphysical perspectives asserting that, most fundamentally, reality is equivalent to mind, spirit, or consciousness; ...

 

Indian actor, director and screenwriter In this Telugu name, the person is referred to by his given name, Sesh, and not by his surname, Adivi. Adivi SeshAdivi Sesh in 2022 during the promotion of MajorBornAdivi Sesh Sunny Chandra (1984-12-17) 17 December 1984 (age 38)Hyderabad, Andhra Pradesh (now Telangana), IndiaAlma materSan Francisco State UniversityOccupationsActordirectorscreenwriterYears active2002– presentFamilySee Adivi Family Adivi Sesh Sunny Chandra (born 17 Decemb...

 

Railway station in Sindh, Pakistan Malir Railway Station ملیر ریلوے اسٹیشنGeneral informationCoordinates24°53′02″N 67°10′35″E / 24.8839°N 67.1763°E / 24.8839; 67.1763Owned byMinistry of RailwaysLine(s)Karachi–Peshawar Railway LineKarachi Circular RailwayPlatforms4Tracks4ConstructionPlatform levels1Other informationStation codeMXBServices Preceding station Pakistan Railways Following station Drigh Colonytowards Kiamari Karachi–Peshawar Lin...

Restaurant The MonocleThe Monocle restaurantRestaurant informationEstablishedSeptember 1960Owner(s)John and Vasiliki ValanosPrevious owner(s)Constantine and Helen ValanosStreet address107 D Street NECityWashingtonStateD.C.Postal/ZIP Code20002Coordinates38°53′40″N 77°00′19″W / 38.89457°N 77.00517°W / 38.89457; -77.00517Websitehttps://themonocle.com The Monocle is a restaurant in the Capitol Hill neighborhood of Washington, D.C. History The Monocle was founde...

 

清华大学外国语言文学系Department of Foreign Languages and Literatures, Tsinghua University类型系建立日期1926年隶属清华大学人文学院系主任颜海平地址 中国北京市海淀区清华园网站http://www.tsinghua.edu.cn/publish/fdll/ 外文系系館 文南樓 清华大学外国语言文学系,简称外文系/DFLL,是清华大学人文学院下属的一个系,始建于1926年。[1] 历史 1926年,成立西洋文学系,后改名外国语言...

 

Regional park in Perth, Western Australia Beeliar Regional ParkBird hide at Bibra LakeTypeRegional parkLocationCockburnKwinanaMelvilleCoordinates32°10′03″S 115°49′57″E / 32.16750°S 115.83250°E / -32.16750; 115.83250 (Beeliar Regional Park)Area3,171 ha (7,840 acres)Established17 January 1995Administered byDepartment of Biodiversity, Conservation and AttractionsWebsiteparks.dpaw.wa.gov.au/park/beeliar Commonwealth Heritage ListOfficial nameB...

Voce principale: Delfino Pescara 1936. Delfino Pescara 1936Stagione 2015-2016Sport calcio Squadra Pescara Allenatore Massimo Oddo All. in seconda Marcello Donatelli Presidente Daniele Sebastiani Serie B4º posto. Promosso in Serie A dopo i play-off. Coppa ItaliaTerzo turno Maggiori presenzeCampionato: Lapadula (40)Totale: Lapadula (40+4) Miglior marcatoreCampionato: Lapadula (27)Totale: Lapadula (27+3) StadioAdriatico Giovanni Cornacchia (20,515) Abbonati3 620 Maggior numero di spet...

 

Town in east London, England Human settlement in EnglandDagenhamThe southern Dagenham skyline includes structures of the Ford plant and wind turbines.DagenhamLocation within Greater LondonPopulation106,247 (2011)[1]OS grid referenceTQ485845• Charing Cross11.5 mi (18.5 km) WLondon boroughBarking & DagenhamCeremonial countyGreater LondonRegionLondonCountryEnglandSovereign stateUnited KingdomPost townDAGENHAMPostcode districtRM...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!