木構造（集合論）

集合論において、木は部分的に順序付けられた集合である。${\displaystyle (T,<)}$各$t ∈ T$セット${\displaystyle \{s\in T:s<t\}}$関係によって整列されている${\displaystyle <}$木はしばしば根が1つ（つまり最小要素）しかないと仮定される。なぜなら、この分野で調査される典型的な問題は、根が1つしかない木に関する問題に容易に還元できるからである。

木構造は半順序集合（poset）である。${\displaystyle (T,<)}$各$t ∈ T$セット${\displaystyle \{s\in T:s<t\}}$関係によって整列されている${\displaystyle <}$特に、各整列集合${\displaystyle (T,<)}$は木です。$t ∈ T$注文タイプ​${\displaystyle \{s\in T:s<t\}}$高さ、ランク[ ^{1 ]}またはレベル^{[ 2 ]と}呼ばれる${\displaystyle t}$高さ​${\displaystyle T}$それ自体は各要素の高さよりも大きい最小の順序数である${\displaystyle T}$木の根​​${\displaystyle T}$は高さ0の要素です。木はしばしば根が1つしかないと想定されます。

単一の根を持つ木は、グラフ理論の意味で根付き木として、2つの方法で見なすことができます。1つは木（グラフ理論）として、もう1つは自明な完全グラフとしてです。最初のケースでは、グラフは半順序集合の無向ハッセ図であり、2番目のケースでは、グラフは単に半順序集合の基底となる（無向）グラフです。ただし、${\displaystyle T}$最小の無限順序数よりも高さが大きい木${\displaystyle \omega }$その場合、ハッセ図の定義は機能しません。例えば、半順序集合${\displaystyle \omega +1=\left\{0,1,2,\dots ,\omega \right\}}$ハッセ図は存在しません。${\displaystyle \omega }$したがって、高さは最大で${\displaystyle \omega }$このようにグラフ理論的な木を定義するには、これが必要である。

木の枝とは、木における極大鎖のことである（つまり、枝内の任意の2つの要素は比較可能であり、枝に含まれない木の任意の要素は、枝内の少なくとも1つの要素とは比較不可能である）。枝の長さとは、枝と順序同型な順序数である。各順序数について、${\displaystyle \alpha }$、${\displaystyle \alpha }$レベルの${\displaystyle T}$は、すべての要素の集合です。${\displaystyle T}$高さ${\displaystyle \alpha }$木は${\displaystyle \kappa }$-tree、序数用${\displaystyle \kappa }$高さがある場合に限り${\displaystyle \kappa }$そして、すべてのレベルのカーディナリティは、${\displaystyle \kappa }$木の幅は、そのレベルの濃度の最大値である。

高さが単根の木${\displaystyle \leq \omega }$ミートセミラティスを形成し、ミート（共通の前駆者）は前駆者の交差の最大要素によって与えられます。この最大要素は、前駆者の集合が空ではなく有限であるため存在します。単一のルートがない場合、前駆者の交差は空になる可能性があります（2つの要素は共通の祖先を持つ必要はありません）。たとえば、${\displaystyle \left\{a,b\right\}}$要素が比較できない場合、また、無限に多くの先行要素がある場合には、最大要素が存在する必要はありません。例として、木があります。${\displaystyle \left\{0,1,2,\dots ,\omega _{0},\omega _{0}'\right\}}$どこ${\displaystyle \omega _{0},\omega _{0}'}$比較対象にはならない。

木のサブツリー${\displaystyle (T,<)}$木です${\displaystyle (T',<)}$どこ${\displaystyle T'\subseteq T}$そして${\displaystyle T'}$下方閉じている${\displaystyle <}$つまり、もし${\displaystyle s,t\in T}$そして${\displaystyle s<t}$それから${\displaystyle t\in T'\implies s\in T'}$部分木の各要素の高さは、全体の木におけるその要素の高さと等しい。^{[ 1 ]}これは、グラフ理論における部分木の概念とは異なり、部分木は全体の木とは異なる根を持つことが多い。

無限木理論には、比較的単純に述べられているものの難しい問題がいくつか存在する。その例として、クレパ予想とススリン予想が挙げられる。これらの問題はどちらもツェルメロ・フレンケル集合論とは独立していることが知られている。ケーニッヒの補題によれば、すべての${\displaystyle \omega }$-木は無限枝を持つ。一方、ZFCの定理によれば、枝もレベルも数えきれない木は数えきれないほど存在し、そのような木はアロンシャイン木として知られている。基数が与えられた場合、${\displaystyle \kappa }$、${\displaystyle \kappa }$-ススリンの木は高さのある木です${\displaystyle \kappa }$サイズがチェーンや反チェーンを持たない${\displaystyle \kappa }$特に、${\displaystyle \kappa }$が単数基数である場合、${\displaystyle \kappa }$-アロンシャインの木と${\displaystyle \kappa }$-Suslin木。実際、任意の無限基数に対して${\displaystyle \kappa }$、 毎${\displaystyle \kappa }$-ススリンの木は${\displaystyle \kappa }$-アロンシャイン木（逆は成り立たない）。弱コンパクト基数を定義する同等の方法の1つは、それが到達不可能な基数であるということである。${\displaystyle \kappa }$ツリープロパティを持つ、つまり${\displaystyle \kappa }$-アロンシャインツリー。^{[ 2 ]}

ススリン予想は元々、ある種の全順序に関する問題として述べられたが、それは次の命題と同等である。高さが最初の不可算順序数であるすべての木$\displaystyle \omega _{1}}$基数の反鎖を持つ$\displaystyle \omega _{1}}$または長さの枝$\displaystyle \omega _{1}}$。

