# Branch of Finite Tree is Finite

Jump to navigation
Jump to search

## Theorem

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

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

Then $\Gamma$ is a finite branch.

## Proof

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

Aiming for a contradiction, suppose $\Gamma$ were an infinite branch of $T$.

By definition $\Gamma$ contains an infinite number of nodes.

This article, or a section of it, needs explaining.In particular: Technically, from the definition currently posted, it doesn't - that still needs to be demonstrated.You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Explain}}` from the code. |

From Subset of Finite Set is Finite, it follows that $\Gamma$ has a finite number of nodes.

From this contradiction it follows that $\Gamma$ can not be an infinite branch of $T$.

Hence the result.

$\blacksquare$

## Sources

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