# example of tree (set theoretic)

The set $\mathbb{Z}^{+}$ is a tree with $<_{T}=<$. This isn’t a very interesting tree, since it simply consists of a line of nodes. However note that the height is $\omega$ even though no particular node has that height.

A more interesting tree using $\mathbb{Z}^{+}$ defines $m<_{T}n$ if $i^{a}=m$ and $i^{b}=n$ for some $i,a,b\in\mathbb{Z}^{+}\cup\{0\}$. Then $1$ is the root, and all numbers which are not powers of another number are in $T_{1}$. Then all squares (which are not also fourth powers) for $T_{2}$, and so on.

To illustrate the concept of a cofinal branch, observe that for any limit ordinal $\kappa$ we can construct a $\kappa$-tree which has no cofinal branches. We let $T=\{(\alpha,\beta)|\alpha<\beta<\kappa\}$ and $(\alpha_{1},\beta_{1})<_{T}(\alpha_{2},\beta_{2})\leftrightarrow\alpha_{1}<% \alpha_{2}\wedge\beta_{1}=\beta_{2}$. The tree then has $\kappa$ disjoint branches, each consisting of the set $\{(\alpha,\beta)|\alpha<\beta\}$ for some $\beta<\kappa$. No branch is cofinal, since each branch is capped at $\beta$ elements, but for any $\gamma<\kappa$, there is a branch of height $\gamma+1$. Hence the supremum of the heights is $\kappa$.

Title example of tree (set theoretic) ExampleOfTreesetTheoretic 2013-03-22 12:52:27 2013-03-22 12:52:27 uzeromay (4983) uzeromay (4983) 5 uzeromay (4983) Example msc 05C05 msc 03E05 CofinalBranch