树（tree）在集合论中是一类具有树状结构的偏序集，其特点是：每个元素的所有前驱（即小于该元素的元素）构成一个良序集。这一概念与图论中的树密切相关，但在集合论中有着更广泛和抽象的形式。

定义
设 \langle S, R \rangle 为一个偏序结构（即 R 是 S 上的偏序关系）。若它满足以下条件：

对任意 x \in S，集合

:A(x) = \{ y \in S \mid y R x \}

对于关系 R 是三歧的（即任意两个元素均可比较）、传递的，并且 A(x) 的任意非空真子集都存在极小元——换言之，\langle A(x), R \rangle 是一个良序结构——

则称该偏序结构 \langle S, R \rangle 为树。

等价地，一棵树可以定义为一个偏序集 \langle T, ，使得对每个 t \in T，集合

:\{ s \in T \mid s

在关系 下是良序的。

基本概念
高度
设 \langle S, R \rangle 为一棵树。对任意元素 x \in S，与集合 A(x) = \{ y \in S \mid y R x \} 序同构的唯一序数称为 x 在树中的高度，记为 \operatorname{ht}(x)。

对于每个序数 \alpha，集合

:T_\alpha = \{ x \in S \mid \operatorname{ht}(x) = \alpha \}

称为树的第 \alpha 层（\alpha-th level）。使得 T_\alpha = \varnothing 的最小序数 \alpha 称为树的高度。

根
高度为 0 的元素称为树的根（root）。在集合论树的研究中，通常假定树只有一个根（单根树），因为许多问题可以简化到这种情况。

分支
树的一条分支（branch）是指树中的一个极大链（maximal chain），即分支中任意两个元素都可比，且树中任何不在该分支中的元素都与分支中至少一个元素不可比。分支的长度是与该分支序同构的序数。

特殊类型的树
\kappa-树
设 \kappa 为一个基数。若一棵树的高度为 \kappa，且每一层的大小都小于 \kappa，则称该树为 \kappa-树（\kappa-tree）。

\kappa-树在组合集合论和力迫理论中具有重要地位。例如，Suslin 树 便是一类特殊的 \omega_1-树。

子树
若 \langle T', 是一棵树，且 T' \subseteq T，并且 T' 上的序关系与 T 上的序关系一致，则称 \langle T', 为 \langle T, 的子树（subtree）。

与图论中树的关系
集合论中的树与图论中的树有着密切联系。若一棵集合论树是单根的，则可以通过以下两种方式之一将其视为图论意义下的有根树：

将偏序集的哈塞图（Hasse diagram）视为无向图；

直接将偏序集的基础图视为无向图。

不过，集合论中的树允许无限长度和无限分支，因此比图论中的树更为一般。

树的高度
若为树，那么对于s中任一元素，与集合A（x）={y∈s丨yRx}同构的序数被称为x在树中所处的高度，记为ht（x）。

我们把集合T（a）={x∈s丨ht(x)=a}称为树的a层，而满足T（a）=∅的最小序数便被称为「树的高度」。

參考文獻