ツリー（記述集合論）

記述的集合論では、集合上の木は、集合内のシーケンスのすべての接頭辞も集合に属するよう な、要素の有限シーケンスの集合です。${\displaystyle X}$${\displaystyle X}$

集合の要素の有限シーケンスすべてのコレクションはと表記されます。この表記法では、木はの空でない部分集合であり、 が 内の長さのシーケンスである場合、短縮されたシーケンスも に属します。特に、 を選択すると、空シーケンスがすべての木に属することがわかります。 ${\displaystyle X}$${\displaystyle X^{<\omega }}$${\displaystyle T}$${\displaystyle X^{<\omega }}$${\displaystyle \langle x_{0},x_{1},\ldots ,x_{n-1}\rangle }$${\displaystyle n}$${\displaystyle T}$${\displaystyle 0\leq m<n}$${\displaystyle \langle x_{0},x_{1},\ldots ,x_{m-1}\rangle }$${\displaystyle T}$${\displaystyle m=0}$

木の枝は、それぞれの有限接頭辞が に属する の要素の無限列です。 を通るすべての枝の集合は と表され、木の本体と呼ばれます。 ${\displaystyle T}$${\displaystyle X}$${\displaystyle T}$${\displaystyle T}$${\displaystyle [T]}$${\displaystyle T}$

枝を持たない木はwellfoundedと呼ばれ、少なくとも 1 つの枝を持つ木はillfoundedと呼ばれます。ケーニッヒの補題により、無限の数のシーケンスを持つ有限集合上の木は必然的に illfounded になります。

木に属する有限シーケンスは、それが 内のより長いシーケンスのプレフィックスでない場合、終端ノードと呼ばれます。同様に、となるの要素がない場合は、 は終端です。終端ノードを持たない木は、剪定されたと呼ばれます。 ${\displaystyle T}$${\displaystyle T}$${\displaystyle \langle x_{0},x_{1},\ldots ,x_{n-1}\rangle \in T}$${\displaystyle x}$${\displaystyle X}$${\displaystyle \langle x_{0},x_{1},\ldots ,x_{n-1},x\rangle \in T}$

グラフ理論において、根付き木とは、特別な根頂点を除くすべての頂点がちょうど 1 つの出力辺を持ち、どの頂点からでもこれらの辺をたどって形成されるパスが最終的に根頂点につながるような有向グラフです。 が記述的集合論の意味での木である場合、それは 内の各シーケンスに対して 1 つの頂点を持ち、各空でないシーケンスからの出力辺が、最後の要素を削除することによって形成される短いシーケンスに接続するグラフに対応します。 このグラフは、グラフ理論の意味での木です。 木の根は空のシーケンスです。 ${\displaystyle T}$${\displaystyle T}$

順序理論では、異なる概念の木が使われます。順序理論的な木は、各要素が整然とした先行要素の集合を持つ、 1 つの最小要素を持つ部分的に順序付けられた集合です。記述集合論におけるすべての木も、 がの適切な接頭辞である場合に限り、 2 つのシーケンスおよびがによって順序付けられるという部分的な順序付けを使用する順序理論的な木です。空のシーケンスは唯一の最小要素であり、各要素は有限で整然とした先行要素の集合 (そのすべての接頭辞の集合) を持ちます。順序理論的な木は、各要素の高さが有限である (つまり、先行要素の有限集合である) 場合に限り、シーケンスの同型木で表すことができます。 ${\displaystyle T}$${\displaystyle U}$${\displaystyle T<U}$${\displaystyle T}$${\displaystyle U}$

上の無限列全体の集合( と表記) には、 X を離散空間として扱うことで、積位相が与えられます。この位相では、のすべての閉部分集合は、何らかの刈り込まれた木 に対して の形をとります。つまり、 が内の無限列の有限接頭辞の集合で構成されるとします。逆に、すべての木の本体はこの位相で閉集合を形成します。 ${\displaystyle X}$${\displaystyle X^{\omega}}$${\displaystyle C}$${\displaystyle X^{\omega}}$${\displaystyle [T]}$${\displaystyle T}$${\displaystyle T}$${\displaystyle C}$${\displaystyle [T]}$${\displaystyle T}$

直積 上の木がしばしば考慮される。この場合、慣例により、偶数要素が から、奇数要素が から得られるシーケンスのみを含む積空間の部分集合 のみを考慮する（例：）。この部分空間の要素は、シーケンスの 2 つの空間の積の部分集合（最初のシーケンスの長さが 2 番目のシーケンスの長さと等しいか 1 大きい部分集合）と自然に同一視される。このようにして、積空間上の をと同一視できる。次に、の射影を形成できる。 ${\displaystyle X\times Y}$${\displaystyle T}$${\displaystyle (X\times Y)^{<\omega }}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle \langle x_{0},y_{1},x_{2},y_{3}\ldots ,x_{2m},y_{2m+1}\rangle }$${\displaystyle X^{<\omega }\times Y^{<\omega }}$${\displaystyle [X^{<\omega }]\times [Y^{<\omega }]}$${\displaystyle [T]}$${\displaystyle [T]}$

${\displaystyle p[T]=\{{\vec {x}}\in X^{\omega }|(\exists {\vec {y}}\in Y^{\omega })\langle {\vec {x}},{\vec {y}}\rangle \in [T]\}}$。

• レーバーツリー、集合論において強制の概念の一部として使用されるツリーの一種

• Kechris, Alexander S. (1995).古典的記述集合論.数学大学院テキスト156. Springer. ISBN 0-387-94374-9 ISBN 3-540-94374-9 .