# Definition:Rooted Tree/Branch

Jump to navigation
Jump to search

## Definition

Let $T$ be a rooted tree with root node $r_T$.

A subset $\Gamma$ of $T$ is a **branch** if and only if all the following conditions hold:

- $(1): \quad$ The root node $r_T$ belongs to $\Gamma$
- $(2): \quad$ The parent of each node in $\Gamma \setminus \left\{{r_T}\right\}$ is in $\Gamma$
- $(3): \quad$ Each node in $\Gamma$ either:
- $(a): \quad$ is a leaf node of $T$

- or:
- $(b): \quad$ has exactly one child node in $\Gamma$.

Informally, a **branch** of a rooted tree is the path from the root to a leaf.

### Finite

Let $T$ be a rooted tree with root node $r_T$.

Let $\Gamma$ be a branch of $T$.

Then $\Gamma$ is **finite** if and only if it has exactly one leaf node.

### Infinite

Let $T$ be a rooted tree with root node $r_T$.

Let $\Gamma$ be a branch of $T$.

Then $\Gamma$ is infinite if and only if it has no leaf node at the end.

## Length

Let $T$ be a rooted tree with root node $r_T$.

Let $\Gamma$ be a finite branch of $T$.

The **length** of $\Gamma$ is defined as the number of ancestors of the leaf at the end of that branch.

## Also see

- Node of Rooted Tree is on Branch
- Leaf of Rooted Tree is on One Branch
- Node of Rooted Tree with Multiple Children is on Multiple Branches

## Sources

- 1996: H. Jerome Keisler and Joel Robbin:
*Mathematical Logic and Computability*... (previous) ... (next): $\S 1.7$: Tableaus