もし${\displaystyle (T,<)}$木である場合、反射閉包${\displaystyle \leq }$の${\displaystyle <}$は、​${\displaystyle T}$逆は成り立たない。例えば、通常の順序では${\displaystyle \leq }$撮影現場で${\displaystyle \mathbb {Z} }$整数の は合計であり、したがって前置順序ですが、${\displaystyle (\mathbb {Z} ,<)}$集合論的な木ではない。例えば集合は${\displaystyle \{n\in \mathbb {Z} :n<0\}}$最小要素は存在しない。

• させて${\displaystyle \kappa }$を序数とし、${\displaystyle X}$集合とする。${\displaystyle T}$すべての関数のセット${\displaystyle f:\alpha \mapsto X}$どこ${\displaystyle \alpha <\kappa }$。 定義する${\displaystyle f<g}$ドメインが​${\displaystyle f}$は、のドメインの真部分集合である。${\displaystyle g}$そして、2つの関数は、${\displaystyle f}$。 それから${\displaystyle (T,<)}$は集合論的な木である。その根は空集合上の唯一の関数であり、その高さは${\displaystyle \kappa }$.ブランチに沿ったすべての関数の和集合は、次の関数を生成します。${\displaystyle \kappa }$に${\displaystyle X}$つまり、メンバーの一般化されたシーケンス${\displaystyle X}$。 もし${\displaystyle \kappa }$は極限順序数であり、どの枝にも最大要素（「葉」）はありません。図は、の例を示しています。${\displaystyle \kappa =\omega \cdot 2}$そして${\displaystyle X=\{0,1\}}$。

• コンピュータサイエンスにおける各ツリーデータ構造は集合論的なツリーである。2つのノードの場合${\displaystyle m,n}$、 定義する${\displaystyle m<n}$もし${\displaystyle n}$は${\displaystyle m}$ルート、ノードの高さ、枝の長さの概念は一致するが、ツリーの高さの概念は1つ異なる。

• オートマトン理論で考慮される無限木（例えば、木（オートマトン理論）を参照）は、集合論的木でもあり、木の高さは最大で${\displaystyle \omega }$。

• グラフ理論上の木は、ルートノードを選択することで集合論上の木に変換できる。${\displaystyle r}$そして定義する${\displaystyle m<n}$もし${\displaystyle m\neq n}$そして${\displaystyle m}$は、(唯一の)無向パス上に位置する。${\displaystyle r}$に${\displaystyle n}$。

• カントール木、クレパ木、ラバー木はいずれも集合論的な木である。

• 木構造（記述集合論）
• 連続グラフ

• Ieke MoerdijkとJaap van Oostenによる「集合、モデル、および証明」。68 ～ 69ページの定義 3.1 と演習 56 を参照 。
• 木構造（集合論的） by Henry on PlanetMath
• HenryによるPlanetMathのブランチ
• PlanetMathのuzeromayによる木の例（集合論的）