# Interpreting a nonstandard definition of a tree

Definition: A tree is a triple $(T,\sigma,\pi)$ where $T$ is a set and $\sigma$ is a so-called successor function from $T$ to the set $T^*$ of all nonempty subsets of $T$, together with a surjective map $\pi:T\rightarrow \mathbb{N}$ such that the following diagram commutes

$$\newcommand{\ra}[1]{\!\!\xrightarrow{\quad#1\quad}\!\!} \newcommand{\da}[1]{\left\downarrow{\scriptstyle#1}\vphantom{\displaystyle\int_0^1}\right.} % \begin{array}{ll} T & \ra{\sigma} & T^* \\ \da{\pi} & & \da{\pi^*} \\ \mathbb{N} & \ra{\sigma^*}&\mathbb{N}^*\\ \end{array}$$

where $\sigma^*$ is the composition of the successor function on $\mathbb{N}$ followed by inclusion into the set $\mathbb{N}$ of all nonempty subsets of $\mathbb{N}$ and $\pi^*:T^*\rightarrow \mathbb{N}^*$ is the map induced by $\pi$ on nonempty subsets of $T$.

I am wanting to understand how the intervals used in the construction of the Cantor middle-third set could be described using the language is this definition. What seems clear to me is that the set $T$ would be subintervals of [0,1] in the construction of the Cantor set, and $\sigma$ would be a relation relating each parent intervals to their two children, which accounts for $T^*$. What I am not clear about is how the rest of the diagram applies. I have had a few ideas about enumerating the sets, but none seem to sync up with the diagram in a sensible way. Additionally I think the fact that the branches in the Cantor construction are nested should be reflected somehow throughout the map. I am imagining some sort of map that takes a word in $\mathbb{N}$ to a "nested word" in $\mathbb{N}^*$, but I am struggling to make this explicit.

The map $\pi$ assigns to each node of the tree $T$ its level. In the specific case of the binary tree of intervals used in the construction of the middle-thirds Cantor set, $\pi([0,1])=0$,

$$\pi([0,1/3])=\pi([2/3,1])=1\;,$$

and so on: if $\pi(I)=n$, and $I_0$ and $I_1$ are the two children of $I$, then $\pi(I_0)=\pi(I_1)=n+1$. The map $\sigma^*$ takes $n\in\Bbb N$ to $\{n+1\}$, the singleton of the successor of $n$.

Saying that the diagram commutes is just saying that if $I$ is an interval on level $n$ of the tree, so that $\pi(I)=n$, then the set of children of $I$ is a subset of level $n+1$ of the tree: every child $J$ of $I$ will satisfy $\pi(J)=n+1$.

This is really not a definition of trees in general: it’s a definition of trees of height $\omega$.

• But isn't the set containment $\supset$ implied in the Cantor construction via $\sigma$ is lost via $\sigma^*$? Given a particular interval on level $n$ it does not necessarily contain a child on level $n+1$. I'm looking for a way to preserve this containment via $\sigma^*$. – Earl Nov 20 '15 at 19:38
• @hammy: Every interval on level $n$ has (and contains as subsets) exactly two children on level $n+1$. And you have no control over $\sigma^*$: it’s given, and is simply the map $\sigma^*(n)=\{n+1\}$. The containment relation among subsets of $T$ has nothing to do with the containment relation among subsets of $\Bbb R$ in the construction of the Cantor set. – Brian M. Scott Nov 20 '15 at 19:49
• I understand the map you suggest, and thank you for the clear explanation. But what I am looking for is a map that preserves this containment. That is, shouldn't we be able to find a map that indicates when $\sigma^*(n)\in\mathbb{N}^*$ is 'contained' in $n\in\mathbb{N}$ instead of just knowing that $\sigma^*(n)$ is on the $n+1$ level. – Earl Nov 20 '15 at 20:46
• @hammy: I can’t make any sense out of that, I’m afraid: $\sigma^*(n)$ isn’t even in the tree, let alone in the $(n+1)$-st level. The definition that you’ve given in your question is simply a fancy way of defining the levels of a tree of height $\omega$. If you want something more than or otherwise different from that, you should toss that definition and explain exactly what it is that you’re trying to do. – Brian M. Scott Nov 20 '15 at 20:51
• @ Brian M. Scott- Got it. I was hoping that I could say more with the diagram. I see now that $\sigma^*$ is not a choice. I did not realize that successor function implied that it must be a "+1". – Earl Nov 22 '15 at 15:18