樹（集理論）

在集合理論中，樹是部分排序的集合（ t ，<），因此對於每個t∈T ，集合{ s∈T ： s < t }是由關係<。通常，假設樹只有一個根（即最小元素），因為該領域研究的典型問題很容易減少到有關單根樹的問題。

定義

樹是部分排序的集合（poset）（ t ，<），因此對於每個t∈T ，{ s∈T ： s <t} set { s∈T ： s < t }是由關係<。特別是，每個有序的集合（ t ，<）是一棵樹。對於每個t∈T ，{ s∈T ： s < t }的順序類型稱為t的高度，表示為ht（ t ， t ）。 T本身的高度最少大於t的每個元素的高度。樹T的根是高度0的元素。通常認為樹只有一個根。集合理論中的樹木通常被定義為向下生長，使根成為最大的節點。

具有單根根的樹可以以兩種方式之一的意義將其視為植根的樹：作為樹（圖理論）或瑣碎的完美圖。在第一種情況下，該圖是部分有序集的無向Hasse圖，在第二種情況下，該圖只是部分有序集的基礎（無向）圖。但是，如果t是高度> ω的樹，則HASSE圖定義不起作用。例如，部分有序集沒有HASSE圖，因為沒有ω的前身。因此，在這種情況下，最多需要ω的高度。

樹的分支是樹上的最大鏈（即，分支的任何兩個元素都是可比的，而樹的任何元素都不是在分支的至少一個元素中無與倫比的）。分支的長度是分支同構的順序。對於每個序數α， t的α水平是高度α的所有元素的集合。一棵樹是κ樹，對於序數κ，並且僅當它具有高度κ且每個級別的基數都小於κ的基數時。一棵樹的寬度是其水平的基礎的至高無上。

任何單根高度樹形式是一個聚會 - 偏見（共同祖先）由祖先交集的最大元素給出，而祖先的祖先是非空的且有限的井井有條的，因此具有最大元素。沒有一個根，父母的交叉可以是空的（例如，兩個要素不需要共同的祖先）元素不可比較的地方；雖然如果有無限數量的祖先，則不需要最大元素 - 例如在哪裡不可比擬。

樹的子樹是一棵樹在哪裡和向下關閉，即，如果和然後。

設定理論屬性

在無限樹理論中，有一些相當簡單地說明但棘手的問題。其中的例子是Kurepa猜想和Suslin猜想。這兩個問題都與Zermelo -Fraenkel集理論無關。由Kőnig的引理，每個ω-樹都有一個無限的分支。另一方面， ZFC的定理是有不可數的樹枝，沒有不可數的樹枝，沒有無法達到的水平。這樣的樹被稱為Aronszajn樹。給定基數κ， κsuslin樹是一棵高度κ，沒有鍊或抗大小κ。特別是，如果κ是奇異的，則存在κ-Aronszajn樹和κ-Suslin樹。實際上，對於任何無限的紅衣主教κ，每棵樹都是κ-aronszajn樹（相反的樹都不成立）。

SUSLIN的猜想最初是關於某些總順序的問題，但相當於陳述：每個高度_ω1的_樹都具有基數的抗逆金敵，或長度為_ω1的分支。

它（ t ，<）是一棵樹，然後<<的反射閉合≤是t上的前綴順序。相反的不結構：例如，整數的集合z上的通常順序≤是一個總數，因此是前綴順序，但是（ z ，<）不是集合理論樹，因為例如集合{ n∈Z ： n <0}沒有最不重要的元素。