Definition:Tree (Set Theory)

This page is about Tree in the context of Set Theory. For other uses, see Tree.

Definition

Let $\struct {T, \preceq}$ be an ordered set.

Let $\struct {T, \preceq}$ be such that for every $t \in T$, the lower closure of $t$:

$t^\preceq := \set {s \in T: s \preceq t}$

is well-ordered by $\preceq$.

Then $\struct {T, \preceq}$ is a tree.

Branch

Let $\struct {T, \preceq}$ be a tree.

A branch of $\struct {T, \preceq}$ is a maximal chain in $\struct {T, \preceq}$.

Subtree

Let $\struct {T, \preceq}$ be a tree.

A subtree of $\struct {T, \preceq}$ is an ordered subset $\struct {S, \preceq}$ with the property that:

for every $\forall s \in S: \forall t \in T: t \preceq s \implies t \in S$

That is, such that $\struct {S, \preceq}$ is a lower closure of $\struct {T, \preceq}$